Improved Algorithms for a Lot-Sizing Problem with Inventory Bounds and Backlogging

Hark-Chin Hwang and Wilco van den Heuvel

No EI 2010-17, Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute

Abstract: This paper considers a dynamic lot-sizing problem with storage capacity limitation in which backlogging is allowed. For general concave production and inventory costs, we present an O(T2) dynamic programming algorithm where T is the length of the planning horizon. Furthermore, for fixed-charge and nonspeculative costs, we provide O(Tlog T) and O(T) algorithms, respectively. This paper therefore concludes that the time complexity to solve the bounded inventory lot-sizing problem with backlogging is the same as the complexity to solve the uncapacitated lot-sizing problem for the commonly used cost structures

Keywords: algorithms; inventory and production; lot-sizing; storage capacity (search for similar items in EconPapers)
Date: 2010-03-29
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
https://repub.eur.nl/pub/18591/EI2010-17.pdf (application/pdf)

Related works:
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:ems:eureir:18591

Access Statistics for this paper

More papers in Econometric Institute Research Papers from Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute Contact information at EDIRC.
Bibliographic data for series maintained by RePub ( this e-mail address is bad, please contact ).