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.
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.
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.
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.
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 
zugeordnet. Alle anderen der Menge 
. In unserem Beispiel werden also die Aufträge 1 und 4 der Gruppe und die Aufträge 2,3 und 5 der Gruppe zugeordnet.
Schritt 2 – Sortierung
Im 2. Schritt sortieren wir die Aufträge. Aufträge der Menge werden nach aufsteigender Bearbeitungszeit auf Station 1 sortiert, die Menge von nach absteigender Bearbeitungszeit auf Station 2. Somit ergeben sich folgende Reihenfolgen innerhalb der Blöcke: In : erst Auftrag 1 dann Auftrag 4 und in : Auftrag 3, Auftrag 5 und Auftrag 2.
Schritt 3 – Verkettung
Im 3. Schritt verketten wir die beiden Blöcke. und 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.