lemon-project-template-glpk
view deps/glpk/examples/jssp.mod @ 9:33de93886c88
Import GLPK 4.47
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 20:59:10 +0100 |
| parents | |
| children |
line source
1 /* JSSP, Job-Shop Scheduling Problem */
3 /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
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.
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. */
17 param n, integer, > 0;
18 /* number of jobs */
20 param m, integer, > 0;
21 /* number of machines */
23 set J := 1..n;
24 /* set of jobs */
26 set M := 1..m;
27 /* set of machines */
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. */
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 */
38 param p{j in J, a in M}, >= 0;
39 /* processing time of j on a */
41 var x{j in J, a in M}, >= 0;
42 /* starting time of j on a */
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] */
49 /* The disjunctive condition that each machine can handle at most one
50 job at a time is the following:
52 x[i,a] >= x[j,a] + p[j,a] or x[j,a] >= x[i,a] + p[i,a]
54 for all i, j in J, a in M. This condition is modeled through binary
55 variables Y as shown below. */
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 */
61 param K := sum{j in J, a in M} p[j,a];
62 /* some large constant */
64 display K;
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 */
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 */
74 var z;
75 /* so-called makespan */
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 */
80 minimize obj: z;
81 /* the objective is to make z as small as possible */
83 data;
85 /* These data correspond to the instance ft06 (mt06) from:
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 */
92 /* The optimal solution is 55 */
94 param n := 6;
96 param m := 6;
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 ;
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 ;
114 end;