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(T4)O(T4) and O(T6)O(T6) 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.