performance flexible jobshop with machine transition times

[getdig...@gmail.com]

Hi Laurent, all,

Have checked all posts on jobshop but have not yet been able to find a solution direction to improve performance for a flexible jobshop example including arcs to deal with transition times for machines. 

I used the flexible job shop example from Laurent (link) as basis and included a circuit constraint (arc) to define transition times for tasks on the same machine depending on a changing job number of the next task.

The model works fine however when adding more than ~10 jobs (in line 57) the solver starts struggling to find a solution. It seems the combination of constraints for precedence in jobs in combination with constraints related to machines (transition times) is resulting in too many constraints to get the model properly working. Without the transition time constraints adding several hundreds of jobs is not a problem for performance.

The example code has been attached. Any suggestions would be very welcome! Many thanks, Olivier              

[Laurent Perron]

Can you increase the horizon?

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/dbc193df-a016-4b32-8d8a-fc1f8f3e91bcn%40googlegroups.com.

[getdig...@gmail.com]

When I double horizon performance gets worse. When running for 10 jobs at the horizon defined in the example code intermediate solutions 0, 1, 2, 3, 4 were found in respectively 2.8, 4.7, 12.4, 14.2 and 25.0 seconds. After doubling horizon intermediate solutions 0, 1, 2, 3, and 4 are found after respectively 15.2, 16.7, 20.3, 33.3 and 37.1 seconds. 

For 30 jobs I won't get a first solution within 5 minutes and will try to run overnight to see if there will be any results.  

Op donderdag 17 februari 2022 om 18:28:24 UTC+1 schreef Laurent Perron:

[getdig...@gmail.com]

No solution found after 8 hours for 30 tasks and doubled horizon , see below the statistics 

Log:

Horizon = 540

Starting CP-SAT solver.
Parameters: max_time_in_seconds: 28800 log_search_progress: true

Initial optimization model '':
#Variables: 25652 (1 in objective)
  - 24840 in [0,1]
  - 721 in [0,540]
  - 91 constants in {3}
#kCircuit: 3
#kIntMax: 1
#kInterval: 360 (#enforced: 270)
#kLinear1: 270 (#enforced: 270)
#kLinear2: 24630 (#enforced: 24570)
#kLinear3: 90
#kNoOverlap: 3

Starting presolve at 0.03s
[Probing] deterministic_time: 1.00002 (limit: 1) wall_time: 1.00883 (Aborted 12023/24841)
[Probing]  - new fixed Boolean: 129 (130/24841)
[Probing]  - new binary clause: 6735
30 affine relations still in the model.

Presolve summary:
  - 180 affine relations were detected.
  - 90 variable equivalence relations were detected.
  - rule 'affine: new relation' was applied 90 times.
  - rule 'circuit: removed false arcs.' was applied 2 times.
  - rule 'deductions: 48600 stored' was applied 1 time.
  - rule 'false enforcement literal' was applied 129 times.
  - rule 'int_max: reduced domains' was applied 2 times.
  - rule 'interval: reduced domains' was applied 90 times.
  - rule 'interval: unused, converted to linear' was applied 90 times.
  - rule 'linear: empty' was applied 270 times.
  - rule 'linear: fixed or dup variables' was applied 90 times.
  - rule 'linear: positive equal one' was applied 90 times.
  - rule 'linear: reduced variable domains' was applied 90 times.
  - rule 'linear: remapped using affine relations' was applied 330 times.
  - rule 'linear: simplified rhs' was applied 24180 times.
  - rule 'presolve: iteration' was applied 1 time.

Presolved optimization model '':
#Variables: 25373 (1 in objective)
  - 24711 in [0,1]
  - 30 in [0,531]
  - 540 in [0,540]
  - 30 in [3,534]
  - 30 in [6,537]
  - 31 in [9,540]
  - 1 constants in {3}
#kCircuit: 3
#kExactlyOne: 90 (#literals: 270)
#kIntMax: 1
#kInterval: 270 (#enforced: 270)
#kLinear2: 24531 (#enforced: 24441)
#kNoOverlap: 3

