Improved algorithms for dynamic lot sizing problems with incremental discount |
| |
| Authors: | Jie Fan Guoqing Wang |
| |
| Affiliation: | Department of Administrative Management, Jinan University, Guangzhou, People’s Republic of China |
| |
| Abstract: | We develop improved algorithms for the dynamic lot sizing problems with incremental discount, where the procurement cost is a concave piecewise linear function with m sections and the holding cost is linear. We decompose the problem carefully and present a new dynamic programming formulation. By using geometric techniques, we show that when m is fixed, the problem can be solved in O(T?log?T) time, and further O(T) time if the procurement cost is stationary. |
| |
| Keywords: | dynamic lot sizing concave piecewise linear cost exact algorithms geometric technique dynamic programming |
|
|
