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<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:

image

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