Programmation dynamique exponentielle pour des problèmes d'ordonnancement de type flowshop à 3 machines

Session : SS3-1 / SS3 : Planification de la Production et Lot-Sizing
Mercredi 10 février 11:00 - 12:20 Salle : RP7
Lei Shang, Christophe Lenté, Mathieu Liedloff et Vincent T'Kindt

Dans cet article, nous traitons du problème flowshop à $3$ machines où nous cherchons à minimiser le emph{makespan}. Nous proposons un algorithme de programmation dynamique qui résoud ce problème en temps O*(3^n). L'algorithme peut être généralisé pour traiter d'autres problèmes. La généralisation de l'algorithme sur le problème F3||f_{max} est présentée.

Mots clés : algorithme modérément exponentiel, programmation dynamique, flowshop