The Value of Multistage Stochastic Programming in Capacity Planning Under Uncertainty

作     者：Huang, Kai Ahmed, Shabbir 

作者机构：SUNY Binghamton Sch Management Binghamton NY 13902 USA Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA 

出 版 物：《OPERATIONS RESEARCH》 (运筹学)

年 卷 期：2009年第57卷第4期

页      面：893-904页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：facilities/equipment planning: capacity expansion production/scheduling: planning programming: stochastic 

摘      要：This paper addresses a general class of capacity planning problems under uncertainty, which arises, for example, in semiconductor tool purchase planning. Using a scenario tree to model the evolution of the uncertainties, we develop a multistage stochastic integer programming formulation for the problem. In contrast to earlier two-stage approaches, the multistage model allows for revision of the capacity expansion plan as more information regarding the uncertainties is revealed. We provide analytical bounds for the value of multistage stochastic programming (VMS) afforded over the two-stage approach. By exploiting a special substructure inherent in the problem, we develop an efficient approximation scheme for the difficult multistage stochastic integer program and prove that the proposed scheme is asymptotically optimal. Computational experiments with realistic-scale problem instances suggest that the VMS for this class of problems is quite high;moreover, the quality and performance of the approximation scheme is very satisfactory. Fortunately, this is more so for instances for which the VMS is high.