Optimization of unpaced synchronous production lines
Final Report Abstract
Das Projekt “Optimierung ungetakteter synchroner Produktionsanlagen” behandelte die Optimierung von Planungsproblemen für ungetaktete Produktionsanlagen mit synchronem Transport. Zunächst wurde das Basisproblem als synchroner Flowshop modelliert und eingehend theoretisch analysiert. Es zeigte sich, dass die Minimierung der Produktionsdauer bereits für drei Maschinen streng NP-schwierig ist. Für andere Zielfunktionen wurde ebenfalls die Komplexität geklärt, dabei konnten für einige Spezialfälle auch polynomiale Algorithmen entwickelt werden. Durch Gespräche mit Praktikern und unter Einbeziehung bestehender Literatur wurden als relevante Erweiterungen des Basisproblems dominierende Maschinen, freiwillige Leerlaufzeiten, Ressourcen mit Rüstzeiten sowie flexible Prozesszeiten identifiziert. Dabei entspricht die Minimierung der Produktionsdauer im Falle zweier dominierender Maschinen einem Tourenplanungsproblem mit einer speziellen Distanz-Matrix. Während das Problem mit einer Tour bereits gut untersucht und effizient lösbar ist, haben wir im Rahmen des Projekts das Problem mit mehreren Touren (Vehicle Routing Problem) modelliert. Obwohl dieses Problem streng NP-schwierig ist, konnten wir sehr gute Näherungslösungen und untere Schranken berechnen. Von besonderem Interesse waren rotierende Anlagen mit synchronem Transport, bei denen Ressourcen benötigt werden, deren Wechsel zu Rüstzeiten führt. Dazu klassifizierten wir die entstehenden synchronen Flowshop-Probleme zunächst nach der Art der Job-Ressourcen-Beziehungen und bzgl. der Rüstzeiten. Unser Hauptaugenmerk galt dabei dem in der Praxis relevanten Fall, dass durch die Ressourcen sog. “Job-Familien” definiert werden, wobei zwei Jobs genau dann zur gleichen Familie gehoren, wenn sie von den gleichen Ressourcen bearbeitet werden können. Es zeigte sich, dass dieses Problem bereits für zwei Maschinen streng NP-schwierig ist. Jedoch konnten wir nachweisen, dass Teilprobleme (z.B. die alleinige Minimierung der Rüstzeiten) in polynomialer Zeit lösbar sind. Durch diese Erkenntnisse konnten wir Dekompositionsverfahren entwickeln, welche vor allem für praxisnahe Probleme und reale Daten sehr gute Ergebnisse liefern. Motiviert durch Weiterqualifikation von Mitarbeitern und den Einsatz flexibler Maschinen untersuchten wir die Erweiterung, dass einzelne Operationen nicht mehr fix einzelnen Maschinen (Mitarbeitern) zugewiesen werden, sondern die benötigte Prozesszeit flexibel verteilt werden darf. Wir zeigten, dass für eine gegebene Produktionsreihenfolge die beste Verteilung der Prozesszeiten in polynomialer Zeit gefunden werden kann. Unter Ausnutzen dieses Ergebnisses wurde ein heuristisches Verfahren entwickelt, welches zu Produktionsplänen mit deutlich geringerer Gesamtproduktionsdauer als im nicht-flexiblen Fall führt. In einer theoretischen Analyse stellte sich heraus, dass auch der Einsatz freiwilliger Leerlaufzeiten prinzipiell überraschend große Verbesserungen der Zielfunktionswerte möglich macht. Dagegen zeigte eine praktische Rechenstudie, dass die erzielten Verbesserungen oft nur relativ gering sind und sich vermutlich der zusätzliche Aufwand, in den Verfahren freiwillige Leerlaufzeiten einzufügen, nicht lohnt. Im Projekt wurde eine große Nähe zu anderen bekannten Fragestellungen der kombinatorischen Optimierung (z.B. mehrdimensionale Zuordnungsprobleme, Tourenplanungsprobleme) deutlich. Durch die Betrachtung der Produktionsplanungsprobleme konnten auch in diesen Bereichen neue Erkenntnisse gewonnen werden. Die im Projekt erzielten theoretischen Ergebnisse und Optimierungsalgorithmen wurden in einschlägigen Zeitschriften im Bereich des Operations Research und Scheduling veröffentlicht.
Publications
- (2015): Complexity results for flow shop problems with synchronous movement, European Journal of Operational Research 242, 34-44
S. Waldherr, S. Knust
(See online at https://doi.org/10.1016/j.ejor.2014.09.053) - (2016): Decomposition algorithms for synchronous flow shop problems with additional resources and setup times, European Journal of Operational Research
S. Waldherr, S. Knust
(See online at https://doi.org/10.1016/j.ejor.2016.11.015) - (2016): Open shop scheduling with synchronization, Journal of Scheduling
C. Weiß, S, Waldherr, S. Knust, N.V. Shakhlevich
(See online at https://doi.org/10.1007/s10951-016-0490-0) - (2016): Solution algorithms for synchronous flow shop problems with two dominating machines, Computers & Operations Research 74, 42-52
M. Kampmeyer, S. Knust, S. Waldherr
(See online at https://doi.org/10.1016/j.cor.2016.04.010) - (2016): Synchronous flow shop problems: How much can we gain by leaving machines idle? Omega
S. Waldherr, S. Knust, D. Briskorn
(See online at https://doi.org/10.1016/j.omega.2016.10.006) - (2016): The assignment problem with nearly Monge arrays and incompatible partner indices, Discrete Applied Mathematics 211, 183-203
C. Weiß, S. Knust, N.V. Shakhlevich, S. Waldherr
(See online at https://doi.org/10.1016/j.dam.2016.04.019)
