assigning jobs to machines with some hard constraints

Problems with modeling
Post Reply
terahacker
User
User
Posts: 1
Joined: 1 year ago

assigning jobs to machines with some hard constraints

Post by terahacker »

About the problem of assigning jobs to machines outside of lessons with GAMS (MILP)
Hello everyone. I searched for solutions on many different platforms, but unfortunately I couldn't get any results. I would be very grateful if anyone can help with this.
The question is about assigning jobs to machines running in parallel. In the example problem, there are 5 machines and 14 jobs. Process times of jobs are known. Each job can be processed on any machine, assigned to only 1 machine, and uninterrupted. No slack, setup or change times between jobs. It is a continuous flow process.
The goal here is to minimize the sum of the maximums of the completion times of all jobs with an optimal assignment (Makespan problem). The most important constraint here is to prevent any two jobs in the process from ending at the same time. For example, the end time of any job whose process on the 1st machine is finished should not be the same as the end time of another job on another machine. I added k4, k5, k6 and k7 constraints to differentiate the completion times of the jobs. But here I am encountering a problem and the solution times are either too long or cannot find the optimal one. Because Gams/Cplex is trying to prevent the end times of the last job on each machine from being the same with the constraints I wrote. These constraints contradict the objective function.
In summary, how can I write a model that will ensure that the completion times of all ongoing jobs on all machines are different? (According to the model, all of the jobs should start at time 0 and finish at Cmax. The finishing time of the last job of each machine can be Cmax and not different)

Option optcr = 0.01;
Option ResLim = 86400;
Option IterLim = 10000;
Sets
j job index /1*14/
k rank index /1*14/
m machine index /1*5/;
parameters
p(j) processing time of job j
/
1 120
2 150
3 100
4 60
5 85
6 40
7 55
8 45
9 95
10 90
11 30
12 65
13 40
14 70
/;
variables
Z, Cmax;
binary variables
X(j,k,m) 1 if job j is assigned to rank k on machine m, 0 otherwise;
variable
C(k,m) completion time of job k on machine m;
equations
obj,k0,k1,k2,k3,k4,k5,k6,k7;
obj.. Z=e=Cmax;
k0(k,m).. Cmax =g= C(k,m);
k1(j,k,m).. C(k,m) =g= (X(j,k,m)*p(j) + C(k-1,m));
k2(k,m).. sum(j,X(j,k,m)) =l= 1;
k3(j).. sum((k,m),X(j,k,m)) =e= 1;
k4(k,m).. (C(k,m)- C(k,m-1)) =g= 4;
k5(k,m).. (C(k,m)- C(k,m-2)) =g= 4;
k6(k,m).. (C(k,m)- C(k,m-3)) =g= 4;
k7(k,m).. (C(k,m)- C(k,m-4)) =g= 4;
model schedulingjobsCmax /all/;
solve schedulingjobsCmax using mip minimizing Z;
display X.l;
Post Reply