IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v57y2009i4p893-904.html
   My bibliography  Save this article

The Value of Multistage Stochastic Programming in Capacity Planning Under Uncertainty

Author

Listed:
  • Kai Huang

    (School of Management, Binghamton University, State University of New York, Binghamton, New York 13902)

  • Shabbir Ahmed

    (School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

Abstract

This paper addresses a general class of capacity planning problems under uncertainty, which arises, for example, in semiconductor tool purchase planning. Using a scenario tree to model the evolution of the uncertainties, we develop a multistage stochastic integer programming formulation for the problem. In contrast to earlier two-stage approaches, the multistage 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 multistage stochastic programming (VMS) afforded over the two-stage approach. By exploiting a special substructure inherent in the problem, we develop an efficient approximation scheme for the difficult multistage stochastic integer program and prove that the proposed scheme is asymptotically optimal. Computational experiments with realistic-scale problem instances suggest that the VMS for this class of problems is quite high; moreover, the quality and performance of the approximation scheme is very satisfactory. Fortunately, this is more so for instances for which the VMS is high.

Suggested Citation

  • Kai Huang & Shabbir Ahmed, 2009. "The Value of Multistage Stochastic Programming in Capacity Planning Under Uncertainty," Operations Research, INFORMS, vol. 57(4), pages 893-904, August.
    • Handle: RePEc:inm:oropre:v:57:y:2009:i:4:p:893-904
    DOI: 10.1287/opre.1080.0623
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1080.0623
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1080.0623?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Swaminathan, Jayashankar M., 2000. "Tool capacity planning for semiconductor fabrication facilities under demand uncertainty," European Journal of Operational Research, Elsevier, vol. 120(3), pages 545-558, February.
    2. S. M. Johnson, 1957. "Sequential Production Planning Over Time at Minimum Cost," Management Science, INFORMS, vol. 3(4), pages 435-437, July.
    3. Hanan Luss, 1982. "Operations Research and Capacity Expansion Problems: A Survey," Operations Research, INFORMS, vol. 30(5), pages 907-947, October.
    4. C. O. Fong & V. Srinivasan, 1981. "The Multiregion Dynamic Capacity Expansion Problem, Part I," Operations Research, INFORMS, vol. 29(4), pages 787-799, August.
    5. Rajagopalan, S., 1994. "Capacity expansion with alternative technology choices," European Journal of Operational Research, Elsevier, vol. 77(3), pages 392-403, September.
    6. John Freidenfelds, 1980. "Capacity Expansion when Demand Is a Birth-Death Random Process," Operations Research, INFORMS, vol. 28(3-part-ii), pages 712-721, June.
    7. James C. Bean & Julia L. Higle & Robert L. Smith, 1992. "Capacity Expansion Under Stochastic Demands," Operations Research, INFORMS, vol. 40(3-supplem), pages 210-216, June.
    8. C. O. Fong & V. Srinivasan, 1981. "The Multiregion Dynamic Capacity Expansion Problem, Part II," Operations Research, INFORMS, vol. 29(4), pages 800-816, August.
    9. Francisco Barahona & Stuart Bermon & Oktay Günlük & Sarah Hood, 2005. "Robust capacity planning in semiconductor manufacturing," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(5), pages 459-468, August.
    10. Oded Berman & Zvi Ganz & Janet M. Wagner, 1994. "A stochastic optimization model for planning capacity expansion in a service industry under uncertain demand," Naval Research Logistics (NRL), John Wiley & Sons, vol. 41(4), pages 545-564, June.
    11. Suleyman Karabuk & S. David Wu, 2003. "Coordinating Strategic Capacity Planning in the Semiconductor Industry," Operations Research, INFORMS, vol. 51(6), pages 839-849, December.
    12. Gary D. Eppen & R. Kipp Martin & Linus Schrage, 1989. "OR Practice—A Scenario Approach to Capacity Planning," Operations Research, INFORMS, vol. 37(4), pages 517-527, August.
    13. Charles H. Fine & Robert M. Freund, 1990. "Optimal Investment in Product-Flexible Manufacturing Capacity," Management Science, INFORMS, vol. 36(4), pages 449-466, April.
    14. Shanling Li & Devanath Tirupati, 1994. "Dynamic Capacity Expansion Problem with Multiple Products: Technology Selection and Timing of Capacity Additions," Operations Research, INFORMS, vol. 42(5), pages 958-976, October.
    15. Shabbir Ahmed & Nikolaos V. Sahinidis, 2003. "An Approximation Scheme for Stochastic Integer Programs Arising in Capacity Expansion," Operations Research, INFORMS, vol. 51(3), pages 461-471, June.
    16. John R. Birge, 1985. "Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs," Operations Research, INFORMS, vol. 33(5), pages 989-1007, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Shabbir Ahmed & Nikolaos V. Sahinidis, 2003. "An Approximation Scheme for Stochastic Integer Programs Arising in Capacity Expansion," Operations Research, INFORMS, vol. 51(3), pages 461-471, June.
    2. Van-Anh Truong & Robin O. Roundy, 2011. "Multidimensional Approximation Algorithms for Capacity-Expansion Problems," Operations Research, INFORMS, vol. 59(2), pages 313-327, April.
    3. Hongmin Li & Stephen C. Graves & Woonghee Tim Huh, 2014. "Optimal Capacity Conversion for Product Transitions Under High Service Requirements," Manufacturing & Service Operations Management, INFORMS, vol. 16(1), pages 46-60, February.
    4. Ahmed, Shabbir & Sahinidis, Nikolaos V., 2008. "Selection, acquisition, and allocation of manufacturing technology in a multi-period environment," European Journal of Operational Research, Elsevier, vol. 189(3), pages 807-821, September.
    5. Metin Çakanyıldırım & Robin O. Roundy & Samuel C. Wood, 2004. "Optimal machine capacity expansions with nested limitations under stochastic demand," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(2), pages 217-241, March.
    6. Torres-Rincón, Samuel & Sánchez-Silva, Mauricio & Bastidas-Arteaga, Emilio, 2021. "A multistage stochastic program for the design and management of flexible infrastructure networks," Reliability Engineering and System Safety, Elsevier, vol. 210(C).
    7. Kavinesh J. Singh & Andy B. Philpott & R. Kevin Wood, 2009. "Dantzig-Wolfe Decomposition for Solving Multistage Stochastic Capacity-Planning Problems," Operations Research, INFORMS, vol. 57(5), pages 1271-1286, October.
    8. Zhouchun Huang & Qipeng P. Zheng & Andrew L. Liu, 2022. "A Nested Cross Decomposition Algorithm for Power System Capacity Expansion with Multiscale Uncertainties," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 1919-1939, July.
    9. Harrison, J. Michael & Van Mieghem, Jan A., 1999. "Multi-resource investment strategies: Operational hedging under demand uncertainty," European Journal of Operational Research, Elsevier, vol. 113(1), pages 17-29, February.
    10. Woonghee Tim Huh & Robin O. Roundy, 2005. "A continuous‐time strategic capacity planning model," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(4), pages 329-343, June.
    11. Jan A. Van Mieghem, 2003. "Commissioned Paper: Capacity Management, Investment, and Hedging: Review and Recent Developments," Manufacturing & Service Operations Management, INFORMS, vol. 5(4), pages 269-302, July.
    12. Jikai Zou & Shabbir Ahmed & Xu Andy Sun, 2018. "Partially Adaptive Stochastic Optimization for Electric Power Generation Expansion Planning," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 388-401, May.
    13. Porteus, Evan L. & Angelus, Alexandar & Wood, Samuel C., 2000. "Optimal Sizing and Timing of Modular Capacity Expansions," Research Papers 1479r2, Stanford University, Graduate School of Business.
    14. Lee, Chia-Yen & Charles, Vincent, 2022. "A robust capacity expansion integrating the perspectives of marginal productivity and capacity regret," European Journal of Operational Research, Elsevier, vol. 296(2), pages 557-569.
    15. Jakubovskis, Aldis, 2017. "Flexible production resources and capacity utilization rates: A robust optimization perspective," International Journal of Production Economics, Elsevier, vol. 189(C), pages 77-85.
    16. Huang, Kai & Ahmed, Shabbir, 2010. "A stochastic programming approach for planning horizons of infinite horizon capacity planning problems," European Journal of Operational Research, Elsevier, vol. 200(1), pages 74-84, January.
    17. Sabet, Ehsan & Yazdani, Baback & Kian, Ramez & Galanakis, Kostas, 2020. "A strategic and global manufacturing capacity management optimisation model: A Scenario-based multi-stage stochastic programming approach," Omega, Elsevier, vol. 93(C).
    18. Martínez-Costa, Carme & Mas-Machuca, Marta & Benedito, Ernest & Corominas, Albert, 2014. "A review of mathematical programming models for strategic capacity planning in manufacturing," International Journal of Production Economics, Elsevier, vol. 153(C), pages 66-85.
    19. Yang, Qing & Zhang, Lei & Zou, Shaohui & Zhang, Jinsuo, 2020. "Intertemporal optimization of the coal production capacity in China in terms of uncertain demand, economy, environment, and energy security," Energy Policy, Elsevier, vol. 139(C).
    20. Kimms, Alf, 1996. "Stability measures for rolling schedules with applications to capacity expansion planning, master production scheduling, and lot sizing," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 418, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:57:y:2009:i:4:p:893-904. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.