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. The purpose of this paper is twofold. First, we derive a backward algorithm based on the forward algorithm by Chen et al. (1994), which solves the general CLSP. We give a problem instances that requires exponential running time using the backward algorithm. Second, we provide a new O($T^2$) algorithm for the CLSP with non-increasing setup cost, general holding cost, non-increasing production cost and non-decreasing capacities over time. This is done by adapting the backward algorithm. Numerical tests show the better performance of our algorithm compared to the algorithm proposed by Chung and Lin (1988).
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. In case of further problems read
the IDEAS help
page. Note that these files are not on the IDEAS
site. Please be patient as the files may be large.
Publisher Info
Paper provided by Erasmus University Rotterdam, Econometric Institute in its series Econometric Institute Report with number
329.