|
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; |