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

, , ,
Erasmus School of Economics
hdl.handle.net/1765/18591
Econometric Institute Research Papers
Report / Econometric Institute, Erasmus University Rotterdam
Erasmus School of Economics

Hwang, H.-C., & van den Heuvel, W. (2010). Improved Algorithms for a Lot-Sizing Problem with Inventory Bounds and Backlogging (No. EI 2010-17). Report / Econometric Institute, Erasmus University Rotterdam (pp. 1–30). Retrieved from http://hdl.handle.net/1765/18591