Ordonnancement d'atelier à deux machines (Johnson)
Introduction
Il s'agit ici d'un autre cas particulier de l'ordonnancement de projet à contraintes disjonctives.
Il y a seulement deux ressources en un exemplaire, que l'on appelle machine 1 et machine 2.
Les tâches sont couplées par deux et correspondent à des travaux ou jobs.
A tout travail correspond une tâche ou opération sur la machine 1, suivie d'une tâche ou opération sur la machine 2.
Le critère à minimiser est toujours la durée totale.
Un théorème, démontrée en 1954 par Johnson, permet de construire un algorithme rapide (polynomial) qui résout ce problème de manière optimale.
Le calcul des dates au plus tôt permet d'obtenir l'ordonnancement précis correspondant à l'algorithme de Johnson.
L'exercice proposé à la fin permet de présenter des heuristiques et des méta-heuristiques pour résoudre le même problème lorsqu'il y a m machines en un seul exemplaire.
Fondamental :
Les ordonnancements semi-actifs sont dominants pour le problème d'ordonnancement d'atelier à deux machines où on minimise la durée totale de l'ordonnancement.
Les définitions d'ensembles semi-actifs et d'ensembles dominants ont été données dans le chapitre sur les méthodes heuristiques simples à base de priorité pour les ordonnancements de projet.
Fondamental :
Les ordonnancements de permutation où les travaux passent dans le même ordre sur les deux machines sont dominants pour le problème d'ordonnancement d'atelier à deux machines où on minimise la durée totale de l'ordonnancement.
Notations
Ai : processing time ou durée du travail i sur la première machine.
Bi : processing time ou durée du travail i sur la seconde machine.
Fondamental :
Johnson a prouvé que pour trouver l'ordonnancement qui minimisela durée totale, il suffit de classer i avant j si :
min(Ai,Bj)≤min(Aj,Bi)
Premier algorithme construit à partir de la règle de Johnson
• Classer les travaux en deux groupes:
• Dans le premier groupe G1, mettre tous les travaux tels que Ai<Bi
• Dans le second groupe G2, mettre tous les travaux tels que Bi≤Ai
• Classer G1 par Ai croissants
• Classer G2 Bi décroissants
• La solution optimale est constituée de la séquence G1 suivi de G2.
• Cette séquence est optimale.
Preuve que la solution construite par l'algorithme respecte bien la règle de Johnson
Il suffit de comparer deux éléments i et j avec i placé avant j.
• si i et j sont dans G1, on a :
Ai<Bi, Aj<Bj et Ai≤Aj puisque i et j sont dans G1 et que G1 est classé dans l'ordre croissant des durées sur la machine 1.
Donc Ai≤Aj≤Bj et min(Ai,Bj)=Ai≤min(Aj,Bi) .
• si i et j sont dans G2, on a :
Bi≤Ai etBj≤Aj et Bj≤Bi puisque i et j sont dans G2 et que G2 est classé dans l'ordre décroissant des durées sur la machine 2. Donc Bj≤Bi≤Ai et min(Ai,Bj)=Bj≤min(Aj,Bi) .
• si i est dans G1 et j dans G2, alors Ai≤Bi etBj≤Aj . Donc min(Ai,Bj)≤min(Aj,Bi) .
Notations utilisées pour un deuxième algorithme qui respect la règle de Johnson
W = ensemble de travaux non encore traités.
L1 = liste des travaux placés en tête
L2 = liste des travaux placés en queue
Deuxième algorithme construit à partir de la règle de Johnson
L1:=∅;
L2:=∅;
W:={travaux};
tantque W≠∅ faire
recherche dans W du travail k possédant la plus petite durée d'opération
sur l'une ou l'autre des deux machines ;
si la plus petite durée est sur la machine fictive m1 alors
on met k en queue de L1;
sinon
on met k en tête de L2;
finsi
On retire k de W ;
fintantque
On peut vérifier que cet algorithme respecte bien la règle de Johnson, car elle est vérifiée localement chaque fois que l'on ajoute une opération.
Ordonnancement obtenu par un ordre de Johnson
L1 suivi de L2 donne l'ordre de passage des opérations sur les deux machines.
On place les opérations de manière contiguë dans cet ordre sur la première machine.
Sur la deuxième machine, on place les produits au plus tôt dans le même ordre en tenant compte de la fin de l'opération qui précède sur la deuxième machine et de la fin de l'opération du produit sur la première machine.
Voir l'exercice qui suit pour avoir des exemples d'utilisation de l'algorithme de Johnson.
