Où est l'erreur dans ce modèle/cette instance de planification de travail?

Question

Le modèle/instance MathProg suivant pour minimiser les retards totaux et les avances de tâches dans une machine renvoie la solution optimale [2, 7, 3, 8, 1, 5, 4, 6] avec un total de 575. Quelqu'un peut m'expliquer pourquoi pas 587, puisque la date de fin pour la tâche 4 est 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

Answer 1

Étant donné que le modèle est la minimisation, la solution optimale suggère que le début de la quatrième tâche est retardée de 6 unités, générant une interruption de la machine.