Weintritt, W. (2020). Solving the paintshop scheduling problem with memetic algorithms [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2020.80201
Das Paint-Shop-Schedling-Problem, abgekürzt PSSP, ist ein kürzlich vorgestelltes praxisnahes Planungsproblem. Das Ziel dieses Problems ist es, einen optimierten Zeitplan für das Lackieren von Autoteilen zu finden. Autoteile, welche lackiert werden sollen, werden auf Trägervorrichtungen platziert. Die Träger werden wiederum mittels Förderband in die Lackiererei transportiert, wo mehrere Lackierroboter die Autoteile lackieren. Das PSSP ist ein anspruchsvolles NP-hartes Problem. Beim Erstellen des Zeitplans müssen weitere Bedingungen beachtet werden, beispielsweise die vorhandenen Materialien und Träger, verbotene Träger- und Farbfolgen, Fälligkeitstermine, usw. Für viele der Probleminstanzen wurden noch keine optimalen Ergebnisse gefunden. Die bestehende wissenschaftliche Literatur für das PSSP befasst sich mit exakten Lösungsverfahren und lokaler Suche. Allerdings wurden noch keine evolutionären Algorithmen zur Lösung des PSSP herangezogen. In dieser Diplomarbeit stellen wir einen memetischen Algorithmus zur Lösung des PSSP vor. Unser Algorithmus folgt der typischen Vorlage eines memetischen Algorithmus. Es wird zuerst eine initiale Bevölkerung generiert, gefolgt von stetiger Evolution. Selektions-, Rekombinations-, Mutations- und lokale Verbesserungsoperatoren werden auf jede Generation der Bevölkerung angewandt. Wir stellen drei neuartige Rekombinationsoperatoren vor, welche mit problemspezifischem Wissen arbeiten. Abschließend konfigurieren wir unseren Algorithmus mittels automatischem und manuellem Parametertuning. Für die experimentelle Analyse unseres Algorithmus verwenden wir öffentlich verfügbare Probleminstanzen. Unser memetischer Algorithmus generiert konkurrenzfähige Lösungen für kleine und mittelgroße Probleminstanzen. Wir schaffen es für 8 der 24 Instanzen neue obere Schranken zu finden.
de
The Paint Shop Scheduling Problem is a recently introduced real-life scheduling problem from the automotive industry. Car parts, which need to be painted, are placed upon carrier devices. These carriers are placed on a conveyor belt and moved into painting cabins, where painting robots paint the parts. The aim is to find an optimized production schedule for the painting of car parts. The Paint Shop Scheduling Problem is a challenging NP-hard problem that imposes constraints like due dates, forbidden carrier and color sequences, maximum and minimum block lengths, and material availability. While the problem has been tackled in literature, there are many problem instances for which the optimal solutions are still unknown. Existing literature is focused on solving the Paint Shop Scheduling Problem with exact and local search approaches. However, population-based algorithms have not yet been applied to solve this problem. In this thesis, we propose a memetic algorithm to solve the Paint Shop Scheduling Problem. Our algorithm follows the typical template of a memetic algorithm. An initial population is generated, followed by the constant evolution of generations. Selection, crossover, mutation, and local improvement operators are applied in each generation. We design three novel crossover operators that consider problem-specific knowledge. Finally, we carefully configure our algorithm, including automated and manual parameter tuning. Using a set of available real-life benchmark instances from the literature, we perform an extensive experimental evaluation of our algorithm. The experimental results show that our memetic algorithm yields competitive results for small- and medium-sized instances and is able to set new upper bounds for some of the problem instances.
