An efficient dynamic programming algorithm for a special case of the capacitated lot-sizing problem
Computers & Operations Research , Volume 33 - Issue 12 p. 3583- 3599
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].
|capacitated lot-sizing, inventory, production|
|ERIM Article Series (EAS)|
|Computers & Operations Research|
|Organisation||Erasmus Research Institute of Management|
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