Improved algorithms for a lot‐sizing problem with inventory bounds and backlogging

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. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012