Corrigé du problème 1
Rappel : PROBLEME 1
Dans ce problème, on considère le problème d'ordonnancement consistant à ordonnancer 5 tâches sur une seule machine. Chaque tâche i possède une durée opératoire pi. Les tâches doivent être exécutées sans préemption. La machine est indisponible durant la période [t1, t2]. L'objectif est de minimiser la date de fin d'exécution de la dernière tâche (makespan).
Les données sont explicitées dans les tableaux suivants. L'objectif est de résoudre le problème par une procédure de séparation et d'évaluation.
paramètre | valeur numérique |
t1 | 13 |
t2 | 15 |
i | 1 | 2 | 3 | 4 | 5 |
pi | 3 | 5 | 4 | 2 | 7 |
Méthode : Solution
La résolution de ce problème commence par la construction d'une solution réalisable. On peut prendre la séquence (1, 2, 3, 4, 5) comme solution de départ. Cette solution donne une valeur de makespan égale à b0=24 conformément à l'ordonnancement décrit dans la figure suivante.
La procédure de séparation et d'évaluation peut se baser sur une borne inférieure LB triviale égale à la somme des durées opératoires et de la durée de l'indisponibilité :
LB = t2 - t1 + p1 + p2 + p3 + p4 + p5
Par ailleurs, la séparation peut se faire à chaque niveau i selon la décision à prendre pour la tâche i : une affectation avant t1 ou bien une affectation après t2. La borne inférieure LB sera donc améliorée dans chaque nœud selon les tâches ordonnancées après la date t2. Par exemple, si dans un nœud quelconque on a décidé d'ordonnancer les tâches 1, 2 et 3 après t2 alors la borne améliorée LB' est calculée comme suit : LB'= t2 + p1 + p2 + p3.
L'exécution de la procédure de séparation et d'évaluation avec une exploration en profondeur donne l'arborescence suivante (pour une meilleure compréhension de la chronologie de la génération de l'arborescence il est recommandé de consulter l'animation correspondant à cet exemple). La valeur indiquée dans chaque nœud correspond à la valeur de la borne inférieure (et à la valeur de la fonction objectif dans un nœud terminal).
Une solution optimale consiste donc à affecter les tâches 4, 3 et 5 avant t1 et les autres tâches après t2 comme le montre la figure suivante. Cette solution donne un makespan égal à 23.
Simulation : Mieux comprendre le déroulement de la procédure par une animation
Afin de mieux comprendre comment la procédure se déroule sur cet exemple il est recommandé de visualiser l'animation suivante étape par étape (un clic correspond à une étape). Cette animation permettra de comprendre chronologiquement la procédure.
