Entwicklung eines hybriden Algorithmus für die sequenzielle Optimierung der Reihenfolgen- und Maschinenbelegungsplanung

Abstract

Für Produktionsunternehmen stellen schwankende Nachfragen eine große Herausforderung dar, die eine wirtschaftlich effiziente Planung schwierig gestalten. Die klassischen Methoden, die einer schwankenden Nachfrage entgegenwirken, werden unter anderem als Produktionsglättung bezeichnet. Diese Methoden betrachten jedoch meist nur die Produktionsmengen, wodurch ausschlaggebende Faktoren und Kosten nicht berücksichtigt werden. Das Ziel dieser Diplomarbeit ist es, den Produktionsplan eines kunststoffverarbeitenden Unternehmens, der sich aus dem Absatzplan ergibt, bestmöglich zu glätten. Jedoch werden im Gegensatz zu den klassischen Methoden möglichst alle relevanten Kosten (Rüst-, Lager-, Verspätungs-, Betriebs- und Wartezeitkosten) und Restriktionen (Maschinen-, Werkzeug- und Rüstmitarbeiterbelegungen sowie ein vorgegebenes Rüstintervall) berücksichtigt, um einen umsetzbaren Produktionsplan mit möglichst geringen Gesamtkosten zu erzielen. Das Problem dieser Arbeit lässt sich durch folgende Fragestellung zusammenfassen: In welcher Reihenfolge und auf welcher Maschine müssen die Aufträge eingeplant werden, damit unter Berücksichtigung aller Restriktionen und Kosten minimale Gesamtkosten entstehen? Es liegt also ein Kombinatorikproblem vor, das durch die hohe Anzahl an Aufträgen und Maschinen einen zu großen Lösungsraum besitzt, wodurch das Durchrechnen aller möglichen Kombinationen nicht realisierbar ist. In diesem Fall kommen sogenannte Metaheuristiken zum Einsatz, die Probleme in der Praxis zwar oft nicht exakt lösen können, aber in angemessener Zeit eine zufriedenstellende Lösung finden. Eine bekannte Metaheuristiken ist der Genetische Algorithmus (GA), der zum Lösen der Maschinenbelegungsplanung in dieser Arbeit benutzt und in Matlab® umgesetzt wurde. Die Reihenfolgenplanung wird über einen Batchprozess vor dem Einsatz des GA definiert. Durch eine sehr aufwändige Anpassung des GA an die Problemstellung und dem Einsatz eines zeitintensiven Decodierungsprozesses konnten alle Restriktionen und Kosten berücksichtigt werden. Als Fundament wurde das Prinzip des Grouping Genetic Algorithm (GGA) benutzt. Zum Erstellen einer guten initialen Population mit einer möglichst hohen Diversität wurden Prinzipien aus der Greedy Randomized Adaptive Search Procedure (GRASP) Metaheuristik eingesetzt. Außerdem wurden bei erweiterten Auswertungen für die Erstellung der initialen Population sowie für die Selektion und den Crossover die Distanz zwischen Individuen aktiv berücksichtigt. Letztendlich wurde der GA dann mit einem Local Search (LS) kombiniert, wodurch eine weitere Reduzierung der Gesamtkosten erzielt werden konnte. Durch eine mögliche Parallelisierung in Matlab, konnte die Rechenzeit der zeitintensiven LS Vorgänge und Decodierungsprozesse in Grenzen gehalten werden. Die Untersuchung des Batchprozesses hat gezeigt, dass durch einen sinnvollen Batchprozess und die damit verbundene Reduktion des Lösungsraums, der GA deutlich bessere Ergebnisse findet, selbst wenn dadurch unter Umständen sehr gute Lösungen ausgeschlossen werden. Eine sinnvolle und gut durchdachte Reduktion des Lösungsraums kann somit für Probleme in der Praxis zielführend sein.

For manufacturing companies, fluctuating demands pose a major challenge that makes economically efficient planning difficult. The classical methods, which counteract a fluctuating demand, are called production smoothing methods. However, these methods usually only consider the production quantities, which does not take into account crucial factors and costs. The aim of this thesis is the production smoothing of a plastics processing company. However, in contrast to the classical methods, all relevant costs (setup, storage, delay, operating and waiting time costs) and constraints (assignment of machines, tools and setup employees as well as a specified setup interval) are taken into account in order to achieve a feasible production plan with low overall costs. The problem of this work can be summarized by the following question: In which order and on which machine do the orders have to be scheduled so that minimal total costs are incurred taking into account all restrictions and costs? So the considered problem is a combinatorial problem, whose solution space ist too vast due to the large number of jobs and machines, so that the calculation of all possible combinations is not feasible. In this case, so-called metaheuristics are used, which often can not find the exakt solution of a practical problem, but find a satisfactory solution in a reasonable time. A well-known metaheurist is the Genetic Algorithm (GA), which was used to solve the machine scheduling problem in this thesis and was implemented in Matlab®. The order sequence is defined via a batch process before the use of the GA. Due to a very time-consuming adaptation of the GA to the problem and the use of a decoding process, all restrictions and costs could be taken into account. As a foundation, the principle of the Grouping Genetic Algorithm (GGA) was used. To create a good initial population with a high diversity, principles from the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristics were used. Furthermore, in extended evaluations the distance between individuals was actively used for the creation of the initial population as well as for the selection and the crossover operator. Finally, the GA was then combined with a Local Search (LS), which further reduced overall costs. Through a possible parallelization in Matlab, the computation time of the time-consuming LS and decoding processes could be kept within limits. The examination of the batch process has shown that by a reasonable batch process and the resulting reduction of the solution space, the GA finds significantly better results, even if this may consequently exclude very good solutions. A meaningful and well thought-out reduction of the solution space can thus be effective for problems in practice.