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;
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.