alpar@1: /* JSSP, Job-Shop Scheduling Problem */
alpar@1: 
alpar@1: /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
alpar@1: 
alpar@1: /* The Job-Shop Scheduling Problem (JSSP) is to schedule a set of jobs
alpar@1:    on a set of machines, subject to the constraint that each machine can
alpar@1:    handle at most one job at a time and the fact that each job has a
alpar@1:    specified processing order through the machines. The objective is to
alpar@1:    schedule the jobs so as to minimize the maximum of their completion
alpar@1:    times.
alpar@1: 
alpar@1:    Reference:
alpar@1:    D. Applegate and W. Cook, "A Computational Study of the Job-Shop
alpar@1:    Scheduling Problem", ORSA J. On Comput., Vol. 3, No. 2, Spring 1991,
alpar@1:    pp. 149-156. */
alpar@1: 
alpar@1: param n, integer, > 0;
alpar@1: /* number of jobs */
alpar@1: 
alpar@1: param m, integer, > 0;
alpar@1: /* number of machines */
alpar@1: 
alpar@1: set J := 1..n;
alpar@1: /* set of jobs */
alpar@1: 
alpar@1: set M := 1..m;
alpar@1: /* set of machines */
alpar@1: 
alpar@1: param sigma{j in J, t in 1..m}, in M;
alpar@1: /* permutation of the machines, which represents the processing order
alpar@1:    of j through the machines: j must be processed first on sigma[j,1],
alpar@1:    then on sigma[j,2], etc. */
alpar@1: 
alpar@1: check{j in J, t1 in 1..m, t2 in 1..m: t1 <> t2}:
alpar@1:       sigma[j,t1] != sigma[j,t2];
alpar@1: /* sigma must be permutation */
alpar@1: 
alpar@1: param p{j in J, a in M}, >= 0;
alpar@1: /* processing time of j on a */
alpar@1: 
alpar@1: var x{j in J, a in M}, >= 0;
alpar@1: /* starting time of j on a */
alpar@1: 
alpar@1: s.t. ord{j in J, t in 2..m}:
alpar@1:       x[j, sigma[j,t]] >= x[j, sigma[j,t-1]] + p[j, sigma[j,t-1]];
alpar@1: /* j can be processed on sigma[j,t] only after it has been completely
alpar@1:    processed on sigma[j,t-1] */
alpar@1: 
alpar@1: /* The disjunctive condition that each machine can handle at most one
alpar@1:    job at a time is the following:
alpar@1: 
alpar@1:       x[i,a] >= x[j,a] + p[j,a]  or  x[j,a] >= x[i,a] + p[i,a]
alpar@1: 
alpar@1:    for all i, j in J, a in M. This condition is modeled through binary
alpar@1:    variables Y as shown below. */
alpar@1: 
alpar@1: var Y{i in J, j in J, a in M}, binary;
alpar@1: /* Y[i,j,a] is 1 if i scheduled before j on machine a, and 0 if j is
alpar@1:    scheduled before i */
alpar@1: 
alpar@1: param K := sum{j in J, a in M} p[j,a];
alpar@1: /* some large constant */
alpar@1: 
alpar@1: display K;
alpar@1: 
alpar@1: s.t. phi{i in J, j in J, a in M: i <> j}:
alpar@1:       x[i,a] >= x[j,a] + p[j,a] - K * Y[i,j,a];
alpar@1: /* x[i,a] >= x[j,a] + p[j,a] iff Y[i,j,a] is 0 */
alpar@1: 
alpar@1: s.t. psi{i in J, j in J, a in M: i <> j}:
alpar@1:       x[j,a] >= x[i,a] + p[i,a] - K * (1 - Y[i,j,a]);
alpar@1: /* x[j,a] >= x[i,a] + p[i,a] iff Y[i,j,a] is 1 */
alpar@1: 
alpar@1: var z;
alpar@1: /* so-called makespan */
alpar@1: 
alpar@1: s.t. fin{j in J}: z >= x[j, sigma[j,m]] + p[j, sigma[j,m]];
alpar@1: /* which is the maximum of the completion times of all the jobs */
alpar@1: 
alpar@1: minimize obj: z;
alpar@1: /* the objective is to make z as small as possible */
alpar@1: 
alpar@1: data;
alpar@1: 
alpar@1: /* These data correspond to the instance ft06 (mt06) from:
alpar@1: 
alpar@1:    H. Fisher, G.L. Thompson (1963), Probabilistic learning combinations
alpar@1:    of local job-shop scheduling rules, J.F. Muth, G.L. Thompson (eds.),
alpar@1:    Industrial Scheduling, Prentice Hall, Englewood Cliffs, New Jersey,
alpar@1:    225-251 */
alpar@1: 
alpar@1: /* The optimal solution is 55 */
alpar@1: 
alpar@1: param n := 6;
alpar@1: 
alpar@1: param m := 6;
alpar@1: 
alpar@1: param sigma :  1  2  3  4  5  6 :=
alpar@1:           1    3  1  2  4  6  5
alpar@1:           2    2  3  5  6  1  4
alpar@1:           3    3  4  6  1  2  5
alpar@1:           4    2  1  3  4  5  6
alpar@1:           5    3  2  5  6  1  4
alpar@1:           6    2  4  6  1  5  3 ;
alpar@1: 
alpar@1: param p     :  1  2  3  4  5  6 :=
alpar@1:           1    3  6  1  7  6  3
alpar@1:           2   10  8  5  4 10 10
alpar@1:           3    9  1  5  4  7  8
alpar@1:           4    5  5  5  3  8  9
alpar@1:           5    3  3  9  1  5  4
alpar@1:           6   10  3  1  3  4  9 ;
alpar@1: 
alpar@1: end;