fdb – Forschungsdatenbank der Europa-Universität Viadrina Frankfurt (Oder)


Prof. Dr. Dr. h. c. Knut Richter: An O(T^3) Algorithm for the Capacitated Lot Sizing Problem with Minimum Order Quantities

Projektleitung Prof. Dr. Dr. h. c. Knut Richter
Time span 01/2009 - 03/2011
Fakultät Wirtschaftswissenschaftliche Fakultät
Lehrstuhl Juniorprofessur in Information & Operations Management


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.


Drittmittelgeber Eigenfinanzierung EUV
Finanzierungsart University budget (100%)


Internationales Projekt Nein