This Article Full Text (PDF) e-companion Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Guan, Y. Articles by Miller, A. J. Search for Related Content

Polynomial-Time Algorithms for Stochastic Uncapacitated Lot-Sizing Problems

School of Industrial Engineering, University of Oklahoma, Norman, Oklahoma 73019
Department of Industrial and Systems Engineering, University of Wisconsin, Madison, Wisconsin 53706
yguan{at}ou.edu
amiller{at}engr.wisc.edu

In 1958, Wagner and Whitin published a seminal paper on the deterministic uncapacitated lot-sizing problem, a fundamental model that is embedded in many practical production planning problems. In this paper, we consider a basic version of this model in which problem parameters are stochastic: the stochastic uncapacitated lot-sizing problem. We define the production-path property of an optimal solution for our model and use this property to develop a backward dynamic programming recursion. This approach allows us to show that the value function is piecewise linear and right continuous. We then use these results to show that a full characterization of the optimal value function can be obtained by a dynamic programming algorithm in polynomial time for the case that each nonleaf node contains at least two children. Moreover, we show that our approach leads to a polynomial-time algorithm to obtain an optimal solution to any instance of the stochastic uncapacitated lot-sizing problem, regardless of the structure of the scenario tree. We also show that the value function for the problem without setup costs is continuous, piecewise linear, and convex, and therefore an even more efficient dynamic programming algorithm can be developed for this special case.

Subject classifications: lot sizing; stochastic programming; dynamic programming; production/scheduling; planning; programming; integer; stochastic.
History: Received June 2006; revision received August 2007; accepted August 2007.