Economics at your fingertips  

An O(T3) algorithm for the capacitated lot sizing problem with minimum order quantities

Irena Okhrin and Knut Richter

European Journal of Operational Research, 2011, vol. 211, issue 3, 507-514

Abstract: 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(T3) 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.

Keywords: Production; planning; Capacitated; lot; sizing; problem; Single; item; Minimum; order; quantities; Capacity; constraints; Dynamic; programming (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11) Track citations by RSS feed

Downloads: (external link)
Full text for ScienceDirect subscribers only

Related works:
Working Paper: An O(Tˆ3) algorithm for the capacitated lot sizing problem with minimum order quantities (2010) Downloads
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link:

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Haili He ().

Page updated 2021-01-14
Handle: RePEc:eee:ejores:v:211:y:2011:i:3:p:507-514