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

Approximation Algorithms for the Stochastic Lot-Sizing Problem with Order Lead Times

Author

Listed:
  • Retsef Levi

    (Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

  • Cong Shi

    (Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109)

Abstract

We develop new algorithmic approaches to compute provably near-optimal policies for multiperiod stochastic lot-sizing inventory models with positive lead times, general demand distributions, and dynamic forecast updates. The policies that are developed have worst-case performance guarantees of 3 and typically perform very close to optimal in extensive computational experiments. The newly proposed algorithms employ a novel randomized decision rule. We believe that these new algorithmic and performance analysis techniques could be used in designing provably near-optimal randomized algorithms for other stochastic inventory control models and more generally in other multistage stochastic control problems.

Suggested Citation

  • Retsef Levi & Cong Shi, 2013. "Approximation Algorithms for the Stochastic Lot-Sizing Problem with Order Lead Times," Operations Research, INFORMS, vol. 61(3), pages 593-602, June.
    • Handle: RePEc:inm:oropre:v:61:y:2013:i:3:p:593-602
    DOI: 10.1287/opre.2013.1162
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2013.1162
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2013.1162?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. Suresh P. Sethi & Feng Cheng, 1997. "Optimality of ( s , S ) Policies in Inventory Models with Markovian Demand," Operations Research, INFORMS, vol. 45(6), pages 931-939, December.
    2. Retsef Levi & Robin Roundy & David Shmoys & Maxim Sviridenko, 2008. "A Constant Approximation Algorithm for the One-Warehouse Multiretailer Problem," Management Science, INFORMS, vol. 54(4), pages 763-776, April.
    3. Özalp Özer & Wei Wei, 2004. "Inventory Control with Limited Capacity and Advance Demand Information," Operations Research, INFORMS, vol. 52(6), pages 988-1000, December.
    4. Awi Federgruen & Paul Zipkin, 1984. "An Efficient Algorithm for Computing Optimal ( s , S ) Policies," Operations Research, INFORMS, vol. 32(6), pages 1268-1285, December.
    5. Srinivas Bollapragada & Thomas E. Morton, 1999. "A Simple Heuristic for Computing Nonstationary (s, S) Policies," Operations Research, INFORMS, vol. 47(4), pages 576-584, August.
    6. Jing-Sheng Song & Paul Zipkin, 1993. "Inventory Control in a Fluctuating Demand Environment," Operations Research, INFORMS, vol. 41(2), pages 351-370, April.
    7. John Rust, 1997. "Using Randomization to Break the Curse of Dimensionality," Econometrica, Econometric Society, vol. 65(3), pages 487-516, May.
    8. Retsef Levi & Martin Pál & Robin O. Roundy & David B. Shmoys, 2007. "Approximation Algorithms for Stochastic Inventory Control Models," Mathematics of Operations Research, INFORMS, vol. 32(2), pages 284-302, May.
    9. Guillermo Gallego & Özalp Özer, 2001. "Integrating Replenishment Decisions with Advance Demand Information," Management Science, INFORMS, vol. 47(10), pages 1344-1360, October.
    10. Yossi Aviv & Awi Federgruen, 2001. "Capacitated Multi-Item Inventory Systems with Random and Seasonally Fluctuating Demands: Implications for Postponement Strategies," Management Science, INFORMS, vol. 47(4), pages 512-531, April.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Huanan Zhang & Cong Shi & Xiuli Chao, 2016. "Technical Note—Approximation Algorithms for Perishable Inventory Systems with Setup Costs," Operations Research, INFORMS, vol. 64(2), pages 432-440, April.
    2. Huanan Zhang & Cong Shi & Chao Qin & Cheng Hua, 2016. "Stochastic regret minimization for revenue management problems with nonstationary demands," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(6), pages 433-448, September.
    3. Gah-Yi Ban, 2020. "Confidence Intervals for Data-Driven Inventory Policies with Demand Censoring," Operations Research, INFORMS, vol. 68(2), pages 309-326, March.
    4. Hao Yuan & Qi Luo & Cong Shi, 2021. "Marrying Stochastic Gradient Descent with Bandits: Learning Algorithms for Inventory Systems with Fixed Costs," Management Science, INFORMS, vol. 67(10), pages 6089-6115, October.
    5. Retsef Levi & Robin Roundy & Van Anh Truong & Xinshang Wang, 2017. "Provably Near-Optimal Balancing Policies for Multi-Echelon Stochastic Inventory Control Models," Mathematics of Operations Research, INFORMS, vol. 42(1), pages 256-276, January.
    6. Darina Graczová & Peter Jacko, 2014. "Generalized Restless Bandits and the Knapsack Problem for Perishable Inventories," Operations Research, INFORMS, vol. 62(3), pages 696-711, June.
    7. Akartunalı, Kerem & Dauzère-Pérès, Stéphane, 2022. "Dynamic lot sizing with stochastic demand timing," European Journal of Operational Research, Elsevier, vol. 302(1), pages 221-229.
    8. Brahimi, Nadjib & Absi, Nabil & Dauzère-Pérès, Stéphane & Nordli, Atle, 2017. "Single-item dynamic lot-sizing problems: An updated survey," European Journal of Operational Research, Elsevier, vol. 263(3), pages 838-863.
    9. Cong Shi & Huanan Zhang & Xiuli Chao & Retsef Levi, 2014. "Approximation algorithms for capacitated stochastic inventory systems with setup costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(4), pages 304-319, June.
    10. Andrew F. Siegel & Michael R. Wagner, 2021. "Profit Estimation Error in the Newsvendor Model Under a Parametric Demand Distribution," Management Science, INFORMS, vol. 67(8), pages 4863-4879, August.
    11. Xiuli Chao & Xiting Gong & Cong Shi & Huanan Zhang, 2015. "Approximation Algorithms for Perishable Inventory Systems," Operations Research, INFORMS, vol. 63(3), pages 585-601, June.
    12. Van-Anh Truong, 2014. "Approximation Algorithm for the Stochastic Multiperiod Inventory Problem via a Look-Ahead Optimization Approach," Mathematics of Operations Research, INFORMS, vol. 39(4), pages 1039-1056, November.
    13. Hossein Jahandideh & Kumar Rajaram & Kevin McCardle, 2020. "Production Campaign Planning Under Learning and Decay," Manufacturing & Service Operations Management, INFORMS, vol. 22(3), pages 615-632, May.
    14. Awi Federgruen & Zhe Liu & Lijian Lu, 2022. "Dual sourcing: Creating and utilizing flexible capacities with a second supply source," Production and Operations Management, Production and Operations Management Society, vol. 31(7), pages 2789-2805, July.
    15. Xiuli Chao & Xiting Gong & Cong Shi & Chaolin Yang & Huanan Zhang & Sean X. Zhou, 2018. "Approximation Algorithms for Capacitated Perishable Inventory Systems with Positive Lead Times," Management Science, INFORMS, vol. 64(11), pages 5038-5061, November.
    16. Alexandar Angelus & Özalp Özer, 2016. "Knowledge You Can Act on: Optimal Policies for Assembly Systems with Expediting and Advance Demand Information," Operations Research, INFORMS, vol. 64(6), pages 1338-1371, December.

    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. Cong Shi & Huanan Zhang & Xiuli Chao & Retsef Levi, 2014. "Approximation algorithms for capacitated stochastic inventory systems with setup costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(4), pages 304-319, June.
    2. Xiuli Chao & Xiting Gong & Cong Shi & Chaolin Yang & Huanan Zhang & Sean X. Zhou, 2018. "Approximation Algorithms for Capacitated Perishable Inventory Systems with Positive Lead Times," Management Science, INFORMS, vol. 64(11), pages 5038-5061, November.
    3. Sandun C. Perera & Suresh P. Sethi, 2023. "A survey of stochastic inventory models with fixed costs: Optimality of (s, S) and (s, S)‐type policies—Discrete‐time case," Production and Operations Management, Production and Operations Management Society, vol. 32(1), pages 131-153, January.
    4. Nasr, Walid W. & Elshar, Ibrahim J., 2018. "Continuous inventory control with stochastic and non-stationary Markovian demand," European Journal of Operational Research, Elsevier, vol. 270(1), pages 198-217.
    5. Long Gao & Susan H. Xu & Michael O. Ball, 2012. "Managing an Available-to-Promise Assembly System with Dynamic Short-Term Pseudo-Order Forecast," Management Science, INFORMS, vol. 58(4), pages 770-790, April.
    6. Xiuli Chao & Xiting Gong & Cong Shi & Huanan Zhang, 2015. "Approximation Algorithms for Perishable Inventory Systems," Operations Research, INFORMS, vol. 63(3), pages 585-601, June.
    7. Van-Anh Truong, 2014. "Approximation Algorithm for the Stochastic Multiperiod Inventory Problem via a Look-Ahead Optimization Approach," Mathematics of Operations Research, INFORMS, vol. 39(4), pages 1039-1056, November.
    8. Xiang, Mengyuan & Rossi, Roberto & Martin-Barragan, Belen & Tarim, S. Armagan, 2023. "A mathematical programming-based solution method for the nonstationary inventory problem under correlated demand," European Journal of Operational Research, Elsevier, vol. 304(2), pages 515-524.
    9. Yossi Aviv & Awi Federgruen, 2001. "Design for Postponement: A Comprehensive Characterization of Its Benefits Under Unknown Demand Distributions," Operations Research, INFORMS, vol. 49(4), pages 578-598, August.
    10. Özalp Özer, 2003. "Replenishment Strategies for Distribution Systems Under Advance Demand Information," Management Science, INFORMS, vol. 49(3), pages 255-272, March.
    11. Tan, Tarkan & Gullu, Refik & Erkip, Nesim, 2007. "Modelling imperfect advance demand information and analysis of optimal inventory policies," European Journal of Operational Research, Elsevier, vol. 177(2), pages 897-923, March.
    12. Xiang, Mengyuan & Rossi, Roberto & Martin-Barragan, Belen & Tarim, S. Armagan, 2018. "Computing non-stationary (s, S) policies using mixed integer linear programming," European Journal of Operational Research, Elsevier, vol. 271(2), pages 490-500.
    13. Guillermo Gallego & Özalp Özer, 2003. "Optimal Replenishment Policies for Multiechelon Inventory Problems Under Advance Demand Information," Manufacturing & Service Operations Management, INFORMS, vol. 5(2), pages 157-175, February.
    14. Ren, Ke & Bidkhori, Hoda & Shen, Zuo-Jun Max, 2024. "Data-driven inventory policy: Learning from sequentially observed non-stationary data," Omega, Elsevier, vol. 123(C).
    15. Gah-Yi Ban, 2020. "Confidence Intervals for Data-Driven Inventory Policies with Demand Censoring," Operations Research, INFORMS, vol. 68(2), pages 309-326, March.
    16. Sandun C. Perera & Suresh P. Sethi, 2023. "A survey of stochastic inventory models with fixed costs: Optimality of (s, S) and (s, S)‐type policies—Continuous‐time case," Production and Operations Management, Production and Operations Management Society, vol. 32(1), pages 154-169, January.
    17. Fernando Bernstein & Gregory A. DeCroix & Yulan Wang, 2011. "The Impact of Demand Aggregation Through Delayed Component Allocation in an Assemble-to-Order System," Management Science, INFORMS, vol. 57(6), pages 1154-1171, June.
    18. Retsef Levi & Robin O. Roundy & David B. Shmoys & Van Anh Truong, 2008. "Approximation Algorithms for Capacitated Stochastic Inventory Control Models," Operations Research, INFORMS, vol. 56(5), pages 1184-1199, October.
    19. Hao Yuan & Qi Luo & Cong Shi, 2021. "Marrying Stochastic Gradient Descent with Bandits: Learning Algorithms for Inventory Systems with Fixed Costs," Management Science, INFORMS, vol. 67(10), pages 6089-6115, October.
    20. Suresh P. Sethi & Houmin Yan & Hanqin Zhang, 2003. "Inventory Models with Fixed Costs, Forecast Updates, and Two Delivery Modes," Operations Research, INFORMS, vol. 51(2), pages 321-328, April.

    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:61:y:2013:i:3:p:593-602. 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.