Inhaltsverzeichnis
Der Johnson-Algorithmus liefert für den 2-Maschinen-Fall eine optimale Reihenfolge der jeweiligen Aufträge, die beide Maschinen in derselben Reihenfolgen durchlaufen. Die Bestimmung der optimale Reihenfolge der Aufträge erfolgt, indem die minimale Bearbeitungszeit als Entscheidungskriterium herangezogen wird. Dies soll anhand eines Beispiels dargestellt werden.
Beispiel: Johnson-Algorithmus
Beispiel
Gegeben seien folgende Aufträge
16 | 5 | 4 | 14 | 12 | 5 | |
6 | 12 | 7 | 9 | 15 | 1 |
Wie sieht die optimale Reihenfolge bei Minimierung der Bearbeitungszeit nach dem Johnson-Algorithmus aus?
Vorgehensweise
Zuerst wird der Auftrag mit der kürzesten Bearbeitungszeit ausgewählt. Ist dieser Auftrag mit der kürzesten Bearbeitungszeit auf Maschine 2 (also
In diesem Beispiel: Der Auftrag
Der Auftrag mit der kürzesten Bearbeitungszeit ist jetzt
4 | 16 | 5 | 14 | 12 | 5 | |
7 | 6 | 12 | 9 | 15 | 1 |
Der nächste Auftrag ist
4 | 5 | 16 | 14 | 12 | 5 | |
7 | 12 | 6 | 9 | 15 | 1 |
Weiter folgt Auftrag
4 | 5 | 14 | 12 | 16 | 5 | |
7 | 12 | 9 | 15 | 6 | 1 |
Als nächstes folgt der Auftrag
4 | 5 | 12 | 14 | 16 | 5 | |
7 | 12 | 15 | 9 | 6 | 1 |
4 | 5 | 12 | 14 | 16 | 5 | |
7 | 12 | 15 | 9 | 6 | 1 |
Berechnung der Gesamtbearbeitungszeit
Die Gesamtbearbeitungszeit ergibt sich wie folgt:
Für Maschine 1 können die Aufträge ohne Verzögerung nacheinander abgearbeitet werden, da dieser Maschine keine weiteren Maschinen vorgelagert sind. Die Bearbeitungszeiten der Aufträge müssen also nur kumuliert werden. Maschine 1 hat damit eine Gesamtbearbeitungszeit von 56 ohne Pufferzeiten.
4 | 9 | 21 | 35 | 51 | 56 |
Für Maschine 2 sieht das schon anders aus. Da die Maschine 1 der Maschine 2 vorgelagert ist, muss dies bei der Berechnung der Bearbeitungszeit berücksichtigt werden. Denn ist ein Auftrag bereits auf Maschine 2 eingeplant, aber auf Maschine 1 noch nicht fertiggestellt, entstehen Pufferzeiten und die Gesamtbearbeitungszeit verlängert sich.
Berechnung
Der Auftrag
4 | 9 | 21 | 35 | 51 | 56 | |
11 | 12 | 15 | 9 | 6 | 1 |
Als nächstes betrachtet man Auftrag
4 | 9 | 21 | 35 | 51 | 56 | |
11 | 23 | 15 | 9 | 6 | 1 |
Auftrag
4 | 9 | 21 | 35 | 51 | 56 | |
11 | 23 | 38 | 9 | 6 | 1 |
Auftrag
4 | 9 | 21 | 35 | 51 | 56 | |
11 | 23 | 38 | 47 | 6 | 1 |
Auftrag
4 | 9 | 21 | 35 | 51 | 56 | |
11 | 23 | 38 | 47 | 57 | 58 |
Berechnung der Pufferzeit
Die Berechnung der Pufferzeit der Maschine 2 erfolgt so:
Man berechnet für einen Auftrag
Pufferzeit = Gesamtbearbeitungszeit aller Aufträge bis
4 | 9 | 21 | 35 | 51 | 56 | |
11 | 23 | 38 | 47 | 57 | 58 | |
Puffer | 4 | 0 | 0 | 0 | 4 | 0 |
Z.B.: Bei Auftrag
Grafisch: Johnson-Algorithmus
Man kann das ganze auch grafisch ermitteln, indem man die Reihenfolge in ein Gantt-Diagramm einzeichnet.