Polynomial time algorithms for the constant capacitated single-item lot sizing problem with stepwise production cost

This paper presents two polynomial time algorithms for the constant capacitated lot sizing problem with a batch production. We give several optimality properties for the general problem. Assuming constant production capacity, constant batch size and Wagner-Whitin cost structure, we derive O(T-4) and O(T-6) time algorithms respectively for the case with production capacity being a multiple of the batch size and for the case with an arbitrary fixed capacity. (C) 2012 Elsevier B.V. All rights reserved.