Playing with job shop problem ft10 (3)

To see how the two different formulations mentioned in http://yetanothermathprogrammingconsultant.blogspot.com/2014/04/playing-with-job-shop-problem-ft10-2.html compare we use a real small example: ft06. Here are the models:

Original formulation with OR constraints: ft06.mzn

int: numjobs = 6; int: numstages = 6; set of int: Jobs = 1..numjobs; set of int: Stages = 1..numstages; array[Jobs,Stages] of int: ProcTimes = [| 1,     3,     6,     7,     3,     6,   | 8,     5,    10,    10,    10,     4,   | 5,     4,     8,     9,     1,     7,   | 5,     5,     5,     3,     8,     9,   | 9,     3,     5,     4,     3,     1,   | 3,     3,     9,    10,     4,     1 |]; array[Jobs,Stages] of int: Machine = [| 2,   0,   1,   3,   5,   4,   | 1,   2,   4,   5,   0,   3,   | 2,   3,   5,   0,   1,   4,   | 1,   0,   2,   3,   4,   5,   | 2,   1,   4,   5,   0,   3,   | 1,   3,   5,   0,   4,   2 |]; int: horizon = sum([ ProcTimes[j,s] | j in Jobs, s in Stages]); array[Jobs,Stages] of var 0..horizon: Start; var 0..horizon: 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 (i in Jobs, j in Jobs where i<j) (      forall (ti in Stages, tj in Stages              where Machine[i,ti]=Machine[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; output ["makespan:",show(makespan),"\n",show(Start)]

Formulation with cumulative constraint: ft06c.mzn

include "globals.mzn"; int: numjobs = 6; int: numstages = 6; int: nummachines = 6; 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 = [| 1,     3,     6,     7,     3,     6,   | 8,     5,    10,    10,    10,     4,   | 5,     4,     8,     9,     1,     7,   | 5,     5,     5,     3,     8,     9,   | 9,     3,     5,     4,     3,     1,   | 3,     3,     9,    10,     4,     1 |]; array[Jobs,Stages] of Machines: Machine = [| 2,   0,   1,   3,   5,   4,   | 1,   2,   4,   5,   0,   3,   | 2,   3,   5,   0,   1,   4,   | 1,   0,   2,   3,   4,   5,   | 2,   1,   4,   5,   0,   3,   | 1,   3,   5,   0,   4,   2 |]; int: horizon = sum([ ProcTimes[j,s] | j in Jobs, s in Stages]); array[Jobs,Stages] of var 0..horizon: Start; var 0..horizon: 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] ); solve minimize makespan; output ["makespan:",show(makespan),"\n",show(Start)]

Comparison

Solution time in seconds

Solver	or ft06.mzn	cumulative ft06c.mnz	Command line
g12fd	0.3	0.2	mzn-g12fd –s ft06.mzn
g12lazy	0.2	6.5	mzn-g12lazy -s ft06.mzn
gecode	0.1	0.1	mzn-gecode -s ft06.mzn
or-tools	147	0.1	minizinc -G or-tools -f \tmp\fz.exe ft06.mzn

Gecode and or-tools show some statistics for these case: