# source:glpk-cmake/examples/jssp.mod@1:c445c931472f

Last change on this file since 1:c445c931472f was 1:c445c931472f, checked in by Alpar Juttner <alpar@…>, 10 years ago

Import glpk-4.45

• Generated files and doc/notes are removed
File size: 3.2 KB
Line
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
17param n, integer, > 0;
18/* number of jobs */
19
20param m, integer, > 0;
21/* number of machines */
22
23set J := 1..n;
24/* set of jobs */
25
26set M := 1..m;
27/* set of machines */
28
29param 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
34check{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
38param p{j in J, a in M}, >= 0;
39/* processing time of j on a */
40
41var x{j in J, a in M}, >= 0;
42/* starting time of j on a */
43
44s.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
57var 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
61param K := sum{j in J, a in M} p[j,a];
62/* some large constant */
63
64display K;
65
66s.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
70s.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
74var z;
75/* so-called makespan */
76
77s.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
80minimize obj: z;
81/* the objective is to make z as small as possible */
82
83data;
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
94param n := 6;
95
96param m := 6;
97
98param 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
106param 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
114end;
Note: See TracBrowser for help on using the repository browser.