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<j) (      forall (ti in Stages, tj in Stages              where MachineNumbers[i,ti]=MachineNumbers[j,tj]) (         Start[i,ti] >= 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:

• https://github.com/MiniZinc/minizinc-benchmarks/blob/master/jobshop/jobshop.mzn
• https://github.com/hakank/hakank/blob/master/minizinc/jobshop.mzn

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.
3. Can we set a time limit and then get the best solution so far?