Preloading model.
#Bound   1.51s best:inf   next:[9,540]    initial_domain

Starting to load the model at 1.51s
[Probing] deterministic_time: 1.00001 (limit: 1) wall_time: 1.02346 (Aborted 12138/24712)
[Probing]  - new fixed Boolean: 3 (4/24712)
[Probing]  - new binary clause: 6738
Initial num_bool: 24712

Starting sequential search at 3.30s

CpSolverResponse summary:
status: UNKNOWN
objective: 540
best_bound: 9
booleans: 24712
conflicts: 150762
branches: 1460176
propagations: 29777980
integer_propagations: 60849120
restarts: 24421
lp_iterations: 1350814
walltime: 28799.9
usertime: 28799.9
deterministic_time: 34034.4
primal_integral: 0

Total cuts added: 89564 (out of 90403 calls) worker: ''
  - num simplifications: 0
  - added 64455 cuts of type 'CG'.
  - added 19730 cuts of type 'CG_K'.
  - added 119 cuts of type 'MIR_1'.
  - added 341 cuts of type 'MIR_2'.
  - added 293 cuts of type 'MIR_3'.
  - added 214 cuts of type 'MIR_4'.
  - added 186 cuts of type 'MIR_5'.
  - added 151 cuts of type 'MIR_6'.
  - added 3941 cuts of type 'ZERO_HALF'.
  - added 134 cuts of type 'ZERO_HALF_K'.

Process finished with exit code 0

Op donderdag 17 februari 2022 om 20:03:44 UTC+1 schreef getdig...@gmail.com:

[Laurent Perron]

There is most likely something wrong with the model.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/aa8e0dcf-4242-4461-976f-e4b2233a6b7en%40googlegroups.com.

[Laurent Perron]

I tripled the horizon. I get the first solution in 4s. 

Horizon = 810

Starting CP-SAT solver v9.2.10257

Parameters: max_time_in_seconds: 300 log_search_progress: true

Setting number of workers to 16

Initial optimization model '':

#Variables: 25651 (#ints:1 in objective)

  - 24840 in [0,1]

  - 721 in [0,810]

  - 90 constants in {3} 

#kCircuit: 3

#kInterval: 360 (#enforced: 270)

#kLinMax: 1

#kLinear1: 270 (#enforced: 270)

#kLinear2: 24900 (#enforced: 24840)

#kLinear3: 180

#kNoOverlap: 3 (#intervals: 270, #optional: 270)

Starting presolve at 0.01s

[ExtractEncodingFromLinear] #potential_supersets=90 #potential_subsets=0 #at_most_one_encodings=0 #exactly_one_encodings=0 #unique_terms=0 #multiple_terms=0 #literals=0 time=8e-05s

[Probing] deterministic_time: 1.00002 (limit: 1) wall_time: 0.729557 (Aborted 12023/24841)

[Probing]  - new fixed Boolean: 129 (130/24841)

[Probing]  - new binary clause: 6735

[DetectDuplicateConstraints] #duplicates=0 time=0.0152535s

[DetectDominatedLinearConstraints] #relevant_constraints=60 #work_done=360 #num_inclusions=0 #num_redundant=0 time=0.000166363s

[DetectOverlappingColumns] #processed_columns=0 #work_done=0 #nz_reduction=0 time=0.0019856s

[ProcessSetPPC] #relevant_constraints=90 #num_inclusions=0 work=810 time=0.000254187s

Presolve summary:

  - 90 affine relations were detected.

  - rule 'affine: new relation' was applied 90 times.

  - rule 'circuit: removed false arcs.' was applied 2 times.

  - rule 'deductions: 48600 stored' was applied 1 time.

  - rule 'false enforcement literal' was applied 129 times.

  - rule 'interval: performed intervals must have a positive size' was applied 390 times.

  - rule 'lin_max: target domain reduced' was applied 1 time.

  - rule 'linear: always true' was applied 270 times.

  - rule 'linear: fixed or dup variables' was applied 90 times.

  - rule 'linear: positive equal one' was applied 90 times.

  - rule 'linear: reduced variable domains' was applied 180 times.

  - rule 'linear: remapped using affine relations' was applied 450 times.

  - rule 'linear: simplified rhs' was applied 24120 times.

  - rule 'presolve: 219 unused variables removed.' was applied 1 time.

  - rule 'presolve: iteration' was applied 1 time.

