Exact and metaheuristic approaches for the production leveling problem

Abstract

Im Rahmen dieser Diplomarbeit wird ein neues Problem im Gebiet der mittelfristigen Produktionsplanung eingeführt - das Production Leveling Problem. Dabei besteht die Aufgabe darin, Aufträge zu Produktionsperioden so zuzuteilen, dass die Auslastung der unterschiedlichen Perioden und Produktionsressourcen ausbalanciert wird. Außerdem sollen die Aufträge möglichst in jener Reihenfolge eingeplant werden, die von deren Priorität bestimmt wird. Das Production Leveling Problem ist ein wichtiger Zwischenschritt im mehrstufigen Prozess der Produktionsplanung, weil es dafür sorgt, dass möglichst ausgewogene Auftragsgruppen zum darauffolgenden Scheduling-Schritt gelangen. In dieser Arbeit wird zunächst ein formales Modell des Problems dargestellt und dessen Komplexität theoretisch analysiert. Als exakte Lösungsverfahren werden Mixed-IntegerProgramming und Constraint-Programming untersucht, welche optimale Lösungen für kleine Instanzen sowie untere Schranken beweisen sollen. Um auch große Probleminstanzen lösen zu können, werden in Folge Verfahren auf der Basis von metaheuristischer lokaler Suche erkundet. Dafür warden eine Greedy-Heuristik und zwei Nachbarschaftsstrukturen für die Lokale Suche eingeführt und die Verfahren Variable Neighborhood Descent und Simulated Annealing untersucht. Zur Evaluierung wird ein Set von realistischen Probleminstanzen eines Industriepartners veröffentlicht, sowie zwei zufallsbasierte Instanzgeneratoren. Die Forschungsfrage bezüglich der exakten Methoden ist, wie große Instanzen in einem fixen Zeitraum lösbar sind. Für die metaheuristischen Ansätze soll gezeigt werden, dass kleine Probleminstanzen annähernd optimal gelöst werden können und die Skalierbarkeit bis hin zu sehr großen Instanzen ebenfalls gegeben ist. Die wichtigsten theoretischen Ergebnisse dieser Arbeit stellen das formale Problemmodell sowie ein Beweis der NP-hardness dar, welche mittels Reduktion von Bin-Packing gezeigt wird. Die Evaluierung der Lösungsmethoden kommt zu dem Resultat, dass mithilfe von Mixed-Integer-Programming Instanzen mit bis zu 250 Aufträgen fast immer gelöst werden können, während bei größeren Instanzen meist keine Lösung gefunden wird. Von den untersuchten metaheuristischen Verfahren produziert Simulated Annealing die besten Resultate. Es wird gezeigt, dass kleine Instanzen, für die untere Schranken bewiesen werden konnten, mit durschnittlich weniger als 3% Optimality Gap gelöst werden können. Auf der anderen Seite sind aber auch die größten Instanzen mit tausenden Aufträgen und Dutzenden von Produktionsperioden in der Regel gut lösbar. Die vorgestellten metaheuristischen Verfahren wurden bereits in der Industrie zum Einsatz gebracht.

This thesis introduces the Production Leveling Problem, which is a new problem in the field of mid-term production planning. The task is to assign orders to production periods such that the workload in each period and on each production resource is balanced, capacity limits are not exceeded and the orders priorities are taken into account. The Production Leveling Problem is an important intermediate step between long-term planning and the final scheduling of orders within a production period, as it responsible for selecting good subsets of orders to be scheduled within each period. A formal model for the Production Leveling Problem is proposed and the theoretical complexity is analyzed. Mixed Integer Programming and Constraint Programming are investigated as exact methods for solving moderately sized instances of the problem. In order to be able to solve also large problem instances, metaheuristic local search is investigated. A greedy heuristic and two neighborhood structures for local search are proposed, in order to apply them using Variable Neighborhood Descent and Simulated Annealing. A set of realistic problem instances from an industrial partner is contributed to the literature, as well as random instance generators and the instances which were generated for evaluation. Regarding exact techniques, the main question of research is, how large instances can be while still being solvable within a fixed amount of time. For the metaheuristic approaches the aim is to show that they produce near-optimal solution for smaller instances, but also scale well to very large instances. The main theoretical results of this thesis are a formal model of the Production Leveling Problem and the proof of NP-hardness by reduction from Bin Packing. The experimental evaluation conveys that the proposed MIP model works well for instances with up to 250 orders, but soon hits a glass ceiling if they get larger. Out of the investigated metaheuristic approaches, Simulated Annealing achieves the best results. It is shown to produce solutions with less than 3% average optimality gap on small instances and to scale well up to thousands of orders and dozens of periods and products. The presented metaheuristic methods are already being actively used in the industry.