Home

NEH-Heuristik

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:

  1. Bestimme für jeden Auftrag $i$ die Summe der Bearbeitungszeiten an allen Maschinen $m=1,2,...,M$:

    $T_i =\sum_{m=1}^{M} a_{im}$

    und sortiere die Aufträge absteigend nach diesem Kriterium.
  2. Setze $\ell=2$. Nimm die Aufträge mit den Rängen $1$ und $2$ und bestimme die Zykluszeit für die Reihenfolgen $\{1,2\}$ und $\{2,1\}$. Fixiere die (partielle) Reihenfolge mit der geringsten Zykluszeit (makespan): $\pi^\ell=\{\pi(1),\pi(2)\}$
  3. Setze $\ell=\ell+1$. Nimm den nächsten Auftrag mit dem Rang $\ell$ und füge ihn der Reihe nach in jede Position der Reihenfolge $\pi^{\ell-1}$ (im vorhergehenden Schritt ermittelt) ein. Wenn die optimale Reihenfolge z.B. $4-3-5-2$ ist und man den Auftrag 1 einfügen will, dann erhält man:
    (1-4-3-5-2), (4-1-3-5-2), (4-3-1-5-2), (4-3-5-1-2), (4-3-5-2-1)
    Bestimme für jede Reihenfolge die Zykluszeit und fixiere die (partielle) Reihenfolge mit der kürzesten Zykluszeit.
  4. Falls $\ell=P$ (Anzahl Aufträge) STOP; andernfalls gehe zu Schritt 3.

Die Berechnung der Zykluszeit verlangt die Nachbildung des zeitlichen Produktionsablaufs und geht wie folgt, wobei die Indizes $i$ die aktuelle Reihenfolge beschreiben:

  1. Auftrag i kann an Maschine j erst beginnen, wenn er an Maschine j-1 beendet wurde:
    START(i,j) >= ENDE(i,j-1) alle i,j
  2. Maschine j kann mit Auftrag i erst beginnen, wenn der Auftrag i-1 auf dieser Stufe beendet wurde:
    START(i,j) >= ENDE(i-1,j) alle i,j
  3. Das Bearbeitungsende des Auftrags i auf Stufe j ergibt sich aus dem Bearbeitungsbeginn zuzüglich der Rüstzeit und der Bearbeitungszeit:
    ENDE(i,j) = START(i,j) + a(i,j) alle i,j
  4. F(0,j) = 0
  5. F(i,0) = 0

Ein Beispiel findet man hier.

Ansichten:

Literatur:

- 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