Polynomial time algorithms for constant capacitated lot sizing problems with equal length step-wise linear costs

This paper presents polynomial time algorithms for three extensions of the classical capacitated lot sizing problem (CLSP). We consider a constant batch size production with a fixed cost associated to each batch, additionally to the production setup cost and a unit holding cost. The production cost can then be considered as a step-wise function where the step length corresponds to the batch size. We can no more use the efficient methods proposed for the CLSP with concave costs in order to solve the CLSP with step-wise costs. We propose several properties of optimal solutions. Based on these properties, three polynomial time algorithms are provided under the assumptions of constant production capacity and constant batch sizes, as well as linear and non-increasing production costs over time. The uncapacitated case is solved in time complexity O(T^3). For the constant capacitated case, with a production capacity multiple of the batch size, the algorithm has a time complexity in O(T^4). The final algorithm concerns the general constant capacitated case, and has a time complexity in O(T^6)