Effiziente Lösungsansätze für mehrstufige Losgrößenprobleme mit Kapazitätsrestriktionen

Florian Sahling

Im Fokus steht hier das dynamische mehrstufige Losgrößenproblem mit Kapazitätsrestriktionen (MLCLSP, engl.: Multi-Level Capacitated Lotsizing Problem). Das MLCLSP und Modellerweiterungen sind NP-schwer. Aus diesem Grund scheitern Standardmethoden der mathematischen Programmierung bei der Lösung realistischer Probleme häufig an der Rechenzeit. Zur Lösung derartiger Probleme wird daher häufig auf heuristische Lösungsansätze zurückgegriffen, deren Einsatz in möglichst kurzer Rechenzeit sehr gute Ergebnisse in der Nähe des Optimums versprechen.

Am Institut für Produktionswirtschaft ist daher die sog. Fix-and-Optimize-Heuristik zur Lösung des MLCLSP entwickelt worden, bei der das Ausgangsproblem iterativ in Unterprobleme zerlegt wird. Die Optimierung dieser Unterprobleme erfolgt mit dem Solver CPLEX. Numerische Ergebnisse haben gezeigt, dass dieser Ansatz zur Lösung unterschiedlicher mehrstufiger Losgrößenprobleme mit Kapazitätsrestriktionen sehr gut geeignet ist. Dabei zeichnet sich dieser Ansatz durch seine hohe Lösungsgüte bei akzeptabler Rechenzeit aus. Darüber hinaus lässt sich die Heuristik im Gegensatz zu anderen Verfahren auch sehr gut auf Modellerweiterungen und -modifikationen anpassen.

Weitere Informationen:

• Institut für Produktionswirtschaft
• Helber, S. und Sahling, F. (2010): A Fix-and-Optimize Approach for the Multi-Level Capacitated Lot Sizing Problem. In: International Journal of Production Economics (123) 2010, S. 247 - 256.
• Sahling, F. (2010): Mehrstufige Losgrößenplanung bei Kapazitätsrestriktionen. Produktion und Logistik, Wiesbaden (Gabler).
• Sahling, F.; Buschkühl, L.; Helber, S. und Tempelmeier, H. (2009): Solving a multi-level capacitated lot sizing problem with multi-period setup carry-over via a fix-and-optimize heuristic. In: Computers & Operations Research (36), S. 2546 - 2553.