An O(T3) algorithm for the capacitated lot sizing problem with minimum order quantities
Irena Okhrin and
European Journal of Operational Research, 2011, vol. 211, issue 3, 507-514
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)
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
Working Paper: An O(Tˆ3) algorithm for the capacitated lot sizing problem with minimum order quantities (2010)
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:211:y:2011:i:3:p:507-514
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 ().