Corrigé du problème 2
Rappel : PROBLEME 2
L'objectif est de reprendre le problème précédent et de trouver la solution optimale par un algorithme de programmation linéaire en nombres binaires pour les données suivantes.
paramètre | valeur numérique |
t1 | 16 |
t2 | 18 |
i | 1 | 2 | 3 | 4 | 5 |
pi | 4 | 3 | 5 | 6 | 8 |
Méthode : Solution
La résolution de ce problème se base sur l'affectation de chaque tâche avant ou après la période d'indisponibilité. On peut donc définir les variables de décision comme suit :
xi = 1 si la tâche i est ordonnancée avant t1 (i=1, 2, 3, 4, 5)
xi = 0 si la tâche i est ordonnancée après t2 (i=1, 2, 3, 4, 5)
Le problème peut donc être formulé en se basant sur le PLNE suivant :
Minimiser t2 + (1-x1)p1 + (1-x2)p2 + (1-x3)p3 + (1-x4)p4 + (1-x5)p5
sous les contraintes
x1p1 + x2p2 + x3p3 + x4p4 + x5p5 ≤t1
xi∈{0,1} (i=1, 2, 3, 4, 5)
Cette dernière formulation peut être instanciée au modèle suivant :
Minimiser 44 - 4x1 - 3x2 - 5x3 - 6x4 - 8x5
sous les contraintes
4p1 + 3p2 + 5p3 + 6p4 + 8p5 ≤16
xi∈{0,1} (i=1, 2, 3, 4, 5)
La résolution de ce problème commence par la construction d'une solution réalisable. On peut prendre la séquence (4, 5, 1, 2, 3) comme solution de départ. Cette solution donne une valeur de makespan égale à BS=30 conformément à l'ordonnancement décrit dans la figure suivante.
La PLNE va s'appuyer sur une relaxation de la contrainte d'intégrité des variables xi qui deviennent des variables réelles dans le modèle relaxé. La résolution du modèle relaxé est facile (elle se fait aisément en saturant la contrainte).
L'exécution de la PLNE avec une exploration en profondeur conduit à 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 2, 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 à 28.
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 nous proposons cette animation en format PPS. Il est recommandé de la visualiser l'évolution de l'arbre étape par étape (un clic correspond à une étape avec une possibilité d'effectuer un retour en arrière à chaque étape). Une étape correspond à la séparation d'un nœud.
