Problèmes d'application sur les méthodes exactes
Exemple : PROBLEME 1
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. 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 |
Exemple : PROBLEME 2
Reprendre le problème précédent. Trouver une 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 |
Exemple : PROBLEME 3
L'objectif est de résoudre une extension du problème précédent avec des durées de latence qi (i=1, 2, 3, 4) et de trouver une solution optimale par un algorithme de programmation dynamique pour les données suivantes. Le critère à minimiser est la date de livraison de la dernière tâche (c'est-à-dire, Lmax = max i=1,2,...,n {Li} avec Li=Ci+qi et Ci la date de fin d'exécution de la tâche i).
paramètre | valeur numérique |
t1 | 11 |
t2 | 14 |
i | 1 | 2 | 3 | 4 |
pi | 4 | 6 | 5 | 2 |
qi | 7 | 4 | 2 | 1 |
