Das Kefk Network Wiki befindet sich im Testbetrieb.

---

Aus Kefk.

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 1 Problem 2 Der Algorithmus 3 Ergebnis 4 Beispiel 5 Weblinks

Problem

Es existiert ein Stapel mit unbestimmt vielen Aufträgen A_n, die in einer optimalen Reihenfolge bezüglich der Durchlaufzeit auf genau zwei Maschinen / Prozessoren, M_j bearbeitet werden sollen.

Der Algorithmus

Das Problem kann mit folgender iterativer Vorschrift gelöst werden.

1. Suche den Auftrag A_i mit der absolut kürzesten Bearbeitungszeit
2. Entscheide:
   • Falls j = 1: Ordne den Auftrag A_i so weit vorn wie möglich in der Reihenfolge an
   • Falls j = 2: Ordne den Auftrag A_i so weit hinten wie möglich in der Reihenfolge an
3. fahre fort bei 1. solange bis jeder Auftrag zugeordnet ist.

Ergebnis

Der Johnson-Algorithmus liefert die Durchlaufzeit-optimale Reihenfolge der Aufträge.

Beispiel

Fünf Aufträge mit unterschiedlichen Bearbeitungszeiten auf den Maschinen M₁ und M₂ sollen Durchlaufzeit-optimal bearbeitet werden.

Die Folgende Tabelle gibt an, wie viel Zeit (in ZE) ein Auftrag A_i auf einer Maschine M_j 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 A₁ mit 3 ZE. Da A₁ auf M₂ (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 A₃ mit 7 ZE. Da A₃ auf M₁ 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

Weblinks

http://www.nist.gov/dads/HTML/johnsonsAlgorithm.html

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort Johnson-Algorithmus, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.