The Economic Lot-Sizing Problem with Lost Sales and Bounded Inventory

In this paper, we consider an economic lot-sizing problem with lost sales and bounded inventory. We prove structural properties of optimal solutions under different assumptions on the cost functions. Using these properties, we present new and improved algorithms for the problem. Specifically, we present the first polynomial algorithm for the general lot-sizing problem with lost sales and bounded inventory, and we show that the complexity can be reduced considerably in the special case of non-increasing lost sales costs. Moreover, with the additional assumption that there is no speculative motive for holding inventory, we improve on an existing result by providing a linear time algorithm.