Flow Shop
Unter einem Flow Shop versteht man in der Maschinenbelegungsplanung eine Klasse von Problemen, bei denen n zu produzierende Aufträge, die aus m Arbeitsgängen bestehen, auf genau m Maschinen zu fertigen sind. Im Gegensatz zu Job-Shop-Problemen ist die Reihenfolge der Maschinen, auf denen die Aufträge bearbeitet werden müssen, für jeden Auftrag identisch. Es handelt sich also um Modellierungen von Produktionssystemen mit Fließproduktion. Bei einem Job Shop werden dagegen Produktionssysteme mit Werkstattfertigung modelliert. Bei normalen Flow-Shop-Problemen kann jeder Auftrag nach jeder Maschine beliebig lange gelagert werden und damit von nachfolgenden Aufträgen grundsätzlich auch überholt werden. In diesem Fall ist die Auftragsfolge auf den Maschinen unterschiedlich. Bei Permutations-Flow-Shops ist auch die Auftragsfolge auf jeder Maschine identisch – Aufträge können hier nicht überholt werden. Optimale Permutationspläne sind grundsätzlich einfacher zu finden. Kann man für ein bestimmtes Flow-Shop-Problem zeigen, dass sich unter den optimalen Maschinenbelegungen auch immer ein Permutationsplan findet, so kann man sich auf diese beschränken. Einige Probleme gehören zu den NP-schweren Problemen, andere sind jedoch noch in polynomialer Zeit zu lösen. Dies betrifft insbesondere speziellere Probleme wie [PF2| | ], also Permutations-Flow-Shops mit genau 2 Maschinen (Details zur Notation unter Klassifikation von Maschinenbelegungsmodellen). Weitere Typen von Maschinenbelegungsproblemen sind Job-Shop- und Open-Shop-Probleme, Maschinenbelegungsprobleme mit parallelen Maschinen oder Maschinenbelegungsproblem mit einer Maschine.[1]
Probleme mit zwei Maschinen
Flow-Shop-Probleme mit zwei Maschinen werden seit Ende der 1950er Jahre untersucht. Sie gehören zu den einfacheren Problemen, obwohl die meisten trotzdem zu den NP-schweren Problemen gehören. Johnson untersuchte den allgemeinen Fall [F2| |Z], der sich mit dem nach ihm benannten Johnson-Algorithmus mit einem Rechenaufwand von O(n log n) lösen lässt. Der Algorithmus betrachtet zunächst alle Aufträge, die auf der ersten Maschine eine kleinere Bearbeitungszeit haben als auf der zweiten. Diese werden nach aufsteigender Bearbeitungszeit der Reihe nach eingeplant. Danach werden die restlichen Aufträge nach fallender Bearbeitungszeit auf der zweiten Maschine sortiert und eingeplant. Bei [F3| |Z] ist der Johnson-Algorithmus anwendbar, falls die mittlere Maschine keinen Engpass darstellt. Dies ist der Fall, falls die kleinste Bearbeitungszeit auf der ersten oder letzten Maschine größer ist als die größte der zweiten Maschine. Man addiert jeweils die Bearbeitungszeiten der ersten beiden und die der letzten beiden Maschinen und erhält ein zwei-Maschinen-Problem, das, mit dem Johnson-Algorithmus gelöst, auch die optimale Belegung für das Drei-Maschinen-Problem liefert. Eine Abwandlung des Problems erlaubt die gleichzeitige Bearbeitung der Aufträge auf beiden Maschinen. Dies ist beispielsweise beim Lossplitting der Fall, bei dem die Aufträge aus Losen bestehen, die bereits nach teilweiser Fertigstellung an die nachfolgende Maschine weitergereicht werden. Dieses Problem lässt sich ebenfalls mit dem Johnson-Algorithmus lösen.[2]
Bei [F2||Z] werden reihenfolgeabhängige Rüstzeiten für das Rüsten von Auftrag j auf Auftrag k auf Maschine i berücksichtigt. Zur Zykluszeit zählt in diesem Fall auch die Rüstzeit dazu. Dieses Problem sowie das analoge Permutations-Problem sind NP-schwer. Sie lassen sich als verallgemeinertes Rundreiseproblem (Traveling Salesman Problem / TSP) betrachten. Für den Fall, dass nur eine Maschine vorhanden ist und alle Bearbeitungszeiten tj=0 gilt, ergibt sich genau das Standard-TSP, das bereits NP-schwer ist. Permutationspläne sind im Allgemeinen nicht optimal, diese können jedoch als obere Schranke dienen, falls man das Problem mit einem Branch-and-Bound-Algorithmus löst. Als untere Schranke bietet es sich an, jeweils nur eine Maschine zu betrachten und das entsprechende TSP zu lösen. Dazu wird ein zusätzlicher Auftrag mit Bearbeitungszeit null eingeführt. Die Entfernungen des TSP entsprechen der Summe aus Rüst- und Bearbeitungszeit. Die optimale Belegung für die isolierte Betrachtung der ersten Maschine stellt eine untere Schranke für Z dar, da nach Abarbeitung aller Aufträge auf der ersten Maschine noch mindestens ein Auftrag auf der zweiten zu bearbeiten ist. Entsprechend muss vor Bearbeitung des ersten Auftrags auf der zweiten Maschine mindestens ein Auftrag auf der ersten Maschine fertiggestellt sein, womit auch diese Zykluszeit für das Gesamtproblem nicht optimal sein kann.[3]
[F2|no wait|Z] stellt Spezialfall des TSP dar, der sich wegen der speziellen Struktur in polynomialer Zeit lösen lässt. Falls die erste Maschine bereits mit Auftrag i belegt ist, darf der folgende Auftrag k erst dann auf der erste Maschine fertiggestellt werden, wenn Auftrag i auf der zweiten Maschine fertig wird, da der Folgeauftrag sonst warten müsste. Für die Einträge der Entfernungsmatrix gilt cij:=max {tj2, tk1}.[4]
Das Problem [F2|aj|Z] ist ebenfalls NP-schwer. Eine Heuristik kombiert dabei den Johnson-Algorithmus und die dynamische Earliest-Due-Date-Regel, bei der der Auftrag als Nächstes eingeplant wird, der den frühesten Fertigstellungszeitpunkt hat.[5]
[F2|aj, nj|Z] ist auch NP-schwer. Gelöst wird es mittels Branch-and-Bound-Verfahren, bei denen entsprechende Probleme mit einer Maschine zur Erzeugung der Schranken dienen.[6]
Beim NP-schweren Problem [F2| |D] zur Minimierung der Durchlaufzeit existieren unter allen optimalen Lösungen auch immer welche mit Permutationsplänen, sodass man sich auf diese konzentrieren kann. Bei der Lösung orientiert man sich an Konzepten zur Lösung von [PF| |Z].[6]
Allgemeine Flow Shops
Bereits das Problem mit drei Maschinen ist NP-schwer. Heuristiken für normale Pläne beruhen meist auf Heuristiken zur Lösung von Job-Shop-Problemen. Für [PF| |Z] sind jedoch spezielle Heuristiken entwickelt worden. Sie versuchen den Johnson-Algorithmus zu verallgemeinern, indem sie Aufträge, die auf den ersten Maschinen relativ niedrige Bearbeitungszeiten haben, möglichst früh einplanen und solche mit relativ hohen auf den späteren Maschinen eher spät einplanen. Außerdem kann man versuchen, die Maschinen in zwei Gruppen zu teilen und die jeweiligen Bearbeitungszeiten addieren, um auf Zwei-Maschinen-Probleme zu kommen. Bessere Ergebnisse erhält man, wenn man alle m-1-Gruppierungen der Maschinen ausprobiert. Eine weitere Möglichkeit besteht darin, die Aufträge zunächst nach steigenden Summen der Bearbeitungszeiten zu sortieren und anschließend der Reihe nach in eine anfangs leere Liste einzuplanen. Die Aufträge werden dabei jeweils an der Position eingeplant, bei der die momentane Zykluszeit durch die Einplanung des weiteren Auftrags möglichst wenig steigt. Verbesserungsverfahren gehen von einem zulässigen Permutationsplan aus und versuchen durch Vertauschen oder Verschieben von Aufträgen die Lösung zu verbessern. Eine exakte Permutations-Lösung liefert das Verfahren von Ingall und Schrage, das mit dem Branch-and-Bound-Verfahren arbeitet.[7]
Siehe auch
Einzelnachweise
- Domschke, Scholl, Voß: Produktionsplanung: Ablauforganisatorische Aspekte. 2. Auflage, Springer, 1997, S. 285, 361 f.
- Domschke, Scholl, Voß: Produktionsplanung: Ablauforganisatorische Aspekte. 2. Auflage, Springer, 1997, S. 362–365.
- Domschke, Scholl, Voß: Produktionsplanung: Ablauforganisatorische Aspekte. 2. Auflage, Springer, 1997, S. 365–368.
- Domschke, Scholl, Voß: Produktionsplanung: Ablauforganisatorische Aspekte. 2. Auflage, Springer, 1997, S. 368 f.
- Domschke, Scholl, Voß: Produktionsplanung: Ablauforganisatorische Aspekte. 2. Auflage, Springer, 1997, S. 369.
- Domschke, Scholl, Voß: Produktionsplanung: Ablauforganisatorische Aspekte. 2. Auflage, Springer, 1997, S. 370.
- Domschke, Scholl, Voß: Produktionsplanung: Ablauforganisatorische Aspekte. 2. Auflage, Springer, 1997, S. 375–378.