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;