Algorithms for single item constant capacity lotsizing problems

The main result of this paper is to provide an O(n3) algorithm for the single item constant capacity lotsizing problem with backlogging and a general number of installable batches, i.e in each time period t we may install up to mt multiples of the batch capacity, where the mt are given and are time-dependent. This generalizes earlier results [12, 16] as we consider backlogging and a general number of installable batches. We also give faster algorithms for three special cases of this general problem. When backlogging is not allowed and the costs satisfy the Wagner-Whitin property the problem is solvable in O(n2logn) time. In the discrete case it is possible to solve the problem with and without backlogging in O(n2) and O(n2logn) time respectively.