IDEAS home Printed from
   My bibliography  Save this article

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


  • 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)


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

    Download full text from publisher

    File URL:
    Download Restriction: no

    References listed on IDEAS

    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. Awi Federgruen & Paul Zipkin, 1984. "An Efficient Algorithm for Computing Optimal ( s , S ) Policies," Operations Research, INFORMS, vol. 32(6), pages 1268-1285, December.
    4. 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.
    5. Jing-Sheng Song & Paul Zipkin, 1993. "Inventory Control in a Fluctuating Demand Environment," Operations Research, INFORMS, vol. 41(2), pages 351-370, April.
    6. John Rust, 1997. "Using Randomization to Break the Curse of Dimensionality," Econometrica, Econometric Society, vol. 65(3), pages 487-516, May.
    7. 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.
    8. 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 are extracted by the CitEc Project, subscribe to its RSS feed for this item.

    Cited by:

    1. repec:eee:ejores:v:263:y:2017:i:3:p:838-863 is not listed on IDEAS
    2. 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.
    3. 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.
    4. 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.
    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. 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.


    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.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Matthew Walls). General contact details of provider: .

    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 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.