Flow-shop

Les algorithmes présentés dans cette section ont pour but de minimiser la durée totale du traitement.

Le problème se résout de manière optimale par l'algorithme de Johnson^[1].

Soient deux partitions de l'ensemble des tâches ${\displaystyle U=\{i/p_{i1}<p_{i2}\}}$ et ${\displaystyle V=\{i/p_{i1}\geq p_{i2}\}}$

• trier les tâches de U par ${\displaystyle p_{i1}}$ croissant
• trier les tâches de V par ${\displaystyle p_{i2}}$ décroissant
• la séquence optimale est constituée de la concaténation des séquences U et V ainsi triées

L'algorithme a une complexité de l'ordre en ${\displaystyle n\log(n)}$, puisqu'il consiste avant tout à exploiter des algorithmes de tri.

Au-delà de deux machines, le flow-shop est un problème NP-difficile, il n'existe pas d'algorithme menant à une solution optimale en temps polynomial (sauf si P=NP), des heuristiques permettent néanmoins d'obtenir des solutions intéressantes.

• Trier les travaux par ${\displaystyle \sum _{j=1}^{n}p_{ij}}$
• Ordonnancer les deux premiers dans l'ordre le plus intéressant
• Pour i = 3 à n Faire
  • Insérer le travail ${\displaystyle i}$ dans la position ${\displaystyle k\in [1,i]}$ la plus intéressante
• Fin Pour

À partir du problème à m machines, on génère m-1 problèmes à 2 machines.

• Management

• Portail de l'informatique théorique