An efficient dynamic programming algorithm for a special case of the capacitated lot-sizing problem

In this paper we consider the capacitated lot-sizing problem (CLSP) with linear costs. It is known that this problem is NP-hard, but there exist special cases that can be solved in polynomial time. We derive a new O(T²) algorithm for the CLSP with non-increasing setup costs, general holding costs, non-increasing production costs and non-decreasing capacities over time, where T is the length of the model horizon. We show that in every iteration we do not consider more candidate solutions than the O(T²) algorithm proposed by Chung and Lin. We also develop a variant of our algorithm that is more efficient in the case of relatively large capacities. Numerical tests show the superior performance of our algorithms compared to the algorithm of Chung and Lin.