*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
The research addresses modeling and algorithmic aspects of a series of closely related multi-stage stochastic programs arising in production planning applications. Using a scenario tree to model the evolution of the uncertain parameters, a multi-stage stochastic programming formulation of a simple lot-sizing problem is studied first. By exploiting the scenario tree structure, efficient Primal and Dual algorithms are developed. Next, motivated by applications in semiconductor tool planning, a general capacity planning problem under uncertainty is considered. A multi-stage stochastic integer programming formulation for the problem is developed.
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. Analytical bounds for the "value of multi-stage stochastic programming" over the two-stage approach are developed. By exploiting a special stochastic lot-sizing substructure inherent in the problem, an efficient approximation scheme is developed.
It is proved that the proposed scheme is asymptotically optimal. A computational study with respect to a realistic-scale semiconductor tool-planning problem is conducted. Numerical results indicate that even an approximate solution to the multi-stage model is far superior to any optimal solution to the two-stage model. These results show that the value of multi-stage stochastic programming for this class of problem is extremely high. Moreover, the proposed approximation scheme appears to perform better precisely for instances with high value of multi-stage stochastic programming. Finally, the simple stochastic lot-sizing model studied earlier is extended to infinite horizon. A finite horizon approximation of this problem is investigated. It is proved that the objective and solution of the finite approximation problem converge to those of the infinite horizon problem as the time horizon goes to infinity. Furthermore, it is shown that there exists a finite planning horizon such that the optimal first-stage solution of the finite horizon approximation problem will be the same as that of the infinite horizon problem. A useful upper bound for this planning horizon is provided.
