An O(Tˆ3) algorithm for the capacitated lot sizing problem with minimum order quantities

Irena Okhrin and Knut Richter

No 284, Discussion Papers from European University Viadrina Frankfurt (Oder), Department of Business Administration and Economics

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 suffcient solvability conditions and apply the general dynamic programming technique to develop an O(T³) 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: 2010
New Economics Papers: this item is included in nep-cmp
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.econstor.eu/bitstream/10419/41404/1/623985543.pdf (application/pdf)

Related works:
Journal Article: An O(T3) algorithm for the capacitated lot sizing problem with minimum order quantities (2011)
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: https://EconPapers.repec.org/RePEc:zbw:euvwdp:284

Access Statistics for this paper

More papers in Discussion Papers from European University Viadrina Frankfurt (Oder), Department of Business Administration and Economics Contact information at EDIRC.
Bibliographic data for series maintained by ZBW - Leibniz Information Centre for Economics ().