Flow-shop

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Configuration d'Ordonnancement («flow-shop») à cheminement unique.

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 _{i=1}^{n}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 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 | 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