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