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.
Studyflix vernetzt: Hier ein Video aus einem anderen Bereich
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.
Moores – und Johnson-Algorithmus — häufigste Fragen
(ausklappen)
Moores – und Johnson-Algorithmus — häufigste Fragen
(ausklappen)-
Was besagt die Johnson-Regel der Terminplanung?Die Johnson-Regel der Terminplanung legt fest, wie man Aufträge für zwei Stationen zu einer Reihenfolge kombiniert, damit die Gesamtdauer (Durchlaufzeit bis zum letzten Auftrag) minimal wird. Man teilt die Aufträge in zwei Gruppen und sortiert die erste nach kleinen Zeiten auf Station 1 und die zweite nach großen Zeiten auf Station 2.
-
Für welche 2-Maschinen-Probleme darf man den Johnson-Algorithmus anwenden?Den Johnson-Algorithmus darf man bei 2-Maschinen-Flow-Shop-Problemen anwenden, bei denen jeder Auftrag genau zweimal bearbeitet wird und zwar immer zuerst auf Station 1 und danach auf Station 2. Außerdem muss man dieselbe Auftragsreihenfolge auf beiden Stationen einhalten und feste Bearbeitungszeiten annehmen.
-
Wie funktioniert der Moore-Algorithmus?Den Moore-Algorithmus führt man aus, indem man die Aufträge zuerst nach ihren Fälligkeitsterminen sortiert und daraus die Fertigstellungszeitpunkte und Verspätungen berechnet. Sobald der erste verspätete Auftrag auftaucht, nimmt man aus allen bis dahin betrachteten Aufträgen den mit der längsten Bearbeitungszeit heraus und legt ihn in Liste B. Man wiederholt das, bis in Liste A keine Verspätung mehr steht.
-
Was macht man am Ende des Moore-Algorithmus mit den Aufträgen aus Liste B?Die Aufträge aus Liste B hängt man am Ende des Moore-Algorithmus einfach an die Reihenfolge aus Liste A an, damit eine vollständige Auftragsreihenfolge entsteht. Die Reihenfolge innerhalb von Liste B ist dabei beliebig, weil das Ziel nur ist, die Anzahl verspäteter Aufträge zu minimieren, nicht die Höhe der Verspätung.
Ablaufplanung verstehen
Der Moore’s und der Johnson-Algorithmus gehören zur Ablaufplanung in der Produktion und sind typische Verfahren der Reihenfolgeplanung. Du ordnest in diesem Themenfeld Aufträge nach klaren Regeln und vergleichst Bearbeitungszeiten, Fertigstellungszeitpunkte und Maschinenfolgen. So wird verständlich, wie unterschiedliche Ziele wie kurze Durchlaufzeiten oder wenige verspätete Aufträge die Reihenfolge von Aufträgen verändern. Im Wirtschaftsbereich findest du passende Videos zu diesem und verwandten Themen.
