Ein heuristisches Dekompositionsverfahren für mehrstufige Losgrößenprobleme

Abstract

In der Arbeit wird ein heuristisches Verfahren zur Lösung von mehrstufigen kapazitätsbeschränkten Losgrößenproblemen entwickelt. Dies ist eine Abstraktion von operativen Produktionsplanungsproblemen. In der betrieblichen Praxis tritt dieses Problem immer dann auf, wenn die Produktion für den Bedarf nach Endprodukten und den abgeleiteten Bedarf nach Vorprodukten geplant werden muss und Ressourcen für die Produktion nur beschränkt zur Verfügung stehen. Es gehört zur Klasse der NP-harten Probleme. Der in der Arbeit vorgeschlagene heuristische Lösungsansatz basiert auf einer Zerlegung des mathematischen Modells für das mehrstufige kapazitätsbeschränkte Losgrößenproblem in Teilprobleme. Jedes Teilproblem ist durch ein Zeitfenster mit ganzzahligen Rüstvariablen charakterisiert. Dieses Zeitfenster rolliert über den Planungshorizont. Sofern das Zeitfenster von der ersten bis zur letzten Periode des Planungshorizontes rolliert, sind die Rüstvariablen hinter dem Zeitfenster relaxiert und die Rüstvariablen vor dem Zeitfenster werden auf die Werte aus vorhergehenden Optimierungen fixiert. Bei einem rückwärts rollierenden Zeitfenster sind die Rüstvariablen hinter den Zeitfenster fixiert und vor dem Zeitfenster relaxiert. Nach dem letzten Rollieren erhält man mit der Lösung des Teilproblems eine heuristische Lösung für das gesamte Problem. Um die Lösungsqualität der heuristischen Dekomposition zu verbessern, kann jedes Teilproblem durch zusätzliche Ungleichungen ergänzt werden, die für den Lösungsraum des gesamten Problems zulässig sind. Den Teilmodellen wurden die aus der Literatur bekannten (l,S)-Ungleichungen und Mixed-Integer-Rounding- Inequalities hinzugefügt. Zudem wurden die Teilmodelle um Restriktionen ergänzt, die die Rüstanzahl nach unten beschränken oder solchen, die sich aus Überlegungen zu Restkapazitäten ergeben. Sofern Rüstzeiten vorhanden sind, kann in den Perioden, in denen die Rüstvariablen relaxiert sind, die Kapazität angepasst werden, um die Unterschätzung der Rüstzeit in diesen Perioden zu berücksichtigen. Verfahrensvarianten ergeben sich durch die Hinzunahme von Ungleichungen zum Teilmodell, der Lösungsreihenfolge der Teilmodelle sowie im Fall von Rüstzeiten durch die Kapazitätsanpassung. Die Verfahrensvarianten wurden an Hand von über 600 Testproblemen untersucht. Für alle Testprobleme, für die zulässige Lösungen bekannt waren, wurden mit der Heuristik zulässige Lösungen erzeugt. Mit bestimmten Varianten der Heuristik konnte das Optimum oder eine sehr gute Lösung für die Testprobleme gefunden werden. Für viele Testprobleme, für die keine optimalen Lösungen bekannt sind, konnten durch die Heuristik die besten bekannten Lösungen verbessert werden.

In this thesis a heuristic decomposition approach for the multi-stage capacitated lot-sizing problem is developed. This problem is an important problem for production planning as it determines lot-sizes and lays the foundation for subsequent processes as detailed scheduling and material requirements planning. It is also well-known to be NP-hard. The proposed approach decomposes the mathematical model of the problem into subproblems. Each subproblem is characterised by a time window. Within this time window the setup variables are binary as in the original problem. The time window rolls over the planning horizon. If the time window rolls forward, variables before the time window are fixed to the values obtained in previously solved subproblems, whereas variables after the time window are relaxed. If the time window rolls backward, the opposite applies to the variables outside the time window. For problems without setup times this procedure with either forward or backward rolling time window guarantees a feasible solution to the problem at hand. The solution quality of this approach can be increased by adding valid inequalities for the whole problem to each sub-problem. (l,S)- and Mixed- Integer-Rounding-Inequalities, which are well-known from literature, have proven to be especially successful. Also, restrictions on the minimum number of setups or capacity excess constraints can tighten the problem formulation. In problems with setup times the capacity consumption is underestimated due to the linearised variables. It has proven valuable to introduce correction factors to anticipate this behaviour. Different variants of this approach were tested with more than 600 well-known test instances. Solutions were found to all test instances where feasible solutions were known as well as to some previously unsolved ones. For many test instances which presently cannot be solved to optimality new best solutions were obtained with the heuristic decomposition approach.