Presolved optimization model '':

#Variables: 25342 (#ints:1 in objective)

  - 24711 in [0,1]

  - 30 in [0,801]

  - 540 in [0,810]

  - 30 in [3,804]

  - 30 in [6,807]

  - 1 in [9,810]

#kCircuit: 3

#kExactlyOne: 90 (#literals: 270)

#kInterval: 360 (#enforced: 270)

#kLinMax: 1

#kLinear2: 24771 (#enforced: 24711)

#kNoOverlap: 3 (#intervals: 270, #optional: 270)

Preloading model.

#Bound   1.10s best:inf   next:[9,810]    initial_domain

Starting Search at 1.14s with 16 workers.

10 full subsolvers: [default_lp, fixed, no_lp, max_lp, reduced_costs, pseudo_costs, quick_restart, quick_restart_no_lp, lb_tree_search, probing]

Interleaved subsolvers: [feasibility_pump, rnd_var_lns_default, rnd_cst_lns_default, graph_var_lns_default, graph_cst_lns_default, scheduling_time_window_lns_default, scheduling_random_lns_default, routing_random_lns_default, routing_path_lns_default, routing_full_path_lns_default, rins_lns_default, rens_lns_default]

#1       4.04s best:414   next:[9,413]    quick_restart_no_lp fixed_bools:9/25162

#2       5.13s best:365   next:[9,364]    no_lp fixed_bools:9/25162

#3       5.18s best:364   next:[9,363]    no_lp fixed_bools:10/25163

#4       5.26s best:362   next:[9,361]    no_lp fixed_bools:10/25192

#5       5.29s best:361   next:[9,360]    no_lp fixed_bools:12/25192

#6       5.38s best:358   next:[9,357]    no_lp fixed_bools:12/25210

#7       5.54s best:357   next:[9,356]    no_lp fixed_bools:15/25210

#8       9.42s best:356   next:[9,355]    routing_random_lns_default(d=0.29 s=58 t=0.10 p=0.00)

#9      10.33s best:352   next:[9,351]    graph_cst_lns_default(d=0.46 s=65 t=0.10 p=0.50)

#10     11.20s best:349   next:[9,348]    no_lp fixed_bools:19/25235

#11     11.24s best:348   next:[9,347]    no_lp fixed_bools:25/25236

#12     11.32s best:347   next:[9,346]    no_lp fixed_bools:26/25240

#13     11.34s best:346   next:[9,345]    no_lp fixed_bools:29/25241

#14     11.37s best:345   next:[9,344]    no_lp fixed_bools:32/25241

#15     11.50s best:344   next:[9,343]    no_lp fixed_bools:34/25248

#16     11.52s best:343   next:[9,342]    no_lp fixed_bools:35/25249

#17     11.55s best:342   next:[9,341]    no_lp fixed_bools:37/25250

#18     11.95s best:341   next:[9,340]    no_lp fixed_bools:40/25264

#19     11.98s best:338   next:[9,337]    no_lp fixed_bools:41/25283

#20     14.57s best:328   next:[9,327]    routing_random_lns_default(d=0.12 s=78 t=0.10 p=0.00)

#21     16.39s best:325   next:[9,324]    routing_full_path_lns_default(d=0.19 s=80 t=0.10 p=0.00)

#22     17.54s best:324   next:[9,323]    no_lp fixed_bools:69/25317

#23     18.01s best:322   next:[9,321]    no_lp fixed_bools:69/25342

#24     18.43s best:320   next:[9,319]    no_lp fixed_bools:76/25421

#25     18.89s best:312   next:[9,311]    routing_path_lns_default(d=0.18 s=89 t=0.10 p=0.25)

#26     19.33s best:311   next:[9,310]    no_lp fixed_bools:100/25449

#27     20.24s best:310   next:[9,309]    no_lp fixed_bools:104/25461

