Sunday, April 13, 2014

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:

image

image