www.wikidata.de-de.nina.az

Johnson Algorithmus Der ist ein Optimierungsverfahren für Warteschlangen das 1954 von Selmer M Johnson vorgestellt wurde

Johnson-Algorithmus

Der Johnson-Algorithmus ist ein Optimierungsverfahren für Warteschlangen, das 1954 von Selmer 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. Der Algorithmus lässt sich auf mehr als zwei Maschinen verallgemeinern, indem Hilfsprobleme erzeugt werden.

Der Algorithmus Bearbeiten

Optimale Maschinenbelegung

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

Beispiel: Fünf Aufträge mit unterschiedlichen Bearbeitungszeiten sollen Zykluszeit-optimal jeweils zuerst auf der Maschine und danach auf der Maschine bearbeitet werden. Die folgende Tabelle gibt an, wie viel Zeit (in ZE) ein Auftrag Ai auf einer Maschine benötigt.

A1 A2 A3 A4 A5
M1 14 12 7 13 11
M2 4 13 8 9 14

Alternative 1 Bearbeiten

Beschreibung der iterativen Vorschrift Bearbeiten

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

  1. Suche den Auftrag Ai mit der absolut kürzesten Bearbeitungszeit
  2. Entscheide:
    • Falls : Ordne den Auftrag so weit vorn wie möglich in der Reihenfolge an
    • Falls : Ordne den Auftrag 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 mit 4 ZE. Da auf 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 mit 7 ZE. Da auf am wenigsten Zeit benötigt, wird er in der neuen Reihenfolge so weit vorn wie möglich eingeordnet usw.

Beispiel zur iterativen Implementation Bearbeiten

Im Folgenden wird der Algorithmus anhand eines Beispiels demonstriert. Die Formatierungen haben folgende Bedeutung:

als kürzeste Laufzeit identifizierter Wert

bereits sequenzierter Auftrag

Der Startzustand umfasst eine zufällige Auftragsreihenfolge:

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

Zustand 1:

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

Zustand 2:

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

Zustand 3:

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

Zustand 4:

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

Zustand 5:

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

Zustand 6 (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.

Zustand 7 (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 Bearbeiten

  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 bilden die erste Gruppe. Die Sortierung nach der kürzesten Bearbeitungsdauer auf der Maschine M1 ergibt den ersten Teil der Lösung: .

Die zweite Gruppe enthält die Aufträge . Die Sortierung nach der längsten Bearbeitungsdauer auf der Maschine ergibt den zweiten Teil der Lösung: .

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

Literatur Bearbeiten

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

Weblinks Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Johnson Algorithmus ist ein Optimierungsverfahren fur Warteschlangen das 1954 von Selmer 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 Auftragen die jeweils auf genau zwei Maschinen nacheinander bearbeitet werden sollen Der Algorithmus lasst sich auf mehr als zwei Maschinen verallgemeinern indem Hilfsprobleme erzeugt werden Inhaltsverzeichnis 1 Der Algorithmus 1 1 Alternative 1 1 1 1 Beschreibung der iterativen Vorschrift 1 1 2 Beispiel zur iterativen Implementation 1 2 Alternative 2 2 Literatur 3 WeblinksDer Algorithmus Bearbeiten nbsp Optimale MaschinenbelegungEs existiert ein Stapel mit unbestimmt vielen Auftragen A n displaystyle A n nbsp die in einer optimalen Reihenfolge bezuglich der Zykluszeit auf genau zwei Maschinen Prozessoren M j displaystyle M j nbsp nacheinander bearbeitet werden sollen Beispiel Funf Auftrage mit unterschiedlichen Bearbeitungszeiten sollen Zykluszeit optimal jeweils zuerst auf der Maschine M 1 displaystyle M 1 nbsp und danach auf der Maschine M 2 displaystyle M 2 nbsp bearbeitet werden Die folgende Tabelle gibt an wie viel Zeit in ZE ein Auftrag Ai auf einer Maschine M j displaystyle M j nbsp benotigt A1 A2 A3 A4 A5M1 14 12 7 13 11M2 4 13 8 9 14Alternative 1 Bearbeiten Beschreibung der iterativen Vorschrift Bearbeiten Das Problem kann mit folgender iterativer Vorschrift gelost werden Suche den Auftrag Ai mit der absolut kurzesten Bearbeitungszeit Entscheide Falls j 1 displaystyle j 1 nbsp Ordne den Auftrag A i displaystyle A i nbsp so weit vorn wie moglich in der Reihenfolge an Falls j 2 displaystyle j 2 nbsp Ordne den Auftrag A i displaystyle A i nbsp so weit hinten wie moglich in der Reihenfolge an fahre fort bei 1 solange bis jeder Auftrag zugeordnet ist Der Johnson Algorithmus sucht sich jetzt den kurzesten Auftrag also A 1 displaystyle A 1 nbsp mit 4 ZE Da A 1 displaystyle A 1 nbsp auf M 2 j 2 displaystyle M 2 j 2 nbsp am wenigsten Zeit benotigt wird er in der neuen Reihenfolge so weit wie moglich hinten eingeordnet Der nachst kurzeste Auftrag ist A 3 displaystyle A 3 nbsp mit 7 ZE Da A 3 displaystyle A 3 nbsp auf M 1 displaystyle M 1 nbsp am wenigsten Zeit benotigt wird er in der neuen Reihenfolge so weit vorn wie moglich eingeordnet usw Beispiel zur iterativen Implementation Bearbeiten Im Folgenden wird der Algorithmus anhand eines Beispiels demonstriert Die Formatierungen haben folgende Bedeutung als kurzeste Laufzeit identifizierter Wertbereits sequenzierter AuftragDer Startzustand umfasst eine zufallige Auftragsreihenfolge x A1 A2 A3 A4 A5 A6 A7 A8M1 12 7 4 3 10 5 6 7M2 8 6 9 6 2 8 9 7Zustand 1 x A1 A2 A3 A4 A6 A7 A8 A5M1 12 7 4 3 5 6 7 10M2 8 6 9 6 8 9 7 2Zustand 2 x A4 A1 A2 A3 A6 A7 A8 A5M1 3 12 7 4 5 6 7 10M2 6 8 6 9 8 9 7 2Zustand 3 x A4 A3 A1 A2 A6 A7 A8 A5M1 3 4 12 7 5 6 7 10M2 6 9 8 6 8 9 7 2Zustand 4 x A4 A3 A6 A1 A2 A7 A8 A5M1 3 4 5 12 7 6 7 10M2 6 9 8 8 6 9 7 2Zustand 5 x A4 A3 A6 A7 A1 A2 A8 A5M1 3 4 5 6 12 7 7 10M2 6 9 8 9 8 6 7 2Zustand 6 Endzustand a x A4 A3 A6 A7 A1 A8 A2 A5M1 3 4 5 6 12 7 7 10M2 6 9 8 9 8 7 6 2Anmerkung Hier ware der Algorithmus theoretisch schon zu Ende bei einer Implementierung kann jedoch noch ein weiterer Zustand aufgrund verschiedener Elementsgrossenuberprufung angezeigt werden Zustand 7 Endzustand b x A4 A3 A6 A7 A8 A1 A2 A5M1 3 4 5 6 7 12 7 10M2 6 9 8 9 7 8 6 2Es gibt bei diesem Beispiel somit 2 richtige Ergebnisse Alternative 2 Bearbeiten Bilde eine Gruppe von Auftragen mit Bearbeitungszeit die auf der ersten Maschine kurzer sind als auf der zweiten Sortiere diese Gruppe aufsteigend nach der Bearbeitungszeit auf Maschine 1 Bilde eine zweite Gruppe mit restlichen Auftragen Sortiere sie absteigend nach der Bearbeitungszeit auf Maschine 2 Die Auftrage A 2 M 1 12 A 3 M 1 7 A 5 M 1 11 displaystyle A 2 M 1 12 A 3 M 1 7 A 5 M 1 11 nbsp bilden die erste Gruppe Die Sortierung nach der kurzesten Bearbeitungsdauer auf der Maschine M1 ergibt den ersten Teil der Losung A 3 A 5 A 2 displaystyle A 3 to A 5 to A 2 nbsp Die zweite Gruppe enthalt die Auftrage A 1 M 2 4 A 4 M 2 9 displaystyle A 1 M 2 4 A 4 M 2 9 nbsp Die Sortierung nach der langsten Bearbeitungsdauer auf der Maschine M 2 displaystyle M 2 nbsp ergibt den zweiten Teil der Losung A 4 A 1 displaystyle A 4 to A 1 nbsp Die durchlaufzeitoptimale Reihenfolge fur dieses Beispiel ist demnach A 3 A 5 A 2 A 4 A 1 displaystyle A 3 to A 5 to A 2 to A 4 to A 1 nbsp Die Abbildung Optimale Maschinenbelegung stellt die optimale Losung grafisch dar Literatur BearbeitenSelmer Martin Johnson Optimal two and three stage production schedules with setup times included In Naval Research Logistics Quarterly vol 1 iss 1 1954 S 61 68 Weblinks BearbeitenJohnson s Algorithm For Scheduling Ajay Joneja The Hong Kong University of Science and Technology Abgerufen von https de wikipedia org w index php title Johnson Algorithmus amp oldid 228148317