Banner Viadrina

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).

Zum Forschungsbericht der Juniorprofessur