Algorithme de Johnson : répartition de la charge sur plusieurs machines

Répartir la charge sur les machines dans un atelier

Cette élaboration correspond à l’ordonnancement de fabrications de N phases mettant en jeu M moyens utilisés en séquentiel.

Algorithme de Johnson

Cette technique ne s’applique uniquement que lorsque N = M = 2.

Selon les ouvrages traitant de ce problème, plusieurs algorithmes différents portent le nom d’algorithme de Jonhson. Nous allons les étudier en s’aidant d’un exemple :

Étant donné quatre OF (P1, P2, P3, P4) réalisés en passant successivement sur les postes de charge M1 et M2.

Illustration 1: Placement des OF dans l'ordre de leur numéro de référence

On peut constater, que dans ce cas, le moyen M1 est bien occupé mais que le moyen M2 est inoccupé pendant 11 heures. De plus, le temps total de réalisation est de 37 heures.

Algorithme « classique ». Tant qu’il y a une fabrication :

• recherche du temps le plus faible de passage sur les deux machines;

• si le temps concerne la première phase nous commençons par elle;

• si le temps concerne la deuxième phase nous terminons par cette fabrication.

Appliqué à l’exemple, nous trouvons l’ordre : P1, P3, P4, P2

Détail :

Tps + faible sur phase 10 → P1, donc au début. P1

Tps + faible sur phase 20 → P2, donc en Fin. P1 → P2

Tps + faible sur phase 20 → P4, donc en Fin. P1 → P4 → P2

Tps + faible sur phase 10 → P3, donc en Début. P1 → P3 → P4 → P2

Illustration 2: Placement des OF dans l'ordre de l'algorithme de Johnson

Avec l’algorithme de Jonhson, le temps d’inoccupation du moyen M2 n’est plus que de 5 heures, ce qui permet de réaliser l’ensemble de ces fabrications en 31 heures.

Autre algorithme

• Établir l’ensemble E1 des fabrications dont le temps opératoire sur le premier poste est inférieur ou égal au temps opératoire sur le deuxième poste.

Groupe E1 → P1, P3

• Établir l’ensemble E2 des fabrications dont le temps opératoire sur le premier poste est supérieur au temps opératoire sur le deuxième poste.

Groupe E2 → P2, P4

• Trier l’ensemble E1 dans l’ordre croissant des temps opératoires sur le premier poste.

P1, P3

• Trier l’ensemble E2 dans l’ordre décroissant des temps opératoires sur le deuxième poste.

P4, P2

• L’ordre des fabrications est déterminé par l’ordre de E1 trié puis de E2 trié.

P1 → P3 → P4 → P2

Appliqué à l’exemple, nous trouvons :

Ensemble E1 trié en ordre croissant de Tm1 = (P1, P3)

Ensemble E2 trié en ordre décroissant de Tm2 = (P4, P2)

Ce qui donne l’ordre : P1, P3, P4, P2

Algorithme de Johnson généralisé

Cette méthode s’applique sur toutes les fabrications dont le processus de production est séquentiel et composé de plus de deux postes de fabrication. Elle peut s’appliquer pour toutes les fabrications en ligne, même si tous les postes de charge ne sont pas utilisés.

Méthode de calcul

Pour chaque fabrication :

• Faire la somme des phases (N).

• Calculer x = N – dernière phase (c’est la somme des _n–_1 premières phases).

• Calculer y = N – première phase (c’est la somme des n–1 dernières phases).

• Calculer le rapport k = x/y.

• L’ordre des fabrications est défini par l’ordre croissant de ce rapport k.

Étant donné quatre OF (P1, P2, P3, P4) réalisés en passant successivement sur les postes de charge M1, M2 et M3.

En appliquant l’algorithme sous forme de tableau, nous trouvons l’ordre ces fabrications:
P4, P3, P2, P1.