Improved algorithms for dynamic lot sizing problems with incremental discount

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.