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