An O(T^3) Algorithm for the Capacitated Lot Sizing Problem with Minimum Order Quantities
Juniorprofessur:
Juniorprofessur in Information & Operations Management
Projekttitel:
An O(T^3) Algorithm for the Capacitated Lot Sizing Problem with Minimum Order Quantities
Projektleitung:
Prof. Dr. Dr. h. c. Knut Richter
Projektart: Lehrstuhlprojekt
Finanzierung: Eigenfinanzierung EUV
Projektbeginn: 01.01.2009
Projektende: 31.03.2011
Projektbeschreibung in englisch:
This paper explores a single-item capacitated lot sizing problem with minimum order quantity, which plays the role of minor set-up cost. We work out the necessary and sufficient solvability conditions and apply the general dynamic programming technique to develop an O(T^3) exact algorithm that is based on the concept of minimal sub-problems. An investigation of the properties of the optimal solution structure allows us to construct explicit solutions to the obtained sub-problems and prove their optimality. In this way, we reduce the complexity of the algorithm considerably and confirm its efficiency in an extensive computational study.
Publikationen:
An O(T^3) algorithm for the capacitated lot sizing problem with minimum order quantities, European Journal of Operational Research 211, 507--514, 2011 (mit K. Richter).
An O(T^3) algorithm for the capacitated lot sizing problem with minimum order quantities, Working Paper 284, European University Viadrina Frankfurt (Oder), 2010, ISSN: 1860 0921 (mit K. Richter).