Heuristische Optimierungsverfahren für das Blocking Flow Shop Scheduling Problem mit flexiblen Maschinenübergängen

In dieser Masterarbeit wird ein Produktionsplanungsproblem aus der Praxis betrachtet, um effiziente Optimierungsmethoden zur Berechnung von Lösungen zu entwickeln. Die dahinterstehende Problematik bezieht sich auf die Kombination von zwei Eigenschaften, welche in dieser gemeinsamer Form in der Literatur noch kaum betrachtet wurden: einerseits die sogenannte „No-Buffer“ oder auch „Blocking“ Nebenbedingung, andererseits flexible Maschinenübergänge mit der Möglichkeit Teile von Bearbeitungsschritten zwischen den Maschinen zu verschieben.Nach einer Analyse eines aus einer Vorgängerarbeit vorhandenen ganzzahligen linearen Programms (ILP) zur Lösung dieses Problems, wird der Fokus auf das Design und die Implementierung von heuristischen Methoden zur Berechnung annähernd optimaler Lösungen gelegt. Den Hauptteil dieser wissenschaftlichen Arbeit bildet die Entwicklung alternativer Lösungsalgorithmen. Dazu wurden die Ergebnisse der Analyse der Lösungsstrukturen aus den ILP-Modellen genützt.Basierend auf ausführlichen Literaturstudien werden unterschiedliche Ansätze für heuristische Methoden vorgestellt, implementiert und analytisch miteinander verglichen. Hierzu werden grundsätzlich zwei Kombinationsvarianten von verschiedenen heuristischen Verfahren definiert und implementiert, welche sich in der Eignung bezüglich der Komplexität von Problemszenarien unterscheiden.Die Implementierung des ganzzahligen linearen Programms sowie der teilweise angepassten Heuristiken in einer Form, welche eine zukünftige Bearbeitung des Themas für Dritte erleichtert, stellen zusätzliche Aspekte dieser Masterarbeit dar. Als Ergebnis werden die Erkenntnisse bei der Anwendung der heuristischen Algorithmen interpretiert und Aussagen zu Ihrer Praxisfähigkeit getätigt. Schlussendlich wird ein Ausblick auf weitere interessante Forschungsfragen in dieser Thematik durchgeführt.This master thesis covers a specific production planning problem arising from a practical application. The main goal is the development of efficient optimization methods for calculating solutions.The combination of two properties, which are barely considered in a joint way within scientific literature, constitutes the main part of the underlying problem. These properties are the so-called „No-Buffer“ or „Blocking“ constraints and flexible machine transitions, which allow the possibility of shifting parts of the workload of single production steps between machines.As a first step, an analysis of an integer linear programming model (ILP), which is already existing from a previous work is conducted. With the therefrom gained insights, the focus is set on the design and implementation of heuristic methods for calculating approximately optimal solutions. The analysis of the problem from a different perspective and the inclusion of alternative solutions, especially regarding heuristics, form the main part of this scientific work. Based on extensive literature studies, different heuristic methods are implemented and analyzed for the further design of two variants of combinations to solve the underlying problem. The numerical analysis shows that these two approaches differ in their suitability regarding the complexity of certain problem scenarios.The implementation of the integer linear program as well as of the adapted heuristics in such a form that others may use it in their future work on the topic, are additional targets of this master thesis. As a result, insights about the application of heuristic methods are analyzed with respect to their practicability. Finally, an outlook on further interesting research questions on this topic is given.Arbeit an der Bibliothek noch nicht eingelangt - Daten nicht geprüftAbweichender Titel laut Übersetzung des Verfassers/der VerfasserinKarl-Franzens-Universität Graz, Masterarbeit, 2020(VLID)486857