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
Publisher Erasmus School of Economics (ESE)
Persistent URL hdl.handle.net/1765/18591
Citation
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). Erasmus School of Economics (ESE). Retrieved from http://hdl.handle.net/1765/18591