Flow shop de permutation à deux et à plus de deux machines
Présentation du problème
On considère ici un flow shop de permutation, c'est-à-dire une chaîne de fabrication où les produits ne se doublent pas entre les postes (ou les machines), l'ordre d'exécution des produits est donc le même sur toutes les machines.
Le critère considéré ici est le critère le plus traditionnel : la durée totale d'exécution de l'ensemble des produits.
On considère un problème à 4 machines et la durée d'exécution des différents produits (8 produits) sur les différentes machines est donnée par le tableau suivant :
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|
1 | 1 | 8 | 2 | 4 | 5 | 6 | 9 | 5 |
2 | 5 | 2 | 5 | 4 | 1 | 8 | 4 | 9 |
3 | 2 | 3 | 7 | 8 | 7 | 7 | 2 | 7 |
4 | 8 | 9 | 8 | 6 | 7 | 4 | 1 | 3 |
En colonne : les 8 produits. En ligne : les 4 machines. Dans le tableau : la durée du produit j sur la machine i.
On se propose d'appliquer une heuristique connue sous le nom d'heuristique C.D.S pour Campbell Dudek et Smith.
Heuristique C.D.S
L'algorithme de Johnson présenté dans le chapitre, permet de résoudre de manière optimale le problème de flow shop de permutation lorsqu'il n'y a que deux machines.
Pour essayer d'obtenir une bonne solution du problème (sans garantie d'optimalité), on construit des problèmes fictifs qui ne comportent que deux machines, on applique à ces problèmes l'algorithme de Johnson ce qui donne des ordres pour les passage des produits, le même utilisé sur toutes les machines.
Enfin, on calcule la durée totale en calculant les dates au plus tôt sur le graphe potentiel-tâche obtenu en utilisant les contraintes de précédence sur la fabrication de chaque produit et les contraintes de précédence correspondant à l'ordre de passage sur les machines.
On retient la meilleure des solutions trouvées qui est donc un majorant de la solution optimale.
Pour savoir dans quelle mesure la solution trouvée est éloignée de la solution optimale, on calcule également des minorants de la solution optimale.
Question
On vous demande d'appliquer la règle de Johnson aux 2 machines 1 et 4 (en faisant comme si les machines 2 et 3 n'existaient pas) et de donner l'ordre obtenu.
Pour appliquer l'algorithme de Johnson, on peut utiliser une technique de tri.
On peut également utiliser une méthode par construction en partant d'un tableau vide ayant autant de positions que de produits.
Puis de manière itérative, jusqu'à ce que tous les produits soient placés,
on cherche le produit non placé ayant la plus petite durée sur l'une ou l'autre des machines,
si la plus petite durée est sur la première machine, on place le produit au début dans la première case encore vide,
si la plus petite durée est sur la dernière machine, on place le produit à la fin dans la dernière case encore vide.
S'il y a plusieurs choix possibles, on peut soit faire un des choix de manière aléatoire, soit construire de manière systématique tous les ordres possibles qui seront tous optimaux (pour les problèmes à deux machines).
Algorithme de Johnson sur les machines 1 et 4
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|
1 | 1 | 8 | 2 | 4 | 5 | 6 | 9 | 5 |
4 | 8 | 9 | 8 | 6 | 7 | 4 | 1 | 3 |
On commence avec le tableau vide :
- | - | - | - | - | - | - | - |
La plus petite durée est de 1.
Elle est sur la première machine sur le produit 1 et sur la dernière machine pour le produit 7.
Le produit 1 est mis en première position et le produit 7 est mis en dernière position.
1 | - | - | - | - | - | - | 7 |
Les plus petites durées suivantes sont 2 pour le produit 3 sur la première machine et de 3 pour le produit 8 sur la dernière machine.
3 est mis derrière 1 au début et 8 est mis avant 7 à la fin.
1 | 3 | - | - | - | - | 8 | 7 |
La plus petite durée pour les produits restants est de 4 pour le produit 4 sur la première machine et pour le produit 6 sur la dernière machine.
4 est mis derrière 1 et 3 au début et 6 est mis avant 8 et 7 à la fin.
1 | 3 | 4 | - | - | 6 | 8 | 7 |
La plus petite durée est de 5 pour le produit 5 sur la première machine, 5 est donc mis derrière 4 en début de séquence et le produit restant 2 est placé dans la seule place qui reste entre 5 et 6.
1 | 3 | 4 | 5 | 2 | 6 | 8 | 7 |
Nouvelles paires de machines fictives
Deux nouvelles machines fictives sont considérées.
La première machine est une "super" machine qui effectue successivement sur les produits l'opération sur la machine 1 suivie de l'opération sur la machine 2.
La dernière machine est une "super" machine qui effectue successivement sur les produits l'opération sur la machine 3 suivie de l'opération sur la machine 4.
Question
On vous demande d'appliquer l'algorithme de Johnson sur les deux nouvelles machines fictives ainsi définies afin de trouver un nouvel ordre de passage des produits sur l'ensemble des machines.
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|
1+2 | 6 | 10 | 7 | 8 | 6 | 14 | 13 | 14 |
3+4 | 10 | 12 | 15 | 14 | 14 | 11 | 3 | 10 |
On commence avec le tableau vide :
- | - | - | - | - | - | - | - |
La plus petite durée est de 3 sur la dernière machine pour le produit 7.
Le produit 7 est placé dans la dernière case.
La plus petite durée est de 6 pour les produits 1 et 5 sur la première machine.
On a donc deux solutions possibles pour le début de l'ordre des produits :
soit 1 suivi de 5, soit 5 suivi de 1.
1 ou 5 | 5 ou 1 | - | - | - | - | - | 7 |
Les plus petites durées suivantes sont 7 pour le produit 3 sur la première machine et 8 pour le produit 4 sur la première machine.
3 et 4 sont donc placés derrière 15 ou 51 au début de l'ordre.
1 ou 5 | 5 ou 1 | 3 | 4 | - | - | - | 7 |
Les plus petites durées des produits restants sont 10 pour le produit 2 sur la première machine et pour le produit 8 sur la dernière machine.
Le produit 2 est donc placé derrière le produit 4 au début alors que 8 est placé avant le produit 7 à la fin.
Il ne reste ensuite plus qu'un seul produit, le produit 6 que l'on place dans la dernière case vide.
1 ou 5 | 5 ou 1 | 3 | 4 | 2 | 6 | 8 | 7 |
Graphe potentiel-tâches correspondant à un ordre donné pour le flow shop de permutation
A tout ordre on peut affecter un graphe potentiel-tâche de la manière suivante : un sommet par opération sur toutes les machines plus un sommet fictif de début et un sommet fictif de fin et des arcs qui représentent d'une part la succession des produits sur chaque machine et d'autre part la succession des opérations au sein de chaque produit d'une machine à la suivante.
Les dates au plus tôt de la dernière tâche de ce graphe fournit la durée totale la plus courte de l'ordonnancement qui correspond à cet ordre.
Question
Pour l'ordre obtenu avec les machines fictives 1 et 4 (en ignorant les machines intermédiaires), on vous demande de dessiner le graphe potentiel-tâche correspondant aux quatre machines, de calculer les dates au plus tôt sur ce graphe et d'en déduire la durée totale de l'ordonnancement correspondant à cet ordre.
Graphe potentiel-tâche sur les quatre machines correspondant à l'ordre des produits 13452687
Au produit j correspond les tâches placées sur la colonne numérotée j.
Les contraintes de précédence sur les lignes (machines) correspondent à l'ordre utilisée pour les produits sur chacune des machines.
Les contraintes de précédence sur les colonnes (produits) correspondent au passage des produits sur les quatre machines.
Les valeurs sur les arcs correspondent toujours à la durée de l'opération qui est à l'origine de l'arc.
Dates au plus tôt du graphe potentiel-tâche correspondant à l'ordre des produits 13452687
La durée totale de l'ordonnancement pour cet ordre est donc égale à 57.
Calcul de minorants
On vous demande de calculer des minorants de la durée totale de l'ordonnancement.
De retenir la plus grande valeur de minorant trouvée comme minorant de la durée minimale.
D'en tirer des conclusion sur la qualité de la solution réalisable trouvée.
Question
Expliquer comment obtenir des minorants à partir de l'énoncé et sans calculer d'ordonnancement, puis calculer ces minorants.
La durée totale est au moins égale à la plus grande somme des durées des opérations sur cette machine.
Si la machine n'est pas la première, on ne peut commencer sur une machine que si le premier produit a atteint cette machine.
Si la machine n'est pas la dernière, l'ordonnancement ne sera terminé que quand le dernier produit qui passe sur cette machine sera passé sur les machines qui suivent.
S'il y a plus de deux produits, le premier produit qui passe sur les machines ne peut pas être le même que le dernier produit qui passe sur les machines.
Calcul d'un minorant pour chaque machine
Pour la machine 1 :
----------------------
La somme des durées des opérations qui passent sur la machine est égale à 40.
Si on met en dernier le produit 7 qui dure 4+2+1=7 sur les autres machines (produit qui passe le plus vite sur les trois dernières machines,
si l'exécution des autres produits sur les autres machines laisse les machines disponibles à l'instant où le produit 7 en a besoin,
alors on termine l'ordonnancement à l'instant : 40+7=47 et on ne peut pas faire mieux.
Pour la machine 2 :
----------------------
La somme des durées des opérations qui passent sur la machine est égale à 38.
Si on met en dernier le produit 7 qui dure 2+1=3 sur les autres machines (produit qui passe le plus vite sur les deux dernières machines,
si on met en premier le produit 1 qui dure 1 sur la première machine (produit qui passe le plus vite sur la première machine)
alors l'ordonnancement dure au minimum 1+38+3 = 42.
Ce minorant est moins contraignant que le précédent.
Pour la machine 3 :
----------------------
La somme des durées des opérations qui passent sur la machine est égale à 43.
Si on met en dernier le produit 7 qui dure 1 sur la dernière machine,
si on met en premier soit le produit 1, soit le produit 5 qui dure 1+5=5+1=6 sur les deux premières machines
alors l'ordonnancement dure au minimum 6+43+1=52.
Ce minorant est plus contraignant que les précédents.
Pour la machine 4 :
----------------------
La somme des durées des opérations qui passent sur la machine est égale à 46.
Si on met en premier le produit un qui dure 1+5+2 (produit qui passe le plus vite sur les trois premières machines)
alors l'ordonnancement dure 8+46=54.
Ce minorant est le plus contraignant des quatre minorants calculés.
C'est donc lui que nous retenons comme minorant.
Evaluation de la solution trouvée par la méthode CDS pour les machines fictives 1 et 4
La solution trouvée a une durée totale de 57, alors que le plus grand minorant obtenu est de 54,
La durée de la solution optimale est donc comprise entre 54 et 57
(plus grand minorant ≤ solution optimale ≤ plus petit majorant = meilleure solution trouvée).
La solution trouvée est donc au plus à quatre unités de temps de la solution optimale.
Pour les plus courageux
Vous pouvez considérer d'autres ordres et calculer la durée totale.
Question
Dessiner le graphe potentiel-tâches et calculer les dates au plus tôt pour les ordres trouvées avec les machines fictives M1+M2 et M3+M4
Durée totale pour l'ordre 15342687
La durée totale est de 54.
Comme le plus grand minorant est également de 54.
L'ordre 15342687 est optimal.
Durée totale pour l'ordre 51342687
La durée totale est de 59.
Cet ordre est strictement moins bon que les deux autres trouvés précédemment.
Il est à noter que la méthode CDS n'est qu'une heuristique.
Il n'est donc pas certain que l'on trouve sur toutes les exemples numériques la solution optimale.
Selon les valeurs numériques, la meilleure solution trouvée par CDS peut être obtenue avec n'importe lequel des groupements de machines permettant de construire deux machines fictives :
M1 et M4
M1+M2 et M3+M4
M1+M2+M3 et M2+M3+M4
ou d'autres variantes que l'on peut imaginer
M1 et M2+M4
M1+M2 et M4
etc.
On peut aussi trouver des ordres en utilisant des méta-heuristiques comme des algorithmes génétiques qui croisent des ordres pour en construire de nouveau ou en utilisant une méthode par voisinage qui modifie légèrement les ordres (par exemple en échangeant la position de deux produits successifs ou en échangeant la position de deux produits quelconque).
