Where is the error in this job scheduling model/instance?

58 views Asked by At

The following MathProg model/instance for minimize total delays and advances of tasks in one machine is returning the optimal solution [2, 7, 3, 8, 1, 5, 4, 6] with total 575. Someone can explain me why not 587, since end date for task 4 is 540?

set tasks;

param procTime {tasks} >= 0;
param deliveryDate {tasks} >= 0;
param BIG := 1000;

var seq {tasks, tasks} binary;
var endDate {tasks} >= 0;
var delay {tasks} >= 0;
var advance {tasks} >= 0;

minimize f: sum {i in tasks : i != 0} (delay[i] + advance[i]);

s.t. c1 {i in tasks : i != 0}: delay[i] >= endDate[i] - deliveryDate[i];

s.t. c2 {i in tasks : i != 0}: advance[i] >= deliveryDate[i] - endDate[i];

s.t. c3 {j in tasks}: sum {i in tasks : i != j} seq[i,j] = 1;

s.t. c4 {i in tasks}: sum {j in tasks : i != j} seq[i,j] = 1;

s.t. c5 {i in tasks, j in tasks : j != 0}: endDate[j] >= endDate[i] - BIG + (procTime[j] + BIG) * seq[i,j];

s.t. c6 {i in tasks: i != 0}: endDate[i] >= 0;

s.t. c7: endDate[0] = 0;

solve;

display seq;

display f;


data;

set tasks := 0 1 2 3 4 5 6 7 8;

param procTime :=
0 0
1 64
2 53
3 63
4 99
5 189
6 44
7 50
8 22;

param deliveryDate :=
0 0
1 100
2 70
3 150
4 601
5 118
6 590
7 107
8 180;

end;

Solution check Solution check

1

There are 1 answers

0
dgolive On

Since the model is minimization, the optimal solution suggests that the start of the fourth task is delayed by 6 units, generating an interruption in the machine.

enter image description here