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].

Additional Metadata
Keywords capacitated lot-sizing, inventory, production
Persistent URL dx.doi.org/10.1016/j.cor.2005.02.046, hdl.handle.net/1765/14390
Series ERIM Article Series (EAS)
Journal Computers & Operations Research
Citation
van den Heuvel, W, & Wagelmans, A.P.M. (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