Provably near-optimal algorithms for multi-stage stochastic optimization models in operations management
Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2012.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2013
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/77827 |
| _version_ | 1811069728812171264 |
|---|---|
| author | Shi, Cong |
| author2 | Retsef Levi. |
| author_facet | Retsef Levi. Shi, Cong |
| author_sort | Shi, Cong |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2012. |
| first_indexed | 2024-09-23T08:15:00Z |
| format | Thesis |
| id | mit-1721.1/77827 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T08:15:00Z |
| publishDate | 2013 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/778272023-03-01T02:07:32Z Provably near-optimal algorithms for multi-stage stochastic optimization models in operations management Shi, Cong Retsef Levi. Massachusetts Institute of Technology. Operations Research Center. Massachusetts Institute of Technology. Operations Research Center Sloan School of Management Operations Research Center. Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2012. Cataloged from PDF version of thesis. Includes bibliographical references (p. 157-165). Many if not most of the core problems studied in operations management fall into the category of multi-stage stochastic optimization models, whereby one considers multiple, often correlated decisions to optimize a particular objective function under uncertainty on the system evolution over the future horizon. Unfortunately, computing the optimal policies is usually computationally intractable due to curse of dimensionality. This thesis is focused on providing provably near-optimal and tractable policies for some of these challenging models arising in the context of inventory control, capacity planning and revenue management; specifically, on the design of approximation algorithms that admit worst-case performance guarantees. In the first chapter, we develop new algorithmic approaches to compute provably near-optimal policies for multi-period stochastic lot-sizing inventory models with positive lead times, general demand distributions and dynamic forecast updates. The proposed policies have worst-case performance guarantees of 3 and typically perform very close to optimal in extensive computational experiments. We also describe a 6-approximation algorithm for the counterpart model under uniform capacity constraints. In the second chapter, we study a class of revenue management problems in systems with reusable resources and advanced reservations. A simple control policy called the class selection policy (CSP) is proposed based on solving a knapsack-type linear program (LP). We show that the CSP and its variants perform provably near-optimal in the Halfin- Whitt regime. The analysis is based on modeling the problem as loss network systems with advanced reservations. In particular, asymptotic upper bounds on the blocking probabilities are derived. In the third chapter, we examine the problem of capacity planning in joint ventures to meet stochastic demand in a newsvendor-type setting. When resources are heterogeneous, there exists a unique revenue-sharing contract such that the corresponding Nash Bargaining Solution, the Strong Nash Equilibrium, and the system optimal solution coincide. The optimal scheme rewards every participant proportionally to her marginal cost. When resources are homogeneous, there does not exist a revenue-sharing scheme which induces the system optimum. Nonetheless, we propose provably good revenue-sharing contracts which suggests that the reward should be inversely proportional to the marginal cost of each participant. by Cong Shi. Ph.D. 2013-03-13T15:51:57Z 2013-03-13T15:51:57Z 2012 2012 Thesis http://hdl.handle.net/1721.1/77827 828627943 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 165 p. application/pdf Massachusetts Institute of Technology |
| spellingShingle | Operations Research Center. Shi, Cong Provably near-optimal algorithms for multi-stage stochastic optimization models in operations management |
| title | Provably near-optimal algorithms for multi-stage stochastic optimization models in operations management |
| title_full | Provably near-optimal algorithms for multi-stage stochastic optimization models in operations management |
| title_fullStr | Provably near-optimal algorithms for multi-stage stochastic optimization models in operations management |
| title_full_unstemmed | Provably near-optimal algorithms for multi-stage stochastic optimization models in operations management |
| title_short | Provably near-optimal algorithms for multi-stage stochastic optimization models in operations management |
| title_sort | provably near optimal algorithms for multi stage stochastic optimization models in operations management |
| topic | Operations Research Center. |
| url | http://hdl.handle.net/1721.1/77827 |
| work_keys_str_mv | AT shicong provablynearoptimalalgorithmsformultistagestochasticoptimizationmodelsinoperationsmanagement |