Video anzeigen

Moores – und Johnson-Algorithmus

Du fragst dich was der Moore’s und der Johnson Algorithmus sind? Perfekt, denn genau das erklären wir dir in diesem Beitrag.

Du möchtest lieber hören statt lesen? Dann schau dir direkt unser Video an.

Inhaltsübersicht

Ablaufplanung: Johnson Algorithmus 

Du hängst immer noch an der Ablaufplanung und weißt einfach nicht, wie du den optimalen Belegungsplan für eine oder zwei Maschinen finden kannst? Keine Sorge, das erklären wir dir jetzt.
Im vorherigen Video haben wir uns die Prioritätsregelverfahren angeschaut. Darauf aufbauend dreht sich jetzt alles um den Moore`s – und den Johnson Algorithmus.

Moore’s Algorithmus 

Machen wir uns als erstes an den Moore`s Algorithmus. Dieser dient dazu, die Anzahl an Verspätungen zu minimieren.
Das Vorgehen ist dabei in vier Schritte gegliedert. Diese schauen wir uns am Beispiel von Armbanduhren genauer an.
Nehmen wir an, du hast fünf Aufträge j für verschiedene Uhren, die du produzieren sollst, eine Bearbeitungsdauer p von j von jeweils 3,5,2,7,3 und einen spätesten Fertigstellungszeitpunkt d von i von jeweils 7,10,3,11,13.

Schritt 1 – Intitialisierung

Schritt eins ist die Initialisierung. Das bedeutet, dass die Aufträge entsprechend der Earliest Due Date Regel sortiert werden. Hierfür ist es wichtig, dass du verstanden hast, wie die EDD-Regel funktioniert. Solltest du hier noch Probleme haben, dann schau dir nochmal unser vorheriges Video zu den Prioritätsregelverfahren an. Bei Anwendung der EDD-Regel ergibt sich folgende Tabelle.

Schritt des Moors Algorithmus
direkt ins Video springen
Schritt 1: Initialisierung

Soweit so gut. In der letzten Spalte der Tabelle siehst du die jeweiligen Verspätungen. Wir wählen den ersten verspäteten Auftrag aus. In unserem Beispiel also Auftrag 4.

Schritt 2 – Auswahl

In Schritt 2 wählen wir dann von allen Aufträgen, die nicht nach dem ersten verspäteten Auftrag beginnen, den aus, der die längste Bearbeitungszeit hat. Jetzt fragst du dich vielleicht, warum wir das machen? Weil dieser Auftrag die Bearbeitung aller anderen Aufträge am meisten verzögert. In unserem Beispiel ist das zufällig wieder der Auftrag 4 mit einer Bearbeitungszeit von 7 Zeiteinheiten.

Schritt zwei des Moore Algorithmus
direkt ins Video springen
Schritt 2: Auftrag auswählen

Es ist allerdings nicht immer so, dass der erste verspätete Auftrag auch der mit der längsten Bearbeitungszeit ist.

Schritt 3 – Auftrag entfernen

Im dritten Schritt entfernen wir den ausgewählten Auftrag 4 dann aus unserer Auftragsliste A und bilden eine zweite Liste B für diesen Auftrag. Für den Fall, dass wir noch mehr Aufträge aussortieren sollten, kommen diese auch in die Liste B. In unserer Liste A hat jeder Auftrag, der nach dem entnommenen Auftrag beginnt, nun einen neuen Fertigstellungszeitpunkt. Warum? Naja wir haben ja einen Auftrag entnommen und die anderen Aufträge können somit früher bearbeitet werden.

Schritt des Moore Algorithmus
direkt ins Video springen
Schritt 3: Auftrag entfernen

Die Verspätung bei Auftrag 5 beträgt jetzt nicht mehr 7 Stunden, sondern liegt bei 0. In unserem Beispiel ist also bereits nach der ersten Anwendung des Moore`s Algorithmus keine Verspätung mehr in Liste A und wir können somit direkt zu Schritt 4 weitergehen. Sollten noch Verspätungen vorhanden sein, wiederholen wir Schritt 2 und 3 und entfernen wieder den Auftrag mit der längsten Bearbeitungszeit und fügen ihn in die Liste B ein. Die optimale Lösung besteht dann aus der Reihenfolge der Liste A, an die die Aufträge aus Liste B beliebig angehängt werden.
In unserem Beispiel sieht das dann so aus: J ist 3,1,2,5,4 p von j ist 2,3,5,3,7, d von j ist 3,7,10,13,11, C von J ist 2,5,10,13,20 und dementsprechend sind die Verspätungen 0,0,0,0,9

Johnson Algorithmus 

Weiter geht’s mit dem Johnson Algorithmus. Stell dir vor, du hast wieder fünf verschiedene Aufträge Uhren zu produzieren. Jeder Auftrag muss jetzt allerdings immer auf zwei Maschinen bearbeitet werden, bevor er fertig ist. Die optimale Produktionsreihenfolge dafür können wir jetzt mit dem Johnson-Algorithmus bestimmen.
Die Aufträge für deine Uhren sind durchnummeriert mit J gleich 1,2,3,4,5 und haben eine Bearbeitungszeit auf Station 1 p von j gleich 2,3,8,4,9 und auf Station 2 von 5,1,6,7,5. Zunächst schauen wir uns nur die ersten beiden Aufträge an.

Johnson Algorithmus - Flow-Shop Problem
direkt ins Video springen
Johnson Algorithmus – Flow-Shop Problem

Wir haben hier ein sogenanntes Flow-shop-Problem. Das bedeutet, dass alle Aufträge N in der selben Reihenfolge auf M Maschinen bearbeitet werden. In unserem Beispiel muss ein Auftrag immer erst auf Station 1 bearbeitet werden, bevor er auf Station 2 geleitet werden kann. Deshalb gibt es genau vier Möglichkeiten die Aufträge anzuordnen. Wir wissen also, dass die Lösung bei unserem Problem eine Permutationslösung sein muss. Daher muss die optimale Lösung der n! Permutationen bestimmt werden. Die vier Möglichkeiten sind:

1.Auf Station 1 und Station 2 jeweils zuerst J1 dann J2
2.Auf Station 1 und 2 jeweils zuerst J2 dann J1
3. Auf Station1 zuerst J2 dann J1 und auf Station 2 erst J1 dann J2 und..
4. Auf Station1 zuerst J1 dann J2 und auf Station 2 erst J2 dann J1.

Schritt 1 – Johnson Algorithmus – Initialisierung

Schritt 1 ist die Initialisierung: hier werden die Aufträge, deren Bearbeitungszeit auf Station 1 kleiner oder gleich der Bearbeitungszeit von Station 2 ist, der Menge Q_1 zugeordnet. Alle anderen der Menge Q_2. In unserem Beispiel werden also die Aufträge 1 und 4 der Gruppe Q_1 und die Aufträge 2,3 und 5 der Gruppe Q_2 zugeordnet.

Schritt 1 des Johnson Algorithmus
direkt ins Video springen
Schritt 1 des Johnson Algorithmus

Schritt 2 – Sortierung

Im 2. Schritt sortieren wir die Aufträge. Aufträge der Menge Q_1 werden nach aufsteigender Bearbeitungszeit auf Station 1 sortiert, die Menge von Q_2 nach absteigender Bearbeitungszeit auf Station 2. Somit ergeben sich folgende Reihenfolgen innerhalb der Blöcke: In Q_1: erst Auftrag 1 dann Auftrag 4 und in Q_2: Auftrag 3, Auftrag 5 und Auftrag 2.

Johnson Algorithmus - Aufträge sortieren
direkt ins Video springen
Johnson Algorithmus – Aufträge sortieren

Schritt 3 – Verkettung

Im 3. Schritt verketten wir die beiden Blöcke. Q_1 und Q_2 werden also miteinander verbunden. Als Ergebnis erhalten wir die optimale Lösung. In unserem Fall also 1,4,3,5,2 mit den Stationswerten S1 gleich 2,4,8,9,3 und S2 gleich 5,7,6,5,1.
So, jetzt weißt du wie du auch für zwei Maschinen einen optimalen Belegungsplan erstellen kannst.

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte .