This article considers a dynamic lot-sizing problem with storage capacity limitation in which backlogging is allowed. For general concave procurement and inventory costs, we present an O(T 2) dynamic programming algorithm where T is the length of the planning horizon. Furthermore, in case of a fixed-charge cost structure without speculative motives, we show that the problem can be solved in O(T) time. By carefully choosing decompositions of the problems, we can use classical results like an efficient matrix searching algorithm and geometric techniques to achieve the results.

, , ,,
Naval Research Logistics: an international journal
Erasmus Research Institute of Management

Hwang, H.-C., & van den Heuvel, W. (2012). Improved algorithms for a lot-sizing problem with inventory bounds and backlogging. Naval Research Logistics: an international journal, 59(3-4), 244–253. doi:10.1002/nav.21485