Johnson-Algorithmus


Johnson-Algorithmus

Der Johnson-Algorithmus ist ein Optimierungsverfahren für Warteschlangen, das 1954 von S. M. Johnson vorgestellt wurde. Es findet unter anderem bei der Reihenfolgeplanung zur Bestimmung der minimalen Zykluszeit in der Produktionswirtschaft Anwendung.

Der Johnson-Algorithmus liefert eine hinsichtlich der Zykluszeit optimale Reihenfolge von unbestimmt vielen Aufträgen, die jeweils auf genau zwei Maschinen nacheinander bearbeitet werden sollen.

Inhaltsverzeichnis

Der Algorithmus

Optimale Maschinenbelegung

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

Beispiel: Fünf Aufträge mit unterschiedlichen Bearbeitungszeiten auf den Maschinen M1 und M2 sollen Zykluszeit-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 4 13 8 9 14

Alternative 1

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

  1. Suche den Auftrag Ai mit der absolut kürzesten Bearbeitungszeit
  2. 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
  3. fahre fort bei 1. solange bis jeder Auftrag zugeordnet ist.

Der Johnson-Algorithmus sucht sich jetzt den kürzesten Auftrag, also A1 mit 4 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.

Beispiel zur iterativen Implementation

Beispiel:

Startzustand:

x A1 A2 A3 A4 A5 A6 A7 A8
M1 12 7 4 3 10 5 6 7
M2 8 6 9 6 2 8 9 7

Zustand1:

x A1 A2 A3 A4 A6 A7 A8 A5
M1 12 7 4 3 5 6 7 10
M2 8 6 9 6 8 9 7 2

Zustand2:

x A4 A1 A2 A3 A6 A7 A8 A5
M1 3 12 7 4 5 6 7 10
M2 6 8 6 9 8 9 7 2

Zustand3:

x A4 A3 A1 A2 A6 A7 A8 A5
M1 3 4 12 7 5 6 7 10
M2 6 9 8 6 8 9 7 2

Zustand4:

x A4 A3 A6 A1 A2 A7 A8 A5
M1 3 4 5 12 7 6 7 10
M2 6 9 8 8 6 9 7 2

Zustand5:

x A4 A3 A6 A7 A1 A2 A8 A5
M1 3 4 5 6 12 7 7 10
M2 6 9 8 9 8 6 7 2

Zustand6 (Endzustand a):

x A4 A3 A6 A7 A1 A8 A2 A5
M1 3 4 5 6 12 7 7 10
M2 6 9 8 9 8 7 6 2

Anmerkung: Hier wäre der Algorithmus theoretisch schon zu Ende, bei einer Implementierung kann jedoch noch ein weiterer Zustand aufgrund verschiedener Elementsgrößenüberprüfung angezeigt werden.

Zustand7 (Endzustand b):

x A4 A3 A6 A7 A8 A1 A2 A5
M1 3 4 5 6 7 12 7 10
M2 6 9 8 9 7 8 6 2


Es gibt bei diesem Beispiel somit 2 richtige Ergebnisse.

Alternative 2

  1. Bilde eine Gruppe von Aufträgen mit Bearbeitungszeit, die auf der ersten Maschine kürzer sind, als auf der zweiten.
    • Sortiere diese Gruppe aufsteigend nach der Bearbeitungszeit auf Maschine 1.
  2. Bilde eine zweite Gruppe mit restlichen Aufträgen.
    • Sortiere sie absteigend nach der Bearbeitungszeit auf Maschine 2.

Die Aufträge A2 (M1=12), A3 (M1=7), A5 (M1=11) bilden die erste Gruppe. Die Sortierung nach der kürzesten Bearbeitungsdauer auf der Maschine M1 ergibt den ersten Teil der Lösung: A3A5A2.

Die zweite Gruppe enthält die Aufträge A1 (M2=4), A4 (M2=9). Die Sortierung nach der längsten Bearbeitungsdauer auf der Maschine M2 ergibt den zweiten Teil der Lösung: A4A1.

Die durchlaufzeitoptimale Reihenfolge für dieses Beispiel ist demnach: A3A5A2A4A1. Die Abbildung „Optimale Maschinenbelegung“ stellt die optimale Lösung grafisch dar.

Literatur

  • S. M. Johnson. Optimal two- and three-stage production schedules with setup times included. In: Naval Research Logistics Quarterly, vol.1, iss.1, 1954

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Johnson — bezeichnet: Johnson (Familienname), siehe dort Namensträger und Etymologie Johnson ist der Name folgender Unternehmen Howard Johnson s, US amerikanische Hotelkette Johnson Johnson, US amerikanischer Kosmetikahersteller und Pharmakonzern Johnson… …   Deutsch Wikipedia

  • Kürzester Weg — Unter einem kürzesten Pfad versteht man in der Graphentheorie einen Pfad zwischen zwei Knoten u und v, welcher minimale Länge hat. Haben die Kanten im Graphen alle das gleiche Kantengewicht, so ist der kürzeste Pfad äquivalent zu dem Pfad mit den …   Deutsch Wikipedia

  • SSSP — Unter einem kürzesten Pfad versteht man in der Graphentheorie einen Pfad zwischen zwei Knoten u und v, welcher minimale Länge hat. Haben die Kanten im Graphen alle das gleiche Kantengewicht, so ist der kürzeste Pfad äquivalent zu dem Pfad mit den …   Deutsch Wikipedia

  • Shortest-Path — Unter einem kürzesten Pfad versteht man in der Graphentheorie einen Pfad zwischen zwei Knoten u und v, welcher minimale Länge hat. Haben die Kanten im Graphen alle das gleiche Kantengewicht, so ist der kürzeste Pfad äquivalent zu dem Pfad mit den …   Deutsch Wikipedia

  • Shortest Path — Unter einem kürzesten Pfad versteht man in der Graphentheorie einen Pfad zwischen zwei Knoten u und v, welcher minimale Länge hat. Haben die Kanten im Graphen alle das gleiche Kantengewicht, so ist der kürzeste Pfad äquivalent zu dem Pfad mit den …   Deutsch Wikipedia

  • Kürzester Pfad — Ein kürzester Pfad ist in der Graphentheorie ein Pfad zwischen zwei Knoten, welcher minimale Länge hat. Haben die Kanten im Graphen alle das gleiche Kantengewicht, so ist der kürzeste Pfad äquivalent zu dem Pfad mit den wenigsten Knoten. Sollten… …   Deutsch Wikipedia

  • Zeitablaufsteuerung — Unter Scheduling (englisch für „Zeitplanerstellung“), auch Zeitablaufsteuerung genannt, versteht man die Erstellung eines Ablaufplanes (schedule), der Prozessen zeitlich begrenzt Ressourcen zuweist (Allokation). Scheduling findet hauptsächlich in …   Deutsch Wikipedia

  • Scheduling — Unter Scheduling (englisch für „Zeitplanerstellung“), auch Zeitablaufsteuerung genannt, versteht man die Erstellung eines Ablaufplanes (schedule), der Prozessen zeitlich begrenzt Ressourcen zuweist (Allokation). Scheduling findet hauptsächlich in …   Deutsch Wikipedia

  • Botenproblem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein… …   Deutsch Wikipedia

  • Euklidisches Traveling-Salesman-Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein… …   Deutsch Wikipedia