multi-machine job shop scheduling

GAMS
1 
Sets

i  'designs'                       /1*37/
j  'operations for each design'    /1*96/
k  'machines'                      /1*3/

;

Scalar

M  'a large positive number'   /100000/

;

Table

P(i,k) 'standard time to design i'


           1           2          3
1        18.2        18.2        6.1
2        13.2        13.2        4.4
3        13.1        13.1        4.4
4        19.0        19.0        6.3
5        10.0        10.0        3.3
6        13.1        13.1        4.4
7        9.0         9.0         3.0
8        5.0         5.0         1.7
9        12.3        12.3        4.1
10       10.4        10.4        3.5
11       10.0        10.0        3.3
12       18.2        18.2        6.1
13       15.6        15.6        5.2
14       15.6        15.6        5.2
15       13.0        13.0        4.3
16       17.0        17.0        5.7
17       13.8        13.8        4.6
18       12.7        12.7        4.2
19       9.0         9.0         3.0
20       12.3        12.3        4.1
21       12.8        12.8        4.3
22       12.8        12.8        4.3
23       6.5         6.5         2.2
24       2.5         2.5         0.8
25       11.9        11.9        4.0
26       13.1        13.1        4.4
27       14.0        14.0        4.7
28       15.8        15.8        5.3
29       12.5        12.5        4.2
30       4.0         4.0         1.3
31       6.8         6.8         2.3
32       2.6         2.6         0.9
33       6.0         6.0         2.0
34       3.0         3.0         1.0
35       18.9        18.9        6.3
36       5.0         5.0         1.7
37       10.4        10.4        3.5



;


Binary Variable

X(i,j,k)    '1 if jth is processed on machine k, 0 else'

;

Variables

Z           'Objective'

;


Positive Variables

Cmax

Tm(k)  'start of working time for machine k'

t(i,j) 'starting time of j'


;

Equations

E1  'each operation belonged to a design should be assigned to only one available machine'

E2  'defining the operations on machine sets'

E3  'the precedence relationships should be between the operation starting times'

E4  'an operation can be assigned to one position of a machine when the machine is idle'

E5  'an operation can be assigned to one position of a machine when the machine is idle'

E6  'determining the makespan of operations by considering last completed time for all operations'


Objective 'minimizing makespan'

;


Objective.. Z =e= Cmax;

E1(i,j)..  sum(k, X(i,j,k)) =e= 1;

E2(k)..  sum(i, sum(j, X(i,j,k))) =l= 1;

E3(i,j).. t(i,j+1) =g= t(i,j) +  sum(k, X(i,j,k) * P(i,k));

E4(i,j,k).. Tm(k) =g= t(i,j) + M * (1- X(i,j,k));

E5(i,j,k).. Tm(k) =l= t(i,j) - M * (1- X(i,j,k));

E6(i,j).. Cmax =g= t(i,j) + sum(k, X(i,j,k)* P(i,k));


Model detop / all /;

solve detop using mip minimizing Z;

display   X.m, Z.m, X.l, Z.l;

objective comes 0 and there is no error code, we didn’t understand why the code is not working

2

Hey hllsyr,

there are multiple issues in the GAMS model that you have posted. The model itself is infeasible due to conflicting constraints.

  • It is not possible for both E1 and E2 to hold with the sets you have provided. When there are just three machines being responsible for as many as 37*96=3552 jobs, it is impossible for each machine to process at most one job while simultaneously finding exactly one machine for each job. Hence you either have to reduce the cardinality of jobs (card(i)*card(j)) or the equations themselves.

  • You could modify the definition of E3 in line 114 by starting with “E3(i,j)$(ord(j)+1<card(j))” which prevents the model from setting an upper bound for the starting time of the last operation.

  • I am not exactly sure what E4 and E5 are trying to express. I assume you are trying to assign the earliest starting time of any job of a specific machine k to Tm(k). Then only E5 makes sense but you must change the sign of the second term (adding instead of subtracting). Hence it should be: E5(i,j,k)… Tm(k) =l= t(i,j) + M * (1- X(i,j,k)); But since Tm(k) is not appearing in any other equation and the optimization is not pushing it upwards, this won’t work correctly on its own.

As a general advice for treating infeasibility in a model: Put “optfile=1 solver=cplex” in the text field at the top (adjacent the green “run” triangle) of your GAMS Studio window and create a textfile “cplex.opt” containing just one line “IIS=1” in the same directory of your GAMS model file (*.gms). This will show you a minimal list of inconsistent equations.

Kind regards,

André