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

[Bearbeiten] 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.

[Bearbeiten] 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

1. 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 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

[Bearbeiten] Weblinks

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