Thesis Defense :: Multi-stage Stochastic Programming Models in Production Planning

Event Details
  • Date/Time:
    • Wednesday June 29, 2005
      1:00 pm - 11:59 pm
  • Location: Groseclose Building, Room 226A
  • Phone:
  • URL:
  • Email:
  • Fee(s):
  • Extras:
Barbara Christopher
Industrial and Systems Engineering
Contact Barbara Christopher

Summary Sentence: Thesis Defense :: Multi-stage Stochastic Programming Models in Production Planning

Full Summary: Thesis Defense :: Multi-stage Stochastic Programming Models in Production Planning

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.

Additional Information

In Campus Calendar

School of Industrial and Systems Engineering (ISYE)

Invited Audience
No audiences were selected.
No keywords were submitted.
  • Created By: Barbara Christopher
  • Workflow Status: Published
  • Created On: Oct 8, 2010 - 7:38am
  • Last Updated: Oct 7, 2016 - 9:52pm