title: Reihenfolge- und Maschinenbelegungsplanung für eine Klasse von Flexible Flow Shop Problemen
title: Flexible Flow Shop Scheduling
titleType: AlternativeTitle
Creators: name: Stalinski, David
Publisher: name: Bergische Universität Wuppertal
Year: 2022

description: Die logistische Leistung eines produzierenden Unternehmens beschreibt dessen Fähigkeit, kurze Lieferzeiten zu realisieren und zugesagte Liefertermine gegenüber seinen Kunden einzuhalten. Die Termintreue als logistisches Primärziel wird in der operativen Produktionsplanung und -steuerung u.a. durch die Ablaufplanung – also durch die Maschinenbelegung sowie durch die Reihenfolgebildung – beeinflusst. Bei der Erstellung von Produktionsplänen liegt in der Regel ein hohes Potenzial in der Optimierung der Abläufe sowie in der Vermeidung von Verschwendungen. In vielen Unternehmen werden diese Planungsaufgaben historisch bedingt noch manuell durch entsprechende Planer durchgeführt. Diese stützen sich dabei auf ihre Erfahrungen und entscheiden demnach nach bestem Wissen und Gewissen. Im Zeitalter der Automatisierung und Digitalisierung wird die Aufgabe der Ablaufplanung zunehmend der Informationstechnik und damit dem Computer zugesprochen. Für die Entwicklung der entsprechenden Entscheidungs- und Entscheidungsunterstützungssysteme sind in der Regel komplexe mathematische Optimierungsprobleme zu lösen. Die Anzahl der Kombinationsmöglichkeiten und damit die benötigte Rechenzeit für eine vollständige Enumeration wächst exponentiell mit der Problemgröße (kombinatorische Explosion). Probleme dieser Art haben daher gemein, dass selbst vermeintlich kleine Aufgabenstellungen sich als praktisch nicht exakt lösbar herausstellen. Im Rahmen der vorliegenden Arbeit wird ein Verfahren für die simultane Reihenfolge- und Maschinenbelegungsplanung für eine Klasse von Flexible Flow Shop Problemen entwickelt. Das Verfahren soll in Bezug auf das Laufzeit- und Lösungsverhalten den Anforderungen für den Einsatz in Entscheidungsunterstützungssystemen realer Produktionen genügen. Flexible Flow Shop Probleme bezeichnen in der Theorie der Ablaufplanung mehrstufige Produktionsprozesse, bei denen jede Stufe aus mindestens einer Maschine besteht und jeder Fertigungsauftrag mindestens in einer der Produktionsstufen bearbeitet werden muss. Flexible Flow Shop Probleme gibt es in nahezu unzähligen Varianten, welche sich wesentlich durch die Ausprägung der Maschinenumgebung sowie die zu berücksichtigenden Restriktionen unterscheiden. Die in dieser Arbeit behandelten Probleme werden durch die im folgenden Absatz zusammengefassten Restriktionen charakterisiert. Ein Teil der Fertigungsaufträge muss einzelne Stufen überspringen und kann technologisch bedingt nicht an allen Maschinen bearbeitet werden. Es sind reihenfolgeabhängige Rüstzeiten zu berücksichtigen, wobei sich die Fertigungsaufträge in eine oder mehrere Auftragsfamilien pro Stufe zusammenfassen lassen. Manche Fertigungsaufträge müssen innerhalb einer Stufe zusammenhängend und am Stück auf derselben Maschine bearbeitet werden. Weiterhin sollen begrenzte Rohmaterialien und Lagerkapazitäten berücksichtigt werden, so dass die Planungsergebnisse praktisch umsetzbar sind. Die Entwicklung des Verfahrens beruht auf mehreren Ansätzen. Durch die zeitliche Diskretisierung des Planungshorizonts in gleichmäßige Planungsperioden wird das Problem bzw. dessen Suchraum zunächst in eine definierte Struktur transformiert. Dadurch wird die Komplexität auf ein definiertes Niveau reduziert und die Manipulation des Modells durch herkömmliche kombinatorische Optimierungsverfahren wird ermöglicht. Die Ableitung von konkreten Ergebnissen in Form von Produktionsplänen für eine bestimmte Kombination wird algorithmisch durch eine ereignisdiskrete Simulationsmethode in einem mathematischen Verfahren hinterlegt. Das entwickelte Verfahren wird einer umfangreichen numerischen Untersuchung unterzogen, um es in Bezug auf die benötigte Rechenzeit sowie die erzielbare Lösungsqualität zu bewerten. Dafür werden zwei standardisierte Optimierungsalgorithmen – ein Ameisenalgorithmus sowie ein Genetischer Algorithmus – implementiert und mit dem Modell gekoppelt. Für beide Optimierungsalgorithmen werden die entsprechenden Verfahrensparameter für unterschiedliche Problemgrößen in statistisch abgesicherten Untersuchungen systematisch variiert und damit optimiert. Die Leistungsfähigkeit der jeweiligen Optimierungsalgorithmen kann damit für unterschiedliche Problemgrößen verglichen werden, so dass eine entsprechende Auswahl erfolgen kann. Das Modell kann dadurch mit optimierten Parametern auf unterschiedliche Probleminstanzen und -größen angewendet werden, um die Einflüsse weiterer Parameter des Verfahrens zu untersuchen. Anhand einer Fallstudie in Form eines konkreten Industriebeispiels wird das Verfahren anschließend auf Datensätze angewandt, welche auf realen Daten eines produzierenden Unternehmens aus der holzverarbeitenden Industrie basieren. Die Produktion ist hochgradig automatisiert und bietet eine qualitativ hochwertige Datengrundlage, welche u.a. auf den Einsatz der RFID-Technik für sekundengenaue Buchungs- und Steuerungsprozesse zurückzuführen ist. Für die rechnerbasierte Unterstützung der operativen Produktionsplanung und -steuerung wurde das Verfahren dort in Form eines Entscheidungssystems implementiert. Es greift dabei auf gesammelte Daten aus einem Zeitraum von mehreren Jahren zurück, um z.B. statistisch abgesicherte Informationen über zu erwartende Produktionszeiten zu generieren. Das System unterstützt die Produktionsleitung bei der Planung und Steuerung der Produktion und hat sich seit der Implementierung erfolgreich etabliert.
description: The logistical performance of a producing company describes its ability to realize short delivery times and meet the promissed delivery dates towards its customers. A great adherence to schedule as a logistic objective is affected within the operative production planning and control by specifying machine allocations and processing sequences. Thus, the process of composing production schedules normally offers high potentials in optimizing the production processes and avoiding waste of time. In many companies these planning processes are still done manually for historical reasons. The schedulers often trust in their experience and take decisions based on the best of their knowledge. In the digital age the task of scheduling falls more and more into the remit of information technology and should therefore be done by computers. In order to develop appropriate decision and decision support systems complex mathematical problems in the form of combinatorial optimization problems need to be solved. The amount of combinatorial possibilities and thus the needed amount of computation time for a full enumeration grows exponential with the problem size (combinatorial explosion). This type of problems is characterised by the fact that even small problem instances are practically not solvable in an exactly way. This thesis deals with the development of a method for the simultaneous calculation of production sequences and machine allocations of a flexible flow shop problem. The method has to comply the requirements of computation times and solution quality for being implemented into decision support systems in real processing companies. In the theory of scheduling flexible flow shop problems designate multi-stage production processes in which each stage consists of at least one machine and each production order must be processed in at least one of the production stages. There are flexible flow shop problems in almost countless variants which differ significantly in the form of the constraints to be taken into account. Solution strategies and approaches cut accordingly for use for special problem types. The problems dealt with in this work are characterized by the restrictions and constraints summarized in the following paragraph. Some of the production orders have to skip some of the stages and cannot be processed on all machines for technological reasons. There are sequent dependent set up times to be taken into account whereby the production orders are classified into one or more families per stage. Some manufacturing orders have be processed simultaniously and in one piece on the same machine. Furthermore the available raw materials and storage capacities must be taken into account during the planning process, so that the planning results are practically feasible. The development of the method is based on several approaches. The problem respectively its search space is initially transformed by dividing the planning horizon by a time grid. This reduces the complexity to a defined level and the manipulation of the model by conventional combinatorial optimization procedures is made possible. The generation of concrete solutions in the form of production plans for a certain combination is algorithmically implemented into the mathematical model as an event discrete simulation. The developed model is subjected to an extensive numerical examination in order to evaluate it in terms of the required computing time and the achievable solution quality. For this, the two standardized optimization algorithms – the ant colony algorithm and the genetic algorithm – are implemented and linked to the model. For both algorithms the corresponding process parameters are examined for different problem sizes in statistically verified studies. Thus, the model can be applied to different problem instances and sizes with optimized Parameters. Based on a case study in the form of a concrete industrial example the method is then applied to data records based on real data from a manufacturing company in the woodworking industry. The production is highly automated and uses the RFID technology for precise booking and control processes. Thus, it already offers a high quality data basis. For a computer-based support of the operational production planning and control the developed method was implemented in the form of a decision system. It uses collected data of several years back to generate e.g statistically verified information about expected production times of the manufacturing orders. The system supports the production management in the planning and control of the production and is successfully settled since its implementation.