imported>Invisigoth67: form

2022-11-20T16:10:34Z

form

Neue Seite

Der '''Johnson-Algorithmus''' ist ein Optimierungsverfahren für Warteschlangen, das 1954 von [[Selmer M. Johnson]] vorgestellt wurde. Es findet unter anderem bei der [[Scheduling|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 ==
[[Datei:Johnson-verfahren.png|miniatur|400px|Optimale Maschinenbelegung]]

Es existiert ein Stapel mit unbestimmt vielen Aufträgen <math>A_n</math>, die in einer optimalen Reihenfolge bezüglich der [[Zykluszeit (Produktion)|Zykluszeit]] ''auf genau zwei'' [[Maschine]]n / [[Prozessor]]en <math>M_j</math> nacheinander bearbeitet werden sollen.

Beispiel: Fünf Aufträge mit unterschiedlichen Bearbeitungszeiten sollen Zykluszeit-optimal jeweils zuerst auf der Maschine <math>M_1</math> und danach auf der Maschine <math>M_2</math> bearbeitet werden. Die folgende Tabelle gibt an, wie viel Zeit (in ZE) ein Auftrag ''Ai'' auf einer Maschine <math>M_j</math> benötigt.
{| class="wikitable"
!
!align="center"| ''A1''
!align="center"| ''A2''
!align="center"| ''A3''
!align="center"| ''A4''
!align="center"| ''A5''
|-
!valign="middle" | ''M1''
|align="center" | 14
|align="center" | 12
|align="center" | 7
|align="center" | 13
|align="center" | 11
|-
!valign="middle" | ''M2''
|align="center" | 4
|align="center" | 13
|align="center" | 8
|align="center" | 9
|align="center" | 14
|-
|}

=== Alternative 1 ===
==== Beschreibung der iterativen Vorschrift ====
Das Problem kann mit folgender [[Iteration|iterativer]] Vorschrift gelöst werden:

# Suche den Auftrag ''Ai'' mit der absolut kürzesten Bearbeitungszeit
# Entscheide:
#* Falls <math>j=1</math>: Ordne den Auftrag <math>A_i</math> so weit '''vorn''' wie möglich in der Reihenfolge an
#* Falls <math>j=2</math>: Ordne den Auftrag <math>A_i</math> so weit '''hinten''' wie möglich in der Reihenfolge an
# fahre fort bei 1. solange bis jeder Auftrag zugeordnet ist.

Der Johnson-Algorithmus sucht sich jetzt den kürzesten Auftrag, also <math>A_1</math> mit 4 ZE. Da <math>A_1</math> auf <math>M_2 (j=2)</math> 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 <math>A_3</math> mit 7 ZE. Da <math>A_3</math> auf <math>M_1</math> am wenigsten Zeit benötigt, wird er in der neuen Reihenfolge so weit vorn wie möglich eingeordnet usw.

==== Beispiel zur iterativen Implementation ====

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:
{| class="wikitable"
|- class="hintergrundfarbe5"
|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:
{| class="wikitable"
|- class="hintergrundfarbe5"
|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:
{| class="wikitable"
|- class="hintergrundfarbe5"
|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:
{| class="wikitable"
|- class="hintergrundfarbe5"
|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:
{| class="wikitable"
|- class="hintergrundfarbe5"
|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:
{| class="wikitable"
|- class="hintergrundfarbe5"
|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):
{| class="wikitable"
|- class="hintergrundfarbe5"
|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):
{| class="wikitable"
|- class="hintergrundfarbe5"
|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 ===
# 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.
# Bilde eine zweite Gruppe mit restlichen Aufträgen.
#* Sortiere sie '''absteigend''' nach der Bearbeitungszeit auf Maschine 2.

Die Aufträge <math>A_2 (M_1=12), A_3 (M_1=7), A_5 (M_1=11)</math> bilden die erste Gruppe. Die Sortierung nach der kürzesten Bearbeitungsdauer auf der Maschine ''M1'' ergibt den ersten Teil der Lösung: <math>A_3\to A_5\to A_2</math>.

Die zweite Gruppe enthält die Aufträge <math>A_1 (M_2=4), A_4 (M_2=9)</math>. Die Sortierung nach der längsten Bearbeitungsdauer auf der Maschine <math>M_2</math> ergibt den zweiten Teil der Lösung: <math>A_4\to A_1</math>.

Die durchlaufzeitoptimale Reihenfolge für dieses Beispiel ist demnach: <math>A_3\to A_5\to A_2\to A_4\to A_1</math>. Die Abbildung „Optimale Maschinenbelegung“ stellt die optimale Lösung grafisch dar.

== Literatur ==
* 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 ==
* [https://ieda.ust.hk/dfaculty/ajay/courses/ieem513/GT/johnson.html Johnson's Algorithm For Scheduling] Ajay Joneja, The Hong Kong University of Science and Technology

[[Kategorie:Maschinenbelegungsplanung]]
[[Kategorie:Betriebssystemtheorie]]
[[Kategorie:Optimierungsalgorithmus]]

Johnson-Algorithmus - Versionsgeschichte

imported>Invisigoth67: form