## Sunday, April 13, 2014

### Playing with job shop problem ft10 (2)

How would a Constraint Programming formulation do on this problem: http://yetanothermathprogrammingconsultant.blogspot.com/2014/04/playing-with-ft10-job-shop-1.html. A straightforward translation of the MIP formulation into Minizinc can look like:

 int: numjobs = 10; int: numstages = 10; set of int: Jobs = 1..numjobs; set of int: Stages = 1..numstages; array[Jobs,Stages] of int: ProcTimes = [| 29, 78,  9, 36, 49, 11, 62, 56, 44, 21,   | 43, 90, 75, 11, 69, 28, 46, 46, 72, 30,   | 91, 85, 39, 74, 90, 10, 12, 89, 45, 33,   | 81, 95, 71, 99,  9, 52, 85, 98, 22, 43,   | 14,  6, 22, 61, 26, 69, 21, 49, 72, 53,   | 84,  2, 52, 95, 48, 72, 47, 65,  6, 25,   | 46, 37, 61, 13, 32, 21, 32, 89, 30, 55,   | 31, 86, 46, 74, 32, 88, 19, 48, 36, 79,   | 76, 69, 76, 51, 85, 11, 40, 89, 26, 74,   | 85, 13, 61,  7, 64, 76, 47, 52, 90, 45 |]; array[Jobs,Stages] of int: MachineNumbers = [|  0, 1, 2, 3, 4, 5, 6, 7, 8, 9,   |  0, 2, 4, 9, 3, 1, 6, 5, 7, 8,   |  1, 0, 3, 2, 8, 5, 7, 6, 9, 4,   |  1, 2, 0, 4, 6, 8, 7, 3, 9, 5,   |  2, 0, 1, 5, 3, 4, 8, 7, 9, 6,   |  2, 1, 5, 3, 8, 9, 0, 6, 4, 7,   |  1, 0, 3, 2, 6, 5, 9, 8, 7, 4,   |  2, 0, 1, 5, 4, 6, 8, 9, 7, 3,   |  0, 1, 3, 5, 2, 9, 6, 7, 4, 8,   |  1, 0, 2, 6, 8, 9, 5, 3, 4, 7 |]; int: horizon = sum([ ProcTimes[j,s] | j in Jobs, s in Stages]); array[Jobs,Stages] of var 0..horizon: Start; var 0..horizon: makespan; % positive variables constraint    forall (j in Jobs) (       Start[j,1]>=0    ); % order constraint    forall (j in Jobs, t in 1..numstages-1) (       Start[j,t+1] >= Start[j,t] + ProcTimes[j,t]    ); % no overlap constraint    forall (i in Jobs, j in Jobs where i= Start[j,tj] + ProcTimes[j,tj] \/         Start[j,tj] >= Start[i,ti] + ProcTimes[i,ti] )      ); constraint    makespan =     max( [ Start[j,numstages] + ProcTimes[j,numstages] | j in Jobs] ); solve minimize makespan;

This looks actually quite nice. We can drop the binary variables that deal with the overlap, and the objective is more intuitive. As most CP solvers don’t deal very well or not at all with continuous variables, we used integer variables. This is ok here as we deal with integer valued processing times. In the real world you may need to rescale and/or approximate these numbers. Unfortunately this model does not solve. I am looking at the cursor and don’t see any feedback about any progress:

There is an alternative formulation that is often much better: replace the no overlap constraints by a global constraint called cumulative. Not totally intuitive but we can translate the model quite easily. In addition we added some bounds on all variables:

 include "globals.mzn"; int: numjobs = 10; int: numstages = 10; int: nummachines = 10; set of int: Jobs = 1..numjobs; set of int: Stages = 1..numstages; set of int: Machines = 0..nummachines-1; array[Jobs,Stages] of int: ProcTimes = [| 29, 78,  9, 36, 49, 11, 62, 56, 44, 21,   | 43, 90, 75, 11, 69, 28, 46, 46, 72, 30,   | 91, 85, 39, 74, 90, 10, 12, 89, 45, 33,   | 81, 95, 71, 99,  9, 52, 85, 98, 22, 43,   | 14,  6, 22, 61, 26, 69, 21, 49, 72, 53,   | 84,  2, 52, 95, 48, 72, 47, 65,  6, 25,   | 46, 37, 61, 13, 32, 21, 32, 89, 30, 55,   | 31, 86, 46, 74, 32, 88, 19, 48, 36, 79,   | 76, 69, 76, 51, 85, 11, 40, 89, 26, 74,   | 85, 13, 61,  7, 64, 76, 47, 52, 90, 45 |]; array[Jobs,Stages] of int: Machine = [|  0, 1, 2, 3, 4, 5, 6, 7, 8, 9,   |  0, 2, 4, 9, 3, 1, 6, 5, 7, 8,   |  1, 0, 3, 2, 8, 5, 7, 6, 9, 4,   |  1, 2, 0, 4, 6, 8, 7, 3, 9, 5,   |  2, 0, 1, 5, 3, 4, 8, 7, 9, 6,   |  2, 1, 5, 3, 8, 9, 0, 6, 4, 7,   |  1, 0, 3, 2, 6, 5, 9, 8, 7, 4,   |  2, 0, 1, 5, 4, 6, 8, 9, 7, 3,   |  0, 1, 3, 5, 2, 9, 6, 7, 4, 8,   |  1, 0, 2, 6, 8, 9, 5, 3, 4, 7 |]; int: last_end = sum([ ProcTimes[j,s] | j in Jobs, s in Stages]); int: last_start = last_end - min([ ProcTimes[j,numstages] | j in Jobs ]); array[Jobs,Stages] of var 0..last_start: Start; var 0..last_end: makespan; % order constraint    forall (j in Jobs, t in 1..numstages-1) (       Start[j,t+1] >= Start[j,t] + ProcTimes[j,t]    ); % no overlap constraint    forall (m in Machines) (        cumulative([ Start[j,t]     | j in Jobs, t in Stages where Machine[j,t]=m ],                   [ ProcTimes[j,t] | j in Jobs, t in Stages where Machine[j,t]=m ],                   [ 1              | j in Jobs, t in Stages where Machine[j,t]=m ],                   1)    ); constraint    makespan =     max( [ Start[j,numstages] + ProcTimes[j,numstages] | j in Jobs] ); % helper constraint    forall (j in Jobs, t in 1..numstages-1) (       Start[j,t+1] >= sum([ProcTimes[j, tt] | tt in 1..t])    ); solve minimize makespan;

Unfortunately still just a blinking cursor…

Any better Minizinc formulation available? Here are some alternative formulations which I have not tried out:

Some questions:

1. No log when solving the models? One would like to see some progress log.
2. How to debug models? Something like a limrow/limcol in GAMS or expand in AMPL? One could look at the “flatzinc” output, but that is difficult to digest.

1. Hi Erwin.

1) Logging: If you put an output section you see some progress, i.e. the intermittent solutions. Example:

output
[
"makespan: " ++ show(makespan) ++ "\n"
]
++
[
if s = 1 then "\n" else " " endif ++
show(Start[j,s])
| j in Jobs, s in Stages
];

2. For debugging models I tend to use "trace(show(....), true)" for showing indices etc. However, inferred domains etc are not shown.

3. Time limit: For fzn-gecode, the time limit is set with "-time millis". I run your model like this (on my Linux) with a time limit of 10s
\$ minizinc -v -G gecode ft10.mzn -f "/home/hakank/gecode/svn/trunk/tools/flatzinc/fzn-gecode -a -mode stat -time 10000"
After 10s some statistics is shown.

Also, you should probably experiment with search strategies, for example (instead of "solve minimize makespan"):
solve :: int_search([Start[j,s] | j in Jobs, s in Stages ], first_fail, indomain_split, complete) minimize makespan;

This finds a makespan of 1110 fast, but then it's stuck.

I don't think my model (jobshop.mzn) is much faster.

/hakank

1. Thanks. for that info!