Mathematical Problems in Engineering
Volume 2012 (2012), Article ID 582323, 21 pages
Research Article

Dynamic Programming and Heuristic for Stochastic Uncapacitated Lot-Sizing Problems with Incremental Quantity Discount

1Department of Automation, TNList, Tsinghua University, Beijing 100084, China
2Industry Solutions, IBM Research-China, Beijing 100193, China

Received 30 January 2012; Revised 25 April 2012; Accepted 8 May 2012

Academic Editor: Jung-Fa Tsai

Copyright © 2012 Yuli Zhang et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


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.