Johnson-Algorithmus

Der Johnson-Algorithmus ist ein Algorithmus zur Bestimmung der optimalen Reihenfolge mehrerer Aufträge an 2 Maschinen, damit die gesamte Bearbeitungszeit möglichst gering ist.

Idee

• Als erstes: Auftrag mit der kürzesten Belegung der ersten Maschine
• Als letztes: Auftrag mit der kürzesten Belegung der letzten Maschine

Algorithmus

Gegeben sind Aufträge mit Bearbeitungszeiten und an den Maschinen, z.B.:

1	2	5
2	3	1
3	8	6
4	4	7
5	9	5

1. Teile die Aufträge in 2 Gruppen:
   • Ordne Aufträge mit der Gruppe zu
   • Der Rest (Aufträge mit ) wird Gruppe zugeordnet
2. Sortiere die Aufträge innerhalb der Gruppen:
   • wird nach aufsteigend sortiert
   • wird nach absteigend sortiert
3. Verkette beide Gruppen und erhalte die optimale Reihenfolge.

Das Beispiel von oben ergibt nach Aufteilung und Sortierung folgende Reihenfolge:

:

1	2	5
4	4	7

:

3	8	6
5	9	5
2	3	1

Daraus folgt die optimale Reihenfolge .