[9] | 1 | /* JSSP, Job-Shop Scheduling Problem */ |
---|
| 2 | |
---|
| 3 | /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */ |
---|
| 4 | |
---|
| 5 | /* The Job-Shop Scheduling Problem (JSSP) is to schedule a set of jobs |
---|
| 6 | on a set of machines, subject to the constraint that each machine can |
---|
| 7 | handle at most one job at a time and the fact that each job has a |
---|
| 8 | specified processing order through the machines. The objective is to |
---|
| 9 | schedule the jobs so as to minimize the maximum of their completion |
---|
| 10 | times. |
---|
| 11 | |
---|
| 12 | Reference: |
---|
| 13 | D. Applegate and W. Cook, "A Computational Study of the Job-Shop |
---|
| 14 | Scheduling Problem", ORSA J. On Comput., Vol. 3, No. 2, Spring 1991, |
---|
| 15 | pp. 149-156. */ |
---|
| 16 | |
---|
| 17 | param n, integer, > 0; |
---|
| 18 | /* number of jobs */ |
---|
| 19 | |
---|
| 20 | param m, integer, > 0; |
---|
| 21 | /* number of machines */ |
---|
| 22 | |
---|
| 23 | set J := 1..n; |
---|
| 24 | /* set of jobs */ |
---|
| 25 | |
---|
| 26 | set M := 1..m; |
---|
| 27 | /* set of machines */ |
---|
| 28 | |
---|
| 29 | param sigma{j in J, t in 1..m}, in M; |
---|
| 30 | /* permutation of the machines, which represents the processing order |
---|
| 31 | of j through the machines: j must be processed first on sigma[j,1], |
---|
| 32 | then on sigma[j,2], etc. */ |
---|
| 33 | |
---|
| 34 | check{j in J, t1 in 1..m, t2 in 1..m: t1 <> t2}: |
---|
| 35 | sigma[j,t1] != sigma[j,t2]; |
---|
| 36 | /* sigma must be permutation */ |
---|
| 37 | |
---|
| 38 | param p{j in J, a in M}, >= 0; |
---|
| 39 | /* processing time of j on a */ |
---|
| 40 | |
---|
| 41 | var x{j in J, a in M}, >= 0; |
---|
| 42 | /* starting time of j on a */ |
---|
| 43 | |
---|
| 44 | s.t. ord{j in J, t in 2..m}: |
---|
| 45 | x[j, sigma[j,t]] >= x[j, sigma[j,t-1]] + p[j, sigma[j,t-1]]; |
---|
| 46 | /* j can be processed on sigma[j,t] only after it has been completely |
---|
| 47 | processed on sigma[j,t-1] */ |
---|
| 48 | |
---|
| 49 | /* The disjunctive condition that each machine can handle at most one |
---|
| 50 | job at a time is the following: |
---|
| 51 | |
---|
| 52 | x[i,a] >= x[j,a] + p[j,a] or x[j,a] >= x[i,a] + p[i,a] |
---|
| 53 | |
---|
| 54 | for all i, j in J, a in M. This condition is modeled through binary |
---|
| 55 | variables Y as shown below. */ |
---|
| 56 | |
---|
| 57 | var Y{i in J, j in J, a in M}, binary; |
---|
| 58 | /* Y[i,j,a] is 1 if i scheduled before j on machine a, and 0 if j is |
---|
| 59 | scheduled before i */ |
---|
| 60 | |
---|
| 61 | param K := sum{j in J, a in M} p[j,a]; |
---|
| 62 | /* some large constant */ |
---|
| 63 | |
---|
| 64 | display K; |
---|
| 65 | |
---|
| 66 | s.t. phi{i in J, j in J, a in M: i <> j}: |
---|
| 67 | x[i,a] >= x[j,a] + p[j,a] - K * Y[i,j,a]; |
---|
| 68 | /* x[i,a] >= x[j,a] + p[j,a] iff Y[i,j,a] is 0 */ |
---|
| 69 | |
---|
| 70 | s.t. psi{i in J, j in J, a in M: i <> j}: |
---|
| 71 | x[j,a] >= x[i,a] + p[i,a] - K * (1 - Y[i,j,a]); |
---|
| 72 | /* x[j,a] >= x[i,a] + p[i,a] iff Y[i,j,a] is 1 */ |
---|
| 73 | |
---|
| 74 | var z; |
---|
| 75 | /* so-called makespan */ |
---|
| 76 | |
---|
| 77 | s.t. fin{j in J}: z >= x[j, sigma[j,m]] + p[j, sigma[j,m]]; |
---|
| 78 | /* which is the maximum of the completion times of all the jobs */ |
---|
| 79 | |
---|
| 80 | minimize obj: z; |
---|
| 81 | /* the objective is to make z as small as possible */ |
---|
| 82 | |
---|
| 83 | data; |
---|
| 84 | |
---|
| 85 | /* These data correspond to the instance ft06 (mt06) from: |
---|
| 86 | |
---|
| 87 | H. Fisher, G.L. Thompson (1963), Probabilistic learning combinations |
---|
| 88 | of local job-shop scheduling rules, J.F. Muth, G.L. Thompson (eds.), |
---|
| 89 | Industrial Scheduling, Prentice Hall, Englewood Cliffs, New Jersey, |
---|
| 90 | 225-251 */ |
---|
| 91 | |
---|
| 92 | /* The optimal solution is 55 */ |
---|
| 93 | |
---|
| 94 | param n := 6; |
---|
| 95 | |
---|
| 96 | param m := 6; |
---|
| 97 | |
---|
| 98 | param sigma : 1 2 3 4 5 6 := |
---|
| 99 | 1 3 1 2 4 6 5 |
---|
| 100 | 2 2 3 5 6 1 4 |
---|
| 101 | 3 3 4 6 1 2 5 |
---|
| 102 | 4 2 1 3 4 5 6 |
---|
| 103 | 5 3 2 5 6 1 4 |
---|
| 104 | 6 2 4 6 1 5 3 ; |
---|
| 105 | |
---|
| 106 | param p : 1 2 3 4 5 6 := |
---|
| 107 | 1 3 6 1 7 6 3 |
---|
| 108 | 2 10 8 5 4 10 10 |
---|
| 109 | 3 9 1 5 4 7 8 |
---|
| 110 | 4 5 5 5 3 8 9 |
---|
| 111 | 5 3 3 9 1 5 4 |
---|
| 112 | 6 10 3 1 3 4 9 ; |
---|
| 113 | |
---|
| 114 | end; |
---|