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 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 o.ä. und die Fertigungsaufträge durchlaufen diese in gleicher Reihenfolge.

Beispiel

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:

Welcher Auftrag soll als erster ausgeführt werden, welcher als zweiter usw.?

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, d.h. 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, d.h. als zweiter (A war der erste).

Für Auftrag C bleibt dann nur noch Platz 3.

Die Auftragsreihenfolge ist:

A – D – C – B.