Local search algorithms for scheduling vehicles in cyclic flexible manufacturing systems

Das Problem des Scheduling von Jobs und Maschinen in flexiblen Produktionssystemen wurde bereits in einer großen Anzahl an wissenschaftlichen Papers in vielen Variationen behandelt. Eine der großen Herausforderungen hierbei ist, dass schon relativ einfache Variationen der auftretenden Probleme NP-vollständig sind. Während die meisten Papers versuchen, die Jobs optimal auf den Maschinen anzuordnen, sucht diese Arbeit einen Lösungsansatz aus einer anderen Perspektive: Der Zeitplan der Jobs auf den Maschinen wird als gegeben angenommen, nur die Anzahl und die Startzeiten der Transportfahrzeuge können verändert werden. Zusätzlich zur Bedingung, dass die Jobs in einer vorgegebenen Reihenfolge bearbeitet werden müssen, dürfen die Transportfahrzeuge nur einem vorgegebenen Kurs folgen, welcher zu allen Maschinen in der Reihenfolge, in der die Jobs verarbeitet werden, führt. Schließlich kehren die Maschinen wieder zum Depot zurück und starten eine neue Runde. Zur Lösungsfindung wird eine Heuristik verwendet: eine iterative lokale Suche für eine zweidimensionale Zielfunktion zur Minimierung der Laufzeit und der Anzahl an Transportfahrzeugen. Diese Heuristik wird dann in zwei Varianten angewandt, mit jeweils unterschiedlichen Perturbationsphasen. Zusätzlich zur Heuristik wird ein Brute-Force-Algorithmus zur Lösung einer Testinstanz verwendet, damit die Ergebnisse und die Laufzeiten der Heuristik mit einem Ansatz, der die Optimallösung erhält, verglichen werden können. Die Heuristikvariationen und der Brute-Force-Algorithmus wurden in Python implementiert.The problem of scheduling jobs and machines in flexible manufacturing systems has been addressed in a vast amount of complex variations in scientific papers. One of the big issues in this category of problems is, that even very basic variations of the problems connected with such systems are NP-complete. Most papers focus on trying to schedule the jobs on the machines optimally. This thesis tries to approach the underlying problem from an entirely different perspective: The schedule of jobs at each stage is considered given, only the amount and starting times of transportation vehicles can be varied. In addition to the constraint of the jobs being in a set order, the transportation vehicles are only allowed to follow a set circuit, visiting all the machines in the order in which the jobs need to be processed, in order to finally return to the depot and start a new lap. For the means of solving this problem, a heuristical approach is made: an Iterative Local Search for a two-dimensional objective function minimizing the amount of machines and the makespan. This heuristic is then applied in two ways, withdifferences in the perturbation phase. In addition to the general heuristical approach, a Brute Force algorithm is used to solve a test case, enabling a comparison between the solutions and run-times of the heuristics and an approach that returns the optimal solution. The heuristic variations and the brute force algorithm were implemented using Python.Martin Gutjahr, BScAbweichender Titel laut Übersetzung des Verfassers/der VerfasserinZusammenfassungen in Deutsch und EnglischKarl-Franzens-Universität Graz, Masterarbeit, 2017(VLID)224605