Re: [Help-glpk] i need some help

[Andrew Makhorin]

Renato,

> this model is to single-machine scheduling problem.

There must be a constraint that at any time the machine can be used
only by one job. However, this constraint is expressed incorrectly in
your model, so in the solution all jobs start at time 0.

The correct constraint is the following:

s.t. rest2{i in TAREFAS, j in TAREFAS,
t in TEMPOS, tt in t..t+tempo_producao[i]-1: j != i and tt in TEMPOS}:
x[i,t] + x[j,tt] <= 1;

which means that if x[i,t] = 1, then
x[j,t] = ... = x[j,t+tempo_producao[i]-1] = 0 for all i, j != i, and t.

See the correct model attached.


Andrew Makhorin


Reading model section from a.md...
52 lines were read
Reading data section from a.dat...
34 lines were read
Generating z...
Generating rest1...
Generating rest2...
Model has been successfully generated
lpx_simplex: original LP has 1546 rows, 105 columns, 3254 non-zeros
lpx_simplex: presolved LP has 1545 rows, 105 columns, 3185 non-zeros
lpx_adv_basis: size of triangular part = 1545
      0:   objval =   4.100000000e+01   infeas =   1.000000000e+00 (0)
      7:   objval =   1.105000000e+02   infeas =   0.000000000e+00 (0)
*     7:   objval =   1.105000000e+02   infeas =   0.000000000e+00 (0)
*    26:   objval =   0.000000000e+00   infeas =   1.165734176e-15 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
Objective function is integral
+    26: mip =     not found yet >=              -inf        (1; 0)
+   132: mip =   2.900000000e+01 >=   0.000000000e+00 100.0% (11; 0)
+   328: mip =   2.400000000e+01 >=   0.000000000e+00 100.0% (20; 6)
+   501: mip =   2.100000000e+01 >=   1.000000000e+00  95.2% (22; 21)
+   935: mip =   1.100000000e+01 >=   2.000000000e+00  81.8% (53; 46)
+   973: mip =   9.000000000e+00 >=   3.000000000e+00  66.7% (28; 104)
+  1036: mip =   9.000000000e+00 >=     tree is empty   0.0% (0; 181)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   4.0 secs
Memory used: 1.8 Mb (1897717 bytes)
job P1 starts at 14
job P2 starts at 5
job P3 starts at 10
job P4 starts at 0
job P5 starts at 3
Model has been successfully processed

a.md
Description: Binary data