Multi-stage Stochastic Programming Models in Production Planning

Show full item record

Please use this identifier to cite or link to this item: http://hdl.handle.net/1853/7164

Title: Multi-stage Stochastic Programming Models in Production Planning
Author: Huang, Kai
Abstract: In this thesis, we study a series of closely related multi-stage stochastic programming models in production planning, from both a modeling and an algorithmic point of view. We first consider a very simple multi-stage stochastic lot-sizing problem, involving a single item with no fixed charge and capacity constraint. Although a multi-stage stochastic integer program, this problem can be shown to have a totally unimodular constraint matrix. We develop primal and dual algorithms by exploiting the problem structure. Both algorithms are strongly polynomial, and therefore much more efficient than the Simplex method. Next, motivated by applications in semiconductor tool planning, we develop a general capacity planning problem under uncertainty. Using a scenario tree to model the evolution of the uncertainties, we present 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 over the two-stage approach. By exploiting the special simple stochastic lot-sizing substructure inherent in the problem, we design an efficient approximation scheme and show that the proposed scheme is asymptotically optimal. We conduct a computational study with respect to a semiconductor-tool-planning problem. 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. Next, we extend the simple stochastic lot-sizing model to an infinite horizon problem to study the planning horizon of this problem. We show that an optimal solution of the infinite horizon problem can be approximated by optimal solutions of a series of finite horizon problems, which implies the existence of a planning horizon. We also provide a useful upper bound for the planning horizon.
Type: Dissertation
URI: http://hdl.handle.net/1853/7164
Date: 2005-07-13
Publisher: Georgia Institute of Technology
Subject: Resource allocation
Multistage stochastic programming
Production planning
Planning horizon
Lot-sizing
Capacity planning
Department: Industrial and Systems Engineering
Advisor: Committee Chair: Shabbir Ahmed; Committee Member: Alex Shapiro; Committee Member: Chip White; Committee Member: Joel Sokol; Committee Member: Ozlem Ergun; Committee Member: Samer Takriti
Degree: Ph.D.

All materials in SMARTech are protected under U.S. Copyright Law and all rights are reserved, unless otherwise specifically indicated on or in the materials.

Files in this item

Files Size Format View
huang_kai_200508_phd.pdf 836.5Kb PDF View/ Open

This item appears in the following Collection(s)

Show full item record