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.

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 _{i=1}^{n}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 $n\log(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 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)

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

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

Notes et références

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

Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

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