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

Overview & Synopsis

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 multiple of the batch size and for the case with arbitrary fixed capacities.% the general case.