makespan.gms : Job scheduling with three datasets - Minimize the makespan

Description

This model solves a job shop scheduling problem using EMP's disjunction
reformulation. The problem which has a set of jobs (j) which must be processed
in a sequence of stages (s). Yet, not all jobs require all stages. A zero wait
transfer policy is assumed between the stages (once a job has started it cannot
be interrupted). To obtain a feasible solution it is necessary to eliminate all
clashes between jobs. It requires that no two jobs are performed at any stage
at any time. The objective is to minimize the makespan, the time to complete
all jobs.

This model includes data sets 1, 6 and 9 which can be reset. E.g.
gams makespan --example=6

References:
Raman & Grossmann, Computers and Chemical Engineering 18, 7, p.563-578, 1994.
Aldo Vecchietti, LogMIP User's Manual, http://www.logmip.ceride.gov.ar/ 2007

Contributor: Alex Meeraus, January 2009


Small Model of Type : LOGICAL


Category : GAMS EMP library


Main file : makespan.gms

$title Job scheduling with three datasets - Minimize the makespan (MAKESPAN,SEQ=15)

$onText
This model solves a job shop scheduling problem using EMP's disjunction
reformulation. The problem which has a set of jobs (j) which must be processed
in a sequence of stages (s). Yet, not all jobs require all stages. A zero wait
transfer policy is assumed between the stages (once a job has started it cannot
be interrupted). To obtain a feasible solution it is necessary to eliminate all
clashes between jobs. It requires that no two jobs are performed at any stage
at any time. The objective is to minimize the makespan, the time to complete
all jobs.

This model includes data sets 1, 6 and 9 which can be reset. E.g.
gams makespan --example=6

References:
Raman & Grossmann, Computers and Chemical Engineering 18, 7, p.563-578, 1994.
Aldo Vecchietti, LogMIP User's Manual, http://www.logmip.ceride.gov.ar/ 2007

Contributor: Alex Meeraus, January 2009

$offText

$if NOT set example $ set example 1

sets j jobs
     s stages
     lt(j,j) upper triangle

alias (j,jj),(s,ss);

parameters w(j,jj) maximum pairwise waiting time
           pt(j)   total processing time;

variables t       completion time
          x(j)    job starting time

positive variable x; binary variable y;

equations comp(j)   job completion time
          seq(j,jj) job sequencing j beore jj ;

comp(j).. t =g= x(j) + pt(j);

seq(j,jj)$(not sameas(j,jj))..  x(j) + w(j,jj) =l= x(jj);

model m / all /;

* now will enter data for different examples 1,6 or 9 only
$ifThen %example% == 1

* data for example 1 - 3 jobs and 3 stages

sets j jobs / A, B, C /, s stages / 1*3 /
table p(j,s) processing time
    1   2   3
 A  5       3
 B      3   2
 C  2   4

scalar optval / 11 /;
$elseIf %example% == 6

* data for example 6  - 7 jobs and 5 stages

sets j jobs / A, B, C, D, E, F, G /, s stages / 1*5 /
table p(j,s) processing time
       1       2       3       4       5
A      3               5               2
B              3       4               3
C      6       3               6
D              8       5       1
E              4       6               2
F      2               5       7
G              8               5       4

scalar optval / 36 /;
$elseIf %example% == 9

* data for example 9 - 5 jobs and 5 stages

sets j jobs / A, B, C, D, E /, s stages / 1*5 /
table p(j,s) processing time
       1       2       3       4       5
A      2       6       5       7       3
B      5       2       4       5       4
C      4       8       2       8       3
D      3       3       5       6       4
E      5       4       3       5       5

scalar optval / 46 /;
$else
$abort 'example has to be 1,6 or 9 but was --example=%example%'
$endIf

* complete data preparation
parameter c(j,s)  stage completion time;

lt(j,jj) = ord(j) < ord(jj);

c(j,s)  = sum(ss$(ord(ss)<=ord(s)), p(j,ss));
w(j,jj) = smax(s, c(j,s) - c(jj,s-1));
pt(j)   = sum(s, p(j,s));

display c,w,pt;

file emp / '%emp.info%' /; put emp '* problem %gams.i%';
loop(lt(j,jj),
   put / 'disjunction *' seq(j,jj) 'else' seq(jj,j));
putclose;

option limcol=0,limrow=0,optcr=0;
solve m using EMP minimizing t;
abort$(abs(m.objval-optval) > 1e-6) 'we did not get the correct solution';