Version:

sequence.gms : Sequencing on a single machine

**Description**

A set of tasks is to be processed on a single machine. The execution of the tasks is non-preemptive (ie cannot be interrupted). For every task i its release date, duration and due date are given. What is the sequence that minimizes the maximum tardiness? Reference: Applications of optimization with Xpress-MP (Last update 10 September, 2007) 7.4 Sequencing jobs on a bottleneck machine, pp 94-97 This model shows how to use different reformulations (BigM, Convex Hull and Indicators) through EMP without any change to the model itself. Contributor: Michael Ferris and Jan-H. Jagla, April 2009

**Small Model of Type : ** LOGICAL

**Category :** GAMS EMP library

**Main file :** sequence.gms

```
$title Sequencing on a single machine (SEQUENCE, SEQ=20)
$ontext
A set of tasks is to be processed on a single machine.
The execution of the tasks is non-preemptive (ie cannot be interrupted).
For every task i its release date, duration and due date are given.
What is the sequence that minimizes the maximum tardiness?
Reference:
Applications of optimization with Xpress-MP (Last update 10 September, 2007)
7.4 Sequencing jobs on a bottleneck machine, pp 94-97
This model shows how to use different reformulations (BigM, Convex Hull and
Indicators) through EMP without any change to the model itself.
Contributor: Michael Ferris and Jan-H. Jagla, April 2009
$offtext
set job / 1*7 /;
set times /release,duration,due/;
table data(times,job)
1 2 3 4 5 6 7
release 2 5 4 8 9
duration 5 6 8 4 2 4 2
due 10 21 15 10 5 15 22
;
alias (job,i,j);
binary variables order(i,j) "i must be ordered before j";
positive variables start(j) "start time of job j";
positive variables comp(j) "completion time of job j";
positive variables late(j) "lateness of job j";
variable tardiness;
equations
defcomp(j),deflate(j), deftard(j);
defcomp(j)..
comp(j) =e= start(j) + data('duration',j);
* This is really max(0, comp(j) - data('due',j))
deflate(j)..
late(j) =g= comp(j) - data('due',j);
deftard(j)..
tardiness =g= late(j);
model base /all/;
*--- BigM Formulation
scalar M; M = sum(job, data('release',job) + data('duration',job));
equations
disjoint1(i,j), disjoint2(i,j);
* The following are either-or constraints, do paper i or paper j
disjoint1(i,j)$(ord(i) lt ord(j))..
comp(i) =l= start(j) + M*(1-order(i,j));
disjoint2(i,j)$(ord(i) lt ord(j))..
comp(j) =l= start(i) + M*order(i,j);
model sequence /base, disjoint1, disjoint2/;
sequence.optcr = 0;
start.lo(j) = max(0, data('release',j));
solve sequence using mip min tardiness;
*--- EMP Formulation facilitating using Bigm, ConvexHull or Indicators
equations
seq(i,j);
model sequence_emp /base, seq/;
sequence_emp.optcr = 0;
* The following are either-or constraints, do paper i or paper j
seq(i,j)$(not sameas(i,j))..
comp(i) =l= start(j);
file emp / '%emp.info%' /
empopt / 'jams.opt' /;
sequence_emp.optfile=1;
scalar ll; ll= LicenseLevel;
*--- EMP Convex Hull (default)
* resulting model requires license
if(ll>0,
loop((i,j)$(ord(i) < ord(j)),
put emp / 'disjunction *' seq(i,j) 'else' seq(j,i));
putclose emp;
putclose empopt / 'FileName convexhull.gms';
solve sequence_emp using emp min tardiness;
abort$(abs(sequence_emp.objval - sequence.objval) > 1e-10) 'EMP Convex Hull: Incorrect solution', sequence_emp.objval, sequence.objval;
);
*--- EMP BigM
put emp / 'default bigm' M:0:0;
loop((i,j)$(ord(i) < ord(j)),
put emp / 'disjunction *' seq(i,j) 'else' seq(j,i));
putclose emp;
putclose empopt / 'FileName bigm.gms';
solve sequence_emp using emp min tardiness;
abort$(abs(sequence_emp.objval - sequence.objval) > 1e-10) 'EMP BigM: Incorrect solution', sequence_emp.objval, sequence.objval;
*--- EMP Indicators (CPLEX, XPRESS and SCIP only)
$if NOT SOLVER cplex $exit
put emp / 'default indic';
loop((i,j)$(ord(i) < ord(j)),
put emp / 'disjunction *' seq(i,j) 'else' seq(j,i));
putclose emp;
putclose empopt / 'FileName indicators.gms'
/ 'SubSolver cplex';
solve sequence_emp using emp min tardiness;
abort$(abs(sequence_emp.objval - sequence.objval) > 1e-10) 'EMP Indicators: Incorrect solution', sequence_emp.objval, sequence.objval;
*--- with EMP one can also mix & match different reformulation types
*--- and change the parameters used by the reformulation
put emp / 'default indic';
loop((i,j)$(ord(i) < ord(j) and ord(i) < card(i) and ord(j) < card(j)),
put emp / 'disjunction *' seq(i,j) 'else' seq(j,i));
loop((i,j)$(ord(i) < ord(j) and (ord(i) < card(i)/2 and ord(j) = card(j))),
put emp / 'disjunction bigm' M:0:0 '*' seq(i,j) 'else' seq(j,i));
loop((i,j)$(ord(i) < ord(j) and (ord(i) >= card(i)/2 and ord(j) = card(j))),
put emp / 'disjunction chull 4000 *' seq(i,j) 'else' seq(j,i));
putclose emp;
putclose empopt / 'FileName mixandmatch.gms'
/ 'SubSolver cplex';
solve sequence_emp using emp min tardiness;
abort$(abs(sequence_emp.objval - sequence.objval) > 1e-10) 'EMP Mix & Match: Incorrect solution', sequence_emp.objval, sequence.objval;
```