Flow-shop

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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.

Description[modifier | modifier le code]

Le flow-shop définit un ensemble de n tâches et m 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 m ;
  • 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 M_{nm}(\mathbb{R}^{+}), dont les coefficients seront nommés p_{ij} (temps pour passer par la tâche i sur la machine j).

Les fonctions objectif sont généralement :

  • C_{max}, date de fin de la dernière tâche sur la machine m, soit le temps total passé à exécuter tous les travaux ;
  • \Sigma^{n}_{i=1} c_i, somme des dates de fin des tâches sur la machine m.

Algorithmes de minimisation de c_{max}[modifier | modifier le code]

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

Flowshop à deux machines[modifier | modifier le code]

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 U = \{i / p_{i1} < p_{i2}\} et V = \{i / p_{i1} \geq p_{i2}\}

  • trier les tâches de U par p_{i1} croissant
  • trier les tâches de V par 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 n \log(n), puisqu'il consiste avant tout à exploiter des algorithmes de tri.

Cas à plus de deux machines[modifier | modifier le code]

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

Heuristique de Nawaz, Enscore et Ham (NEH)[modifier | modifier le code]

  • Trier les travaux par \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 i dans la position k \in [1,i] la plus intéressante
  • Fin Pour

Heuristique de Campbell, Dudek et Smith[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

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

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]