model takes forever to solve Topic is solved

[pnong]

Hey people,
I've got an issue about my model.
I created a gams model to find cmax on my flowshop problem. Firstly i tried with 5 jobs, the problem solved immiedetly and it worked perfectly. After that i tried the same codes to solve the same problem with 10 jobs. Gams found the best solution which i already know in 255.6 secs. But the solution has not come to an end. It was taking days. The issue is the solving procces takes days and i wanna know why and where is the problem.

Thank you so much for your help.

Code: Select all

option lp = cplex;

set
j is numarasi /1*15/
m makine numarasi /1*3/;

alias (j, i);
table
P(j,m) islem süreleri
    1   2   3
1   22  20  7
2   7   18  14
3   6   19  15
4   20  12  4
5   16  20  14
6   5   14  8
7   9   14  12
8   5   15  11
9   11  12  11
10  7   15  3
11  21  14  4
12  11  16  2
13  8   16  13
14  8   16  4
15  25  12  8


;

scalar
L büyük bir sayı /1000/
*zamanlama2
J_1 iş sayısı -1 /9/;
*siralama3

variables
X(i,j,m) m makinesinde i işinden sonra j işi geliyorsa 1 değilse 0
C(j,m) m makinesinde j işinin tamamlanma zamanı
CJ(j) j işinin tamamlanma zamanı
CMAX maksimum tamamlanma zamani;

binary variables
X(i,j,m);

equations
siralama1 (i,m) her makinede her işten sonra en fazla bir iş
siralama2 (j,m) her makinede her işten önce en fazla bir iş
siralama3 (m) makinedeki takip sayıisi iş sayısından bir az olması
zamanlama1 (j,m) ilk makinede zamanlama
zamanlama2 (i,j,m) işler arası zamanlama
zamanlama3 (j,m) makineler arası zamanlama
zamanlama4 (j,m) her işin tamamlanma zamanı
makstamamlanma (j) maksimum tamamlanma zamanı
;

siralama1 (i,m).. sum(j, X(i,j,m)$(ord(j)<>ord(i))) =l= 1;

siralama2 (j,m).. sum(i, X(i,j,m)$(ord(j)<>ord(i))) =l= 1;

siralama3 (m).. sum (i, sum (j, X(i,j,m)$(ord(j)<>ord(i)))) =e= 14;

zamanlama1 (j,m)$(ord(m)=1).. C(j,m) =g= P(j,m);

zamanlama2 (i,j,m)$(ord(j)<>ord(i)).. C(j,m) - C(i,m) + 1000 *(1-X(i,j,m)) =g= P(j,m);

zamanlama3 (j,m)$(ord(m)>1).. C(j,m) - C(j,m-1) =g= P(j,m);

zamanlama4 (j,m)$(ord(m)=3).. CJ(j) =e= C(j,m);

makstamamlanma (j).. CMAX =g= CJ(j);

model akistipi /all/;
solve akistipi using mip minimizing CMAX;
display X.l, C.l, CJ.l;
* 255.66 saniye sonra optimal değere ulaştı

[Fred]

Hi pnong,

Scheduling problems are known to be challenging. Besides finding good feasible solutions (which seems to work okay for this model), solvers also work on improving the best known bound. I fed your problem into several state-of-the-art MIP solvers. After 10 minutes, they all provide a solution with objective in the range 240 to 244 and a bound in the range 53 to 56. So the relative gap is still huge. There is no simple way to make solvers close the gap more quickly. Some solvers allow setting different strategies, e.g. either to focus more on finding good feasible solutions or to focus more on improving the bound (e.g. by setting Cplex option mipemphasis=3) but this does not lead to significant improvements of the bound for this model.

You mention that you know the best solution already. If I understand the model/data correctly, we can derive a bound of 240 from symbol P(j,m) because the max total duration on one machine is 233 on m=2 and the minimum duration a job has to spend on machines 1 and 3 is 5 and 2. With that said, we know that the objective cannot be any better than 233+5+2=240. When using Cplex, you can define a corresponding stopping criterion via GAMS/Cplex option lowerobjstop. In this particular case, this may work because there is indeed a feasible solution with the value of that trivial bound. When the model/data becomes more complex, this may no longer be an option.

Of course when you know that the relaxation is poor and the bound is bad, you can also specify other termination criteria (e.g. time)

I hope this helps!

Fred

[pnong]

Hi pnong,

Scheduling problems are known to be challenging. Besides finding good feasible solutions (which seems to work okay for this model), solvers also work on improving the best known bound. I fed your problem into several state-of-the-art MIP solvers. After 10 minutes, they all provide a solution with objective in the range 240 to 244 and a bound in the range 53 to 56. So the relative gap is still huge. There is no simple way to make solvers close the gap more quickly. Some solvers allow setting different strategies, e.g. either to focus more on finding good feasible solutions or to focus more on improving the bound (e.g. by setting Cplex option mipemphasis=3) but this does not lead to significant improvements of the bound for this model.

You mention that you know the best solution already. If I understand the model/data correctly, we can derive a bound of 240 from symbol P(j,m) because the max total duration on one machine is 233 on m=2 and the minimum duration a job has to spend on machines 1 and 3 is 5 and 2. With that said, we know that the objective cannot be any better than 233+5+2=240. When using Cplex, you can define a corresponding stopping criterion via GAMS/Cplex option lowerobjstop. In this particular case, this may work because there is indeed a feasible solution with the value of that trivial bound. When the model/data becomes more complex, this may no longer be an option.

Of course when you know that the relaxation is poor and the bound is bad, you can also specify other termination criteria (e.g. time)

I hope this helps!

Fred

Thanks, Fred!

Your detailed answers were really kind and helped a lot to clarify many things.

A time constraint seems like the best option for me, because I don't want to make GAMS iterations stop when the best solution is 240, because the purpose of the model is, of course, to find the optimal solution.

Thank you very much for your help!

-Samet