Flow-shop

Le flow-shop est un problème d'ordonnancement d'atelier.

Description

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

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

Flowshop à deux machines

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 nlog(n), puisqu'il consiste avant tout à exploiter des algorithmes de tri.

Cas à plus de deux machines

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.

Nawaz-Enscore-Ham (NEH)

• 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

Campbell Dudek Smith

Notes et références

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

Articles connexes

• Management