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(T2) 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(T2) algorithm proposed by [Chung and Lin, 1988. Management Science 34, 420–6]. 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, 1988. Management Science 34, 420–6].

, ,,
ERIM Article Series (EAS)
Computers & Operations Research
Erasmus Research Institute of Management

van den Heuvel, W., & Wagelmans, A. (2006). An efficient dynamic programming algorithm for a special case of the capacitated lot-sizing problem. Computers & Operations Research, 33(12), 3583–3599. doi:10.1016/j.cor.2005.02.046