Improved algorithms for dynamic lot sizing problems with incremental discount. (2nd January 2019) - Fan, Jie; Wang, Guoqing
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.