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';