The value of multi-stage stochastic programming in capacity planning under uncertainty

Kai Huang (kaihisye.isye.gatech.edu)
Shabbir Ahmed (sahmedisye.gatech.edu)

Abstract: 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 multi-stage stochastic integer programming formulation for the problem. In contrast to earlier two-stage approaches, the multi-stage 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 multi-stage stochastic programming (VMS) afforded over the two-stage approach. By exploiting a special lot-sizing substructure inherent in the problem, we develop an efficient approximation scheme for the difficult multi-stage 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.

Keywords: multi-stage stochastic programming, capacity planning, semiconductor tool planning, stochastic lot-sizing, analysis of algorithms

Category 1: Stochastic Programming

Category 2: Applications -- OR and Management Sciences (Production and Logistics )

Citation: Technical Report, School of Industrial & Systems Engineering, Georgia Tech.

Download: [PDF]

Entry Submitted: 04/29/2005
Entry Accepted: 04/29/2005
Entry Last Modified: 04/30/2005

Modify/Update this entry