#28     21.92s best:305   next:[9,304]    no_lp fixed_bools:108/25486

#29     23.52s best:292   next:[9,291]    routing_path_lns_default(d=0.13 s=99 t=0.10 p=0.20)

#30     25.02s best:290   next:[9,289]    routing_random_lns_default(d=0.18 s=108 t=0.10 p=0.33)

#31     26.70s best:282   next:[9,281]    routing_path_lns_default(d=0.09 s=109 t=0.10 p=0.17)

#32     30.36s best:274   next:[9,273]    routing_random_lns_default(d=0.24 s=118 t=0.10 p=0.43)

#Bound  31.50s best:274   next:[10,273]   reduced_costs

#33     33.15s best:270   next:[10,269]   graph_cst_lns_default(d=0.36 s=125 t=0.10 p=0.43)

#34     33.31s best:269   next:[10,268]   routing_random_lns_default(d=0.18 s=128 t=0.10 p=0.38)

#35     34.49s best:261   next:[10,260]   routing_path_lns_default(d=0.09 s=129 t=0.10 p=0.25)

#36     36.31s best:256   next:[10,255]   routing_random_lns_default(d=0.23 s=138 t=0.10 p=0.44)

#37     37.05s best:247   next:[10,246]   routing_path_lns_default(d=0.07 s=139 t=0.10 p=0.22)

#38     39.12s best:235   next:[10,234]   routing_random_lns_default(d=0.18 s=148 t=0.10 p=0.40)

#39     42.36s best:226   next:[10,225]   routing_random_lns_default(d=0.23 s=158 t=0.10 p=0.45)

#Bound  43.62s best:226   next:[11,225]   reduced_costs

#40     43.68s best:222   next:[11,221]   routing_random_lns_default(d=0.18 s=168 t=0.10 p=0.42)

#41     47.31s best:212   next:[11,211]   routing_random_lns_default(d=0.23 s=178 t=0.10 p=0.46)

#42     50.30s best:211   next:[11,210]   routing_random_lns_default(d=0.18 s=188 t=0.10 p=0.43)

#43     54.99s best:203   next:[11,202]   routing_random_lns_default(d=0.23 s=198 t=0.10 p=0.47)

#44     59.18s best:198   next:[11,197]   routing_random_lns_default(d=0.18 s=209 t=0.10 p=0.44)

#Bound  60.15s best:198   next:[12,197]   reduced_costs

#45     61.16s best:195   next:[12,194]   routing_random_lns_default(d=0.15 s=221 t=0.10 p=0.41)

#46     64.32s best:194   next:[12,193]   routing_full_path_lns_default(d=0.20 s=235 t=0.10 p=0.44)

#47     67.30s best:190   next:[12,189]   routing_random_lns_default(d=0.22 s=245 t=0.10 p=0.47)

#48     70.43s best:186   next:[12,185]   routing_random_lns_default(d=0.18 s=257 t=0.10 p=0.45)

#49     74.04s best:185   next:[12,184]   routing_random_lns_default(d=0.22 s=269 t=0.10 p=0.48)

#50     76.87s best:182   next:[12,181]   routing_random_lns_default(d=0.18 s=281 t=0.10 p=0.45)

#51     80.90s best:164   next:[12,163]   routing_random_lns_default(d=0.22 s=293 t=0.10 p=0.48)

#52     83.14s best:160   next:[12,159]   routing_random_lns_default(d=0.19 s=305 t=0.10 p=0.46)

#53     86.56s best:151   next:[12,150]   routing_random_lns_default(d=0.22 s=317 t=0.10 p=0.48)

#54     89.20s best:139   next:[12,138]   routing_path_lns_default(d=0.10 s=330 t=0.10 p=0.42)

#55     89.85s best:136   next:[12,135]   routing_full_path_lns_default(d=0.20 s=331 t=0.10 p=0.46)

#56     94.53s best:132   next:[12,131]   routing_full_path_lns_default(d=0.20 s=355 t=0.10 p=0.46)

#57     97.90s best:131   next:[12,130]   routing_full_path_lns_default(d=0.20 s=379 t=0.10 p=0.47)

#58     97.98s best:130   next:[12,129]   routing_random_lns_default(d=0.19 s=377 t=0.10 p=0.47)

#59    100.15s best:126   next:[12,125]   routing_random_lns_default(d=0.22 s=389 t=0.10 p=0.48)

#60    101.07s best:124   next:[12,123]   routing_random_lns_default(d=0.19 s=401 t=0.10 p=0.47)

#61    104.83s best:123   next:[12,122]   graph_var_lns_default(d=0.42 s=421 t=0.10 p=0.47)

#62    109.58s best:122   next:[12,121]   routing_random_lns_default(d=0.19 s=449 t=0.10 p=0.47)

#63    111.53s best:121   next:[12,120]   routing_random_lns_default(d=0.22 s=461 t=0.10 p=0.49)

#64    116.72s best:119   next:[12,118]   routing_path_lns_default(d=0.12 s=486 t=0.10 p=0.46)

Sub-solver search statistics:

  'max_lp':

     LP statistics:

       final dimension: 1851 rows, 25645 columns, 236660 entries with magnitude in [3.513642e-02, 1.000000e+00]

       total number of simplex iterations: 101169

       num solves: 

         - #OPTIMAL: 2102

         - #DUAL_UNBOUNDED: 4

         - #DUAL_FEASIBLE: 6076

       managed constraints: 31772

       merged constraints: 2821

       shortened constraints: 2344

       coefficient strenghtenings: 4706

       num simplifications: 5755

       total cuts added: 5493 (out of 11483 calls)

         - 'CG': 47

         - 'Circuit': 1827

         - 'IB': 3299

         - 'LinMax': 2

         - 'MIR_1': 75

         - 'MIR_2': 24

         - 'MIR_3': 15

         - 'MIR_4': 13

         - 'MIR_5': 15

         - 'MIR_6': 11

         - 'ZERO_HALF': 50

         - 'clique': 115

  'reduced_costs':

     LP statistics:

       final dimension: 4655 rows, 25645 columns, 218564 entries with magnitude in [3.857010e-03, 1.000000e+00]

       total number of simplex iterations: 94449

       num solves: 

         - #OPTIMAL: 190

         - #DUAL_UNBOUNDED: 3

         - #DUAL_FEASIBLE: 6136

       managed constraints: 35288

       merged constraints: 1083

       shortened constraints: 1289

       coefficient strenghtenings: 5890

       num simplifications: 7148

       total cuts added: 10009 (out of 19352 calls)

         - 'CG': 74

         - 'Circuit': 1014

         - 'IB': 8262

         - 'LinMax': 21

         - 'MIR_1': 145

         - 'MIR_2': 50

         - 'MIR_3': 61

         - 'MIR_4': 54

         - 'MIR_5': 67

         - 'MIR_6': 56

         - 'ZERO_HALF': 81

         - 'ZERO_HALF_K': 2

         - 'clique': 122

  'pseudo_costs':

     LP statistics:

       final dimension: 1955 rows, 25645 columns, 77899 entries with magnitude in [2.678571e-02, 1.000000e+00]

       total number of simplex iterations: 120700

       num solves: 

         - #OPTIMAL: 1837

         - #DUAL_UNBOUNDED: 30

         - #DUAL_FEASIBLE: 5243

       managed constraints: 35889

       merged constraints: 3102

       shortened constraints: 2223

       coefficient strenghtenings: 6399

       num simplifications: 7964

       total cuts added: 10610 (out of 27525 calls)

         - 'CG': 113

         - 'Circuit': 1658

         - 'IB': 8241

         - 'LinMax': 28

         - 'MIR_1': 151

         - 'MIR_2': 38

         - 'MIR_3': 33

         - 'MIR_4': 24

         - 'MIR_5': 39

         - 'MIR_6': 34

         - 'ZERO_HALF': 64

         - 'clique': 187

  'lb_tree_search':

     LP statistics:

       final dimension: 6155 rows, 25645 columns, 547374 entries with magnitude in [9.390603e-04, 1.000000e+00]

       total number of simplex iterations: 216995

       num solves: 

         - #OPTIMAL: 197

         - #DUAL_FEASIBLE: 8583

       managed constraints: 36162

       merged constraints: 1048

       shortened constraints: 2253

       coefficient strenghtenings: 8743

       num simplifications: 10997

       total cuts added: 9883 (out of 12923 calls)

         - 'CG': 49

         - 'Circuit': 1735

         - 'IB': 7167

         - 'LinMax': 32

         - 'MIR_1': 286

         - 'MIR_2': 30

         - 'MIR_3': 52

         - 'MIR_4': 34

         - 'MIR_5': 93

         - 'MIR_6': 71

         - 'ZERO_HALF': 89

         - 'clique': 245

Solutions found per subsolver:

  'graph_cst_lns_default': 2

  'graph_var_lns_default': 1

  'no_lp': 22

  'quick_restart_no_lp': 1

  'routing_full_path_lns_default': 5

  'routing_path_lns_default': 7

  'routing_random_lns_default': 26

Objective bounds found per subsolver:

  'initial_domain': 1

  'reduced_costs': 3

Improving variable bounds shared per subsolver:

  'default_lp': 2

  'lb_tree_search': 3

  'max_lp': 1

  'no_lp': 1924

  'pseudo_costs': 7

  'quick_restart_no_lp': 3928

  'reduced_costs': 3

Clauses shared per subsolver:

  'default_lp': 4

  'no_lp': 16

  'pseudo_costs': 2

  'quick_restart_no_lp': 132

CpSolverResponse summary:

status: FEASIBLE

objective: 119

best_bound: 12

booleans: 24712

conflicts: 86

branches: 50400

propagations: 10901427

integer_propagations: 499340

restarts: 24288

lp_iterations: 34651

walltime: 302.618

usertime: 302.618

deterministic_time: 439.971

gap_integral: 2066.41

Job 0:

  task_0_0 starts at 0 (alt 2, machine 2, duration 3)

  task_0_1 starts at 60 (alt 0, machine 0, duration 3)

  task_0_2 starts at 68 (alt 0, machine 0, duration 3)

Job 1:

  task_1_0 starts at 20 (alt 1, machine 1, duration 3)

  task_1_1 starts at 56 (alt 2, machine 2, duration 3)

  task_1_2 starts at 64 (alt 1, machine 1, duration 3)

Job 2:

  task_2_0 starts at 32 (alt 0, machine 0, duration 3)

  task_2_1 starts at 100 (alt 2, machine 2, duration 3)

  task_2_2 starts at 108 (alt 0, machine 0, duration 3)

Job 3:

  task_3_0 starts at 80 (alt 2, machine 2, duration 3)

  task_3_1 starts at 92 (alt 2, machine 2, duration 3)

  task_3_2 starts at 96 (alt 1, machine 1, duration 3)

Job 4:

  task_4_0 starts at 28 (alt 2, machine 2, duration 3)

  task_4_1 starts at 56 (alt 0, machine 0, duration 3)

  task_4_2 starts at 76 (alt 0, machine 0, duration 3)

Job 5:

  task_5_0 starts at 16 (alt 2, machine 2, duration 3)

  task_5_1 starts at 60 (alt 2, machine 2, duration 3)

  task_5_2 starts at 104 (alt 1, machine 1, duration 3)

Job 6:

  task_6_0 starts at 44 (alt 1, machine 1, duration 3)

  task_6_1 starts at 56 (alt 1, machine 1, duration 3)

  task_6_2 starts at 80 (alt 0, machine 0, duration 3)

Job 7:

  task_7_0 starts at 52 (alt 0, machine 0, duration 3)

  task_7_1 starts at 68 (alt 2, machine 2, duration 3)

  task_7_2 starts at 108 (alt 1, machine 1, duration 3)

Job 8:

  task_8_0 starts at 24 (alt 2, machine 2, duration 3)

  task_8_1 starts at 76 (alt 1, machine 1, duration 3)

  task_8_2 starts at 116 (alt 0, machine 0, duration 3)

Job 9:

  task_9_0 starts at 8 (alt 1, machine 1, duration 3)

  task_9_1 starts at 88 (alt 0, machine 0, duration 3)

  task_9_2 starts at 100 (alt 0, machine 0, duration 3)

Job 10:

  task_10_0 starts at 8 (alt 0, machine 0, duration 3)

  task_10_1 starts at 12 (alt 2, machine 2, duration 3)

  task_10_2 starts at 72 (alt 2, machine 2, duration 3)

Job 11:

  task_11_0 starts at 16 (alt 0, machine 0, duration 3)

  task_11_1 starts at 32 (alt 2, machine 2, duration 3)

  task_11_2 starts at 48 (alt 2, machine 2, duration 3)

Job 12:

  task_12_0 starts at 4 (alt 1, machine 1, duration 3)

  task_12_1 starts at 16 (alt 1, machine 1, duration 3)

  task_12_2 starts at 96 (alt 2, machine 2, duration 3)

Job 13:

  task_13_0 starts at 24 (alt 0, machine 0, duration 3)

  task_13_1 starts at 36 (alt 0, machine 0, duration 3)

  task_13_2 starts at 108 (alt 2, machine 2, duration 3)

Job 14:

  task_14_0 starts at 0 (alt 0, machine 0, duration 3)

  task_14_1 starts at 44 (alt 0, machine 0, duration 3)

  task_14_2 starts at 72 (alt 0, machine 0, duration 3)

Job 15:

  task_15_0 starts at 40 (alt 1, machine 1, duration 3)

  task_15_1 starts at 48 (alt 0, machine 0, duration 3)

  task_15_2 starts at 84 (alt 2, machine 2, duration 3)

Job 16:

  task_16_0 starts at 4 (alt 0, machine 0, duration 3)

  task_16_1 starts at 8 (alt 2, machine 2, duration 3)

  task_16_2 starts at 44 (alt 2, machine 2, duration 3)

Job 17:

  task_17_0 starts at 12 (alt 0, machine 0, duration 3)

  task_17_1 starts at 104 (alt 2, machine 2, duration 3)

  task_17_2 starts at 116 (alt 1, machine 1, duration 3)

Job 18:

  task_18_0 starts at 20 (alt 0, machine 0, duration 3)

  task_18_1 starts at 100 (alt 1, machine 1, duration 3)

  task_18_2 starts at 112 (alt 2, machine 2, duration 3)

Job 19:

  task_19_0 starts at 28 (alt 1, machine 1, duration 3)

  task_19_1 starts at 72 (alt 1, machine 1, duration 3)

  task_19_2 starts at 76 (alt 2, machine 2, duration 3)

Job 20:

  task_20_0 starts at 88 (alt 2, machine 2, duration 3)

  task_20_1 starts at 92 (alt 1, machine 1, duration 3)

  task_20_2 starts at 116 (alt 2, machine 2, duration 3)

Job 21:

  task_21_0 starts at 4 (alt 2, machine 2, duration 3)

  task_21_1 starts at 12 (alt 1, machine 1, duration 3)

  task_21_2 starts at 64 (alt 2, machine 2, duration 3)

Job 22:

  task_22_0 starts at 40 (alt 2, machine 2, duration 3)

  task_22_1 starts at 104 (alt 0, machine 0, duration 3)

  task_22_2 starts at 112 (alt 0, machine 0, duration 3)

Job 23:

  task_23_0 starts at 36 (alt 2, machine 2, duration 3)

  task_23_1 starts at 52 (alt 2, machine 2, duration 3)

  task_23_2 starts at 92 (alt 0, machine 0, duration 3)

Job 24:

  task_24_0 starts at 64 (alt 0, machine 0, duration 3)

  task_24_1 starts at 84 (alt 0, machine 0, duration 3)

  task_24_2 starts at 112 (alt 1, machine 1, duration 3)

Job 25:

  task_25_0 starts at 20 (alt 2, machine 2, duration 3)

  task_25_1 starts at 24 (alt 1, machine 1, duration 3)

  task_25_2 starts at 32 (alt 1, machine 1, duration 3)

Job 26:

  task_26_0 starts at 0 (alt 1, machine 1, duration 3)

  task_26_1 starts at 40 (alt 0, machine 0, duration 3)

  task_26_2 starts at 48 (alt 1, machine 1, duration 3)

Job 27:

  task_27_0 starts at 28 (alt 0, machine 0, duration 3)

  task_27_1 starts at 36 (alt 1, machine 1, duration 3)

  task_27_2 starts at 80 (alt 1, machine 1, duration 3)

Job 28:

  task_28_0 starts at 52 (alt 1, machine 1, duration 3)

  task_28_1 starts at 88 (alt 1, machine 1, duration 3)

  task_28_2 starts at 96 (alt 0, machine 0, duration 3)

Job 29:

  task_29_0 starts at 60 (alt 1, machine 1, duration 3)

  task_29_1 starts at 68 (alt 1, machine 1, duration 3)

  task_29_2 starts at 84 (alt 1, machine 1, duration 3)

Solve status: FEASIBLE

Optimal objective value: 119

Statistics

  - conflicts : 86

  - branches  : 50400

  - wall time : 302.617698 s

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

[Xiang Chen]

Hi Olivier,

Are you using multiple workers?

The line in the log that says:

Starting sequential search at 3.30s

Is a bit sus.

[getdig...@gmail.com]

Thanks for getting back. I use the following setting for workers: "solver.num_search_workers = 8" (on a 4 core laptop with 8 logical processors)   

I started again from scratch using the example file scheduling_with_transitions_sat.py which basically is a representation of a similar problem I would like to solve however with currently only one task per job defined. This example has also been mentioned by Laurent in several posts as transition solution and added one additional task for each job (so in total two tasks per job). I experience the same problem. Over 10 jobs the model is struggling to find a solution. The model has been attached in this message.  

To be very specific I only made the following changes to the original example: 

1) I use "small_jobs" for testing (triggered by 'default=0' in Parser.add_argument in line 25)

2) I added a second task for each job in "small_jobs"

3 The number of additional jobs to test performance can be defined in a variable "additionaljobs" in line 71 

3) I changed the code "if previous_end:" in line 172 to "if previous_end is not None:" to avoid the error "NotImplementedError: Evaluating a LinearExpr instance as a Boolean is not implemented." This error was caused by having more than one task in a single job. This change is exactly similar to the code used in the original flexible jobshop example from Laurent (link)  

No other changes to the model vs. the example scheduling_with_transitions_sat.py but still having the same problem. Any further guidance would be very helpful. Many thanks in advance both!

Regards, Olivier       

Op zaterdag 19 februari 2022 om 12:38:49 UTC+1 schreef xiang10...@gmail.com:

[Laurent Perron]

mostly, it is 

solver.parameters.num_search_workers = 8

instead of 

solver.num_search_workers = 8

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--

You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/ec102a6c-e9b2-4d77-9075-41072f65b9c7n%40googlegroups.com.

[getdig...@gmail.com]

Heroes! Thanks Laurent and Xiang, this solved my problem to a large extent. The debugging process going through the code line by line was a great experience as I now fully appreciate how CPSAT works triggering many new ideas for use cases.  

One observation; using 8 workers my first solution took 25 seconds (vs. 4 seconds for Laurent). Despite only having 4 cores with 8 "logical processors" on my laptop I was very surprised to see permance significantly increasing to 5 seconds using 16 workers. With 16 workers also the total number of jobs the model can process is significantly increasing. 

I would like to further increase the number of jobs and may need to switch hardware, for instance using a Google compute engine with 16 vCPUs.

In case you have a view on an optimal hardware configuration including the optimal number of workers could you please let me know.

Regards, Olivier  

Op zaterdag 19 februari 2022 om 17:42:40 UTC+1 schreef Laurent Perron:

[Laurent Perron]

Hi, we tune for 16 workers.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

To view this discussion on the web visit https://groups.google.com/d/msgid/or-tools-discuss/55da9b9e-8d42-414e-9b3b-26abff1c415fn%40googlegroups.com.