Polynomial algorithms for single-item lot-sizing models with bounded inventory and backlogging or outsourcing

This paper addresses a real-life single-item dynamic lot sizing problem arising in a refinery for crude oil procurement. It can be considered as a lot sizing problem with bounded inventory. We consider two managerial policies. With one policy, a part of the demand of a period can be backlogged and with the other, a part of the demand of a period can be outsourced. We define actuated inventory bounds and show that any bounded inventory lot sizing model can be transformed into an equivalent model with actuated inventory bounds. The concept of actuated inventory bounds significantly contributes to the complexity reduction. In the studied models, the production capacity can be assumed to be unlimited and the production cost functions to be linear ut with fixed charges. The results can be easily extended to piecewise linear concave production cost functions. The goal is to minimize the total cost of production, inventory holding and backlogging, or outsourcing. We show that the backlogging model can be solved in O(T-2) time with general concave inventory holding and backlogging cost functions where T is the number of periods in the planning horizon. The complexity is reduced to O(T) when the inventory/backlogging cost functions are linear and there is no speculative motives to hold either inventory or backlogging. When the outsourcing levels are unbounded, we show that the outsourcing model can be transformed into an inventory/backlogging model. As a consequence, the problem can be solved in O(T-2) time, if the outsourcing cost functions are linear with fixed charges even if the inventory holding cost functions are general concave functions. When the outsourcing level of a period is bounded from above by the demand of the period, which is the case in many application areas, we show that the outsourcing model can be solved in O(T-2 log T) time if the inventory holding and the outsourcing cost functions are linear.