Flow-shop

Le flow-shop est un problème de la théorie de l'ordonnancement, un domaine de la recherche opérationnelle et de l'algorithmique.

DescriptionModifier

Le flow-shop définit un ensemble de   tâches et   machines. Les contraintes du problème sont de deux types :

  • les contraintes de gamme, toutes les tâches doivent passer sur toutes les machines, de la machine 1 à la machine   ;
  • les contraintes de ressource, une machine ne peut traiter qu'une tâche à la fois.

En général, on cherche des solutions telles que les tâches ne peuvent pas se doubler, elles passent dans le même ordre sur toutes les machines, c'est ce qu'on appelle flowshop de permutation.

Dans le cas le plus simple, les données du problème sont les temps que chaque tâche passe sur chaque machine, soit une matrice dans  , dont les coefficients seront nommés   (temps pour passer par la tâche i sur la machine j).

Les fonctions objectif sont généralement :

  •  , date de fin de la dernière tâche sur la machine  , soit le temps total passé à exécuter tous les travaux ;
  •  , somme des dates de fin des tâches sur la machine  .

Algorithmes de minimisation de cmaxModifier

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

Flowshop à deux machinesModifier

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   et  

  • trier les tâches de U par   croissant
  • trier les tâches de V par   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  , puisqu'il consiste avant tout à exploiter des algorithmes de tri.

Cas à plus de deux machinesModifier

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.

Heuristique de Nawaz, Enscore et Ham (NEH)Modifier

  • Trier les travaux par  
  • Ordonnancer les deux premiers dans l'ordre le plus intéressant
  • Pour i = 3 à n Faire
    • Insérer le travail   dans la position   la plus intéressante
  • Fin Pour

Heuristique de Campbell, Dudek et SmithModifier

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

Notes et référencesModifier

  1. S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Res. Log. Quart. I(1954)61-68.

Voir aussiModifier

Articles connexesModifier