Exercice 6 - Ordonnancement

En votre qualité de manager, vous vous retrouvez confronté au problème suivant : vous avez un ensemble de tâches à effectuer, chacune d'elle ayant un temps d'exécution connu à l'avance et une date de fin souhaitée. De plus, il existe pour chaque tâche une date avant laquelle il n'est pas possible de commencer son exécution. Votre équipe ne peut pas travailler sur deux tâches différentes en même temps et il n'est pas possible de fractionner ou d'interrompre l'exécution d'une tâche. Si l'exécution d'une tâche n'est pas achevée avant la date de fin souhaitée, on dit de cette tâche qu'elle est en retard. Votre objectif est de déterminer un calendrier d'exécution des tâches de sorte à minimiser la somme des retards. Voici les projets à réaliser en septembre :

numéro	nom	exécution au plus tôt	durée	deadline
1	changer la plomberie	1	1	6
2	débugger le projet $A$	2	3	4
3	nettoyer la voiture du PDG	1	1	6
4	installer le progiciel $B$	8	2	23
5	créer la base de donnée pour $C$	1	5	12
6	coder une interface graphique pour $C$	10	5	15
7	préparer le planning d'octobre	17	2	19

Par exemple, l'installation du progiciel $B$ prend $2$ jours consécutifs, elle ne peut pas commencer avant le $8$ septembre, et doit se terminer au plus tard le $23$ septembre. Il possible de commencer le $8$ et de terminer le $9$ tout comme il est possible de commencer le $22$ et de terminer le $23$.

1. Donnez une solution réalisable pour ce problème. Vous présenterez la solution sous forme d'un tableau, chaque tâche occupera une ligne et celles-ci seront disposées dans l'ordre de leur exécution. Vous utiliserez quatre colonnes
   • le nom de la tâche
   • la date de début
   • le temps d'exécution
   • la date de fin d'éxecution
2. Formalisons le problème.
   • Données : un nombre $n$ de tâches, un ensemble de durées $\{d_1, \ldots, d_n\}$, un ensemble de dates de début d'exécution au plus tôt $\{r_1, \ldots, r_n\}$, un ensemble de dates de fin d'exécution au plus tard $\{f_1, \ldots, f_n\}$, une constante $M$.
   • Question : Existe-t-il un ordre d'exécution des tâches tel que la somme cumulée des retards n'excède pas $M$ ?
   Nous appelerons ce problème SCHEDULING. Soient $\{s_1, \ldots, s_n\}$ les dates de début d'exécution de chacune des tâche. Soient $\{t_1, \ldots, t_n\}$ les dates de fin d'exécution. Donnez une relation simple entre $t_i$, $s_i$ et $d_i$. Prenez bien soin de vérifier que cette relation est vérifiée dans l'exemple de la question précédente.
3. L'exécution de la tâche $i$ ne peut pas commencer avant la date $r_i$. Exprimez cette contrainte avec les notations des questions précédentes.
4. Deux tâches d'indices respectifs $i$ et $j$ ne peuvent pas se superposer, exprimez cette contrainte à l'aide d'une proposition portant sur $s_i$, $s_j$, $t_i$ et $t_j$.
5. Combien y a-t-il de contraintes de cette forme ? Vous justifierez votre réponse en dénombrant les couples $(i, j)$ tels que $1 \leq i < j \leq n$.
6. Nous notons $\max (a, b)$ la plus grande des deux valeurs $a$ et $b$. A quoi correspond la valeur $\max (0, t_i - f_i)$ ?
7. Nous choisissons comme fonction objectif la somme cumulée des retards. Exprimez cette fonction objectif à partir des $t_i$ et des $f_i$
8. Exprimez la condition ``la somme cumulée des retards n'excède pas $M$'' avec les notations de la question précédente