Johnson-Algorithmus
Johnson-Algorithmus Definition
Der Johnson-Algorithmus ist eine Möglichkeit, das Reihenfolgeproblem bei Werkstattfertigung – die optimale Reihenfolge der Aufträge auf den Arbeitsplätzen / Maschinen zu bestimmen – zu lösen.
Optimiert – das heißt hier: minimiert – wird die Zykluszeit bzw. die gesamte Bearbeitungszeit; das ist die Zeit, die für alle Fertigungsaufträge (im Beispiel unten vier Aufträge) benötigt wird.
Ausgangspunkt: Es gibt zwei Maschinen / Stationen oder Ähnliches und die Fertigungsaufträge durchlaufen diese in gleicher Reihenfolge.
Alternative Begriffe: Johnson-Verfahren, Verfahren von Johnson.
Beispiel
Beispiel: Optimale Auftragsreihenfolge mit dem Johnson-Algorithmus bestimmen
Ein Lieferdienst bietet Pizza und Flammkuchen an. Das erfordert immer zwei Stationen in identischer Reihenfolge: 1) "Belegen" und 2) "Backen".
Folgende 4 "Fertigungsaufträge" (Kundenbestellungen) A bis D mit ihren jeweiligen Bearbeitungszeiten in Minuten auf den beiden Stationen liegen vor:
| Auftrag | Station 1 | Station 2 |
|---|---|---|
| A "Pizza Magherita" | 2 | 10 |
| B "Flammkuchen Klassik" | 7 | 3 |
| C "Pizza Spezial" | 5 | 12 |
| D "Flammkuchen Spezial" | 4 | 8 |
Welcher Auftrag soll als erster ausgeführt werden, welcher als zweiter und so weiter?
Der Johnson-Algorithmus geht so vor:
#1 Den Auftrag mit der geringsten Bearbeitungszeit (BZ) (auf einer Station) wählen. Das ist A mit 2 Minuten auf der Station 1 "Belegen". (Wenn es mehrere Aufträge mit gleich kurzer BZ gibt, kann man einen beliebigen wählen).
#2 Erfolgt diese kürzeste BZ auf Station 1 (so wie bei A), wird der Auftrag so früh wie möglich bearbeitet, d.h. hier als erster. A ist also der Auftrag, der als erster drankommt.
#3 Erfolgt diese kürzeste BZ hingegen auf Station 2, wird der Auftrag so spät wie möglich bearbeitet.
#4 Der nächste Auftrag wird gewählt, der Vorgang wiederholt, bis alle Aufträge eingeplant sind.
Die nächst kürzeste BZ hat Auftrag B mit 3 Minuten auf Station 2 "Backen". Dieser Auftrag wird deshalb so spät wie möglich, das heißt hier als letzter ausgeführt. Auftrag B kommt also als 4. und letzter Auftrag dran.
Auftrag D hat die nächst kürzeste BZ mit 4 Minuten auf Station 1. Der Auftrag wird deshalb so früh wie möglich bearbeitet, das heißt als zweiter (A war der erste).
Für Auftrag C bleibt dann nur noch Platz 3.
Die Auftragsreihenfolge ist:
A – D – C – B.