Semiconductor tool planning via multi-stage stochastic programming

This paper presents an optimization model for planning tool purchases for a semiconductor manufacturing facility under uncertain operating conditions. By modeling the uncertain parameters using a scenario tree, we develop a stochastic pro-gramming formulation for the problem. In contrast to earlier two-stage approaches for this problem, our model allows for re-vision of the tool purchase plan as more information regarding the uncertain problem parameters becomes available. The pro-posed model is a multi-stage stochastic integer program and, in general, is extremely difficult to solve to optimality. We propose a LP-relaxation based approximation scheme for the problem. Our preliminary numerical results indicate that even an approximate solution to the multi-stage model is far supe-rior to any optimal solution to the two-stage model. These results confirm that the value of multi-stage stochastic pro-gramming for this class of problems is extremely high