Principe
Pour n tâches passant sur la machine A puis la machine B : on cherche le plus petit temps parmi toutes les tâches. S'il est sur A, la tâche se place au début ; s'il est sur B, à la fin. On retire la tâche et on recommence. Le résultat est optimal pour 2 machines.
Comprendre pas à pas
1. La situation
Cinq ordres passent tous d'abord en découpe laser, puis en pliage, dans le même ordre. Le chef d'atelier veut terminer le lot le plus tôt possible. Question : dans quel ordre passer les ordres ?
2. Les temps par machine (heures)
| Ordre | J1 | J2 | J3 | J4 | J5 |
|---|---|---|---|---|---|
| Machine 1 : découpe | 3 | 5 | 1 | 6 | 7 |
| Machine 2 : pliage | 6 | 2 | 2 | 6 | 5 |
3. L'idée
L'algorithme de Johnson donne l'ordre optimal (durée totale minimale) quand plusieurs travaux passent sur deux machines dans le même ordre. Idée : commencer par les travaux courts sur la machine 1 (pour alimenter vite la machine 2), finir par les travaux courts sur la machine 2 (pour qu'elle ne termine pas tard).
1) Travaux avec temps M1 ≤ temps M2 : en tête, par temps M1 croissant
2) Autres travaux : en queue, par temps M2 décroissant
4. Le calcul déroulé
Groupe 1 (M1 ≤ M2). J3 (1 ; 2), J1 (3 ; 6), J4 (6 ; 6) : par M1 croissant → J3, J1, J4.
Groupe 2 (M1 > M2). J2 (5 ; 2), J5 (7 ; 5) : par M2 décroissant → J5, J2.
Séquence. J3 – J1 – J4 – J5 – J2 : fin à 24 h.
Comparaison. Dans l'ordre J1 à J5 : fin à 27 h. Gain : 3 heures (11 %) sans rien changer d'autre.
5. À vous de jouer
Basculez entre l'ordre de saisie (0) et l'ordre de Johnson (1) : regardez la durée totale et les attentes de la machine 2.
6. Ce qu'il faut retenir
- Deux machines, même ordre de passage : Johnson donne l'optimum.
- Courts sur M1 en tête, courts sur M2 en queue.
- Un gain gratuit, simplement par l'ordre de passage.
Mise en œuvre
- Acteurs
- Ordonnanceur
- Durée
- Quelques minutes par séquence
- Livrables
- Séquence optimale sur deux machines
- Relever les tempsTemps de chaque lot sur la machine A et sur la machine B.
- Trouver le plus petit tempsParmi tous les temps restants, sur A ou sur B.
- Placer le lotPlus petit temps sur A : en tête de séquence ; sur B : en fin de séquence.
- RépéterRetirez le lot placé et recommencez jusqu'à ce que tous les lots soient placés.
Exemple d'application
Découpe puis pliage de 5 lots : en appliquant Johnson, la durée totale passe de 21 h (ordre d'arrivée) à 17 h.
Points de vigilance
- Applicable strictement à 2 machines : au-delà, ce n'est qu'une heuristique