1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/examples/jssp.mod	Sun Nov 06 20:59:10 2011 +0100
     1.3 @@ -0,0 +1,114 @@
     1.4 +/* JSSP, Job-Shop Scheduling Problem */
     1.5 +
     1.6 +/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
     1.7 +
     1.8 +/* The Job-Shop Scheduling Problem (JSSP) is to schedule a set of jobs
     1.9 +   on a set of machines, subject to the constraint that each machine can
    1.10 +   handle at most one job at a time and the fact that each job has a
    1.11 +   specified processing order through the machines. The objective is to
    1.12 +   schedule the jobs so as to minimize the maximum of their completion
    1.13 +   times.
    1.14 +
    1.15 +   Reference:
    1.16 +   D. Applegate and W. Cook, "A Computational Study of the Job-Shop
    1.17 +   Scheduling Problem", ORSA J. On Comput., Vol. 3, No. 2, Spring 1991,
    1.18 +   pp. 149-156. */
    1.19 +
    1.20 +param n, integer, > 0;
    1.21 +/* number of jobs */
    1.22 +
    1.23 +param m, integer, > 0;
    1.24 +/* number of machines */
    1.25 +
    1.26 +set J := 1..n;
    1.27 +/* set of jobs */
    1.28 +
    1.29 +set M := 1..m;
    1.30 +/* set of machines */
    1.31 +
    1.32 +param sigma{j in J, t in 1..m}, in M;
    1.33 +/* permutation of the machines, which represents the processing order
    1.34 +   of j through the machines: j must be processed first on sigma[j,1],
    1.35 +   then on sigma[j,2], etc. */
    1.36 +
    1.37 +check{j in J, t1 in 1..m, t2 in 1..m: t1 <> t2}:
    1.38 +      sigma[j,t1] != sigma[j,t2];
    1.39 +/* sigma must be permutation */
    1.40 +
    1.41 +param p{j in J, a in M}, >= 0;
    1.42 +/* processing time of j on a */
    1.43 +
    1.44 +var x{j in J, a in M}, >= 0;
    1.45 +/* starting time of j on a */
    1.46 +
    1.47 +s.t. ord{j in J, t in 2..m}:
    1.48 +      x[j, sigma[j,t]] >= x[j, sigma[j,t-1]] + p[j, sigma[j,t-1]];
    1.49 +/* j can be processed on sigma[j,t] only after it has been completely
    1.50 +   processed on sigma[j,t-1] */
    1.51 +
    1.52 +/* The disjunctive condition that each machine can handle at most one
    1.53 +   job at a time is the following:
    1.54 +
    1.55 +      x[i,a] >= x[j,a] + p[j,a]  or  x[j,a] >= x[i,a] + p[i,a]
    1.56 +
    1.57 +   for all i, j in J, a in M. This condition is modeled through binary
    1.58 +   variables Y as shown below. */
    1.59 +
    1.60 +var Y{i in J, j in J, a in M}, binary;
    1.61 +/* Y[i,j,a] is 1 if i scheduled before j on machine a, and 0 if j is
    1.62 +   scheduled before i */
    1.63 +
    1.64 +param K := sum{j in J, a in M} p[j,a];
    1.65 +/* some large constant */
    1.66 +
    1.67 +display K;
    1.68 +
    1.69 +s.t. phi{i in J, j in J, a in M: i <> j}:
    1.70 +      x[i,a] >= x[j,a] + p[j,a] - K * Y[i,j,a];
    1.71 +/* x[i,a] >= x[j,a] + p[j,a] iff Y[i,j,a] is 0 */
    1.72 +
    1.73 +s.t. psi{i in J, j in J, a in M: i <> j}:
    1.74 +      x[j,a] >= x[i,a] + p[i,a] - K * (1 - Y[i,j,a]);
    1.75 +/* x[j,a] >= x[i,a] + p[i,a] iff Y[i,j,a] is 1 */
    1.76 +
    1.77 +var z;
    1.78 +/* so-called makespan */
    1.79 +
    1.80 +s.t. fin{j in J}: z >= x[j, sigma[j,m]] + p[j, sigma[j,m]];
    1.81 +/* which is the maximum of the completion times of all the jobs */
    1.82 +
    1.83 +minimize obj: z;
    1.84 +/* the objective is to make z as small as possible */
    1.85 +
    1.86 +data;
    1.87 +
    1.88 +/* These data correspond to the instance ft06 (mt06) from:
    1.89 +
    1.90 +   H. Fisher, G.L. Thompson (1963), Probabilistic learning combinations
    1.91 +   of local job-shop scheduling rules, J.F. Muth, G.L. Thompson (eds.),
    1.92 +   Industrial Scheduling, Prentice Hall, Englewood Cliffs, New Jersey,
    1.93 +   225-251 */
    1.94 +
    1.95 +/* The optimal solution is 55 */
    1.96 +
    1.97 +param n := 6;
    1.98 +
    1.99 +param m := 6;
   1.100 +
   1.101 +param sigma :  1  2  3  4  5  6 :=
   1.102 +          1    3  1  2  4  6  5
   1.103 +          2    2  3  5  6  1  4
   1.104 +          3    3  4  6  1  2  5
   1.105 +          4    2  1  3  4  5  6
   1.106 +          5    3  2  5  6  1  4
   1.107 +          6    2  4  6  1  5  3 ;
   1.108 +
   1.109 +param p     :  1  2  3  4  5  6 :=
   1.110 +          1    3  6  1  7  6  3
   1.111 +          2   10  8  5  4 10 10
   1.112 +          3    9  1  5  4  7  8
   1.113 +          4    5  5  5  3  8  9
   1.114 +          5    3  3  9  1  5  4
   1.115 +          6   10  3  1  3  4  9 ;
   1.116 +
   1.117 +end;