Ablaufplanung: Flow Shop mit $n$ Aufträgen und $m$ Produktionsstufen, NEH-Heuristik
Bei Reihenproduktion sind die Ressourcen dem Arbeitsplan der Produkte entsprechend angeordnet. Alle Produkte besuchen die Ressourcen in derselben Reihenfolge. Die Bearbeitungszeiten an den einzelnen Produktionsstufen (Maschinen, Arbeitsplätze, stationen) sind deterministisch bekannt, können aber von Produkt zu Produkt unterschiedlich sein. Es geht jetzt darum, die Einlastungsreihenfolge der Produkt so zu bestimmen, daß die Zykluszeit (makespan), d.h. der Zeitraum zwischen dem Beginn der Bearbeitung des ersten Produkts an der ersten Station und dem Ende der Bearbeitung des letzten Produkts an der letzten Station minimal wird.
Beispiel: Es werden unbearbeitete Produkte für einen vorliegenden Kundenauftrag angeliefert. Diese Produkte werden in einem mehrstufigen Produktionsprozeß verarbeitet und sollen dann soll schnell wie möglich als Gesamtheit, d.h. mit einer einmaligen Lieferung, an den wartenden Kunden ausgeliefert werden.
Für die Bestimmung der Einlastungsreihenfolge der Aufträge bei Reihenproduktion gibt es verschiedene Verfahren, deren Anwendbarkeit u.a. von der Anzahl der Produktionsstufen abhängt.
Besonders bekannt ist das exakte Verfahren von Johnson, das die zykluszeitminimale Reihenfolge für $n$ Aufträge an 2 Maschinen bestimmt. Dieses ist jedoch auf die Situation mit 2 Maschinen beschränkt. Unter bestimmten Annahmen kann man es auch für 3 Maschinen einsetzen. Für mehr als 3 Maschinen bzw. Produktionsstufen sind zahlreiche heuristische Verfahren vorgeschlagen wurde.
Eines dieser Verfahren, das dieselbe Problemstellung wie das Verfahren von Johnson, allerdings für eine beliebige Anzahl von Maschinen löst, die die NEH-Heuristik (nach den Namen der Autoren Nawaz, Enscore, und Ham). Zielsetzung ist wieder die Minimierung der Zykluszeit (makespan). In der Zykluszeit sind Wartezeiten der Aufträge vor ihrer Bearbeitung an der Maschine 1 und nach ihrer Bearbeitung an der letzten Maschine $m$ mit enthalten. Es wird also einen geschlossene Auftragsankunft und eine geschlossene Auftragsweitergabe angenommen.
In diesem Modul die NEH-Heuristik implementiert. Die Aufträge können zum Zeitpunkt 0 eingeplant werden. Alle Aufträge haben dieselbe Maschinenfolge, die der Indizierung der Maschinen enspricht.
Die NEH-Heuristik läuft wie folgt ab:
Die Berechnung der Zykluszeit verlangt die Nachbildung des zeitlichen Produktionsablaufs und geht wie folgt, wobei die Indizes $i$ die aktuelle Reihenfolge beschreiben:
Ein Beispiel findet man hier.
Ansichten:
- Domschke/Scholl/Voß (1997)
- Nawaz, M., Enscore, M.M., und I. Ham, A heuristic algorithm for the m-machine, n-job flow-shop sequencing
problem, in: OMEGA 11(1983), S. 91-95
Datenschutz | © 2021 POM Prof. Tempelmeier GmbH | Imprint