Dynamic programming and heuristic for stochastic uncapacitated lot-sizing problems with incremental quantity discount

The stochastic uncapacitated lot-sizing problems with incremental quantity discount have been studied in this paper. First, a multistage stochastic mixed integer model is established by the scenario analysis approach and an equivalent reformulation is obtained through proper relaxation under the decreasing unit order price assumption. The proposed reformulation allows us to extend the production-path property to this framework, and furthermore we provide a more accurate characterization of the optimal solution. Then, a backward dynamic programming algorithm is developed to obtain the optimal solution and considering its exponential computation complexity in term of time stages, we design a new rolling horizon heuristic based on the proposed property. Comparisons with the commercial solver CPLEX and other heuristics indicate better performance of our proposed algorithms in both quality of solution and run time. © 2012 Yuli Zhang et al.