Johnson-Algorithmus
aus Wikipedia, der freien Enzyklopädie
Der Johnson-Algorithmus ist ein Verfahren zur Reihenfolgeplanung in den Bereichen Produktionswirtschaft und technische Informatik und geht zurück auf David Johnson, 1976. Der mathematische Ansatz gründet auf der Graphentheorie.
Inhaltsverzeichnis |
[Bearbeiten] Problem
Es existiert ein Stapel mit unbestimmt vielen Aufträgen An, die in einer optimalen Reihenfolge bezüglich der Durchlaufzeit auf genau zwei Maschinen / Prozessoren, Mj bearbeitet werden sollen.
[Bearbeiten] Der Algorithmus
Das Problem kann mit folgender iterativer Vorschrift gelöst werden.
- Suche den Auftrag Ai mit der absolut kürzesten Bearbeitungszeit
- Entscheide:
- Falls j = 1: Ordne den Auftrag Ai so weit vorn wie möglich in der Reihenfolge an
- Falls j = 2: Ordne den Auftrag Ai so weit hinten wie möglich in der Reihenfolge an
- fahre fort bei 1. solange bis jeder Auftrag zugeordnet ist.
[Bearbeiten] Ergebnis
Der Johnson-Algorithmus liefert die Durchlaufzeit-optimale Reihenfolge der Aufträge.
[Bearbeiten] Beispiel
Fünf Aufträge mit unterschiedlichen Bearbeitungszeiten auf den Maschinen M1 und M2 sollen Durchlaufzeit-optimal bearbeitet werden.
Die Folgende Tabelle gibt an, wie viel Zeit (in ZE) ein Auftrag Ai auf einer Maschine Mj benötigt.
| A1 | A2 | A3 | A4 | A5 | |
|---|---|---|---|---|---|
| M1 | 14 | 12 | 7 | 13 | 11 |
| M2 | 3 | 27 | 8 | 9 | 30 |
Der Johnson-Algorithmus sucht sich jetzt den kürzesten Auftrag, also A1 mit 3 ZE. Da A1 auf M2 (j=2) am wenigsten Zeit benötigt, wird er in der neuen Reihenfolge so weit wie möglich hinten eingeordnet.
Der nächst-kürzeste Auftrag ist A3 mit 7 ZE. Da A3 auf M1 am wenigsten Zeit benötigt, wird er in der neuen Reihenfolge so weit vorn wie möglich eingeordnet.
Usw.
Die durchlaufzeitoptimale Reihenfolge für dieses Beispiel ist demnach:
A3 -> A5 -> A2 -> A4 -> A1
