Polynomial-Time Algorithms for Stochastic Uncapacitated Lot-Sizing Problems

Yongpei Guan () and Andrew J. Miller ()
Additional contact information
Yongpei Guan: School of Industrial Engineering, University of Oklahoma, Norman, Oklahoma 73019
Andrew J. Miller: Department of Industrial and Systems Engineering, University of Wisconsin, Madison, Wisconsin 53706

Operations Research, 2008, vol. 56, issue 5, 1172-1183

Abstract: 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.

Keywords: lot sizing; stochastic programming; dynamic programming; production/scheduling; planning; programming; integer; stochastic (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1070.0479 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:56:y:2008:i:5:p:1172-1183

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().