IDEAS home Printed from
   My bibliography  Save this article

Technical Note—Approximation Algorithms for Perishable Inventory Systems with Setup Costs


  • Huanan Zhang

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

  • Cong Shi

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

  • Xiuli Chao

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


We develop the first approximation algorithm for periodic-review perishable inventory systems with setup costs. The ordering lead time is zero. The model allows for correlated demand processes that generalize the well-known approaches to model dynamic demand forecast updates. The structure of optimal policies for this fundamental class of problems is not known in the literature. Thus, finding provably near-optimal control policies has been an open challenge. We develop a randomized proportional-balancing policy (RPB) that can be efficiently implemented in an online manner, and we show that it admits a worst-case performance guarantee between 3 and 4. The main challenge in our analysis is to compare the setup costs between RPB and the optimal policy in the presence of inventory perishability, which departs significantly from the previous works in the literature. The numerical results show that the average performance of RPB is good (within 1% of optimality under i.i.d. demands and within 7% under correlated demands).

Suggested Citation

  • 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.
  • Handle: RePEc:inm:oropre:v:64:y:2016:i:2:p:432-440
    DOI: 10.1287/opre.2016.1485

    Download full text from publisher

    File URL:
    Download Restriction: no

    References listed on IDEAS

    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. Retsef Levi & Ganesh Janakiraman & Mahesh Nagarajan, 2008. "A 2-Approximation Algorithm for Stochastic Inventory Control Models with Lost Sales," Mathematics of Operations Research, INFORMS, vol. 33(2), pages 351-374, May.
    3. Brant E. Fries, 1975. "Optimal Ordering Policy for a Perishable Commodity with Fixed Lifetime," Operations Research, INFORMS, vol. 23(1), pages 46-61, February.
    4. Gregory P. Prastacos, 1984. "Blood Inventory Management: An Overview of Theory and Practice," Management Science, INFORMS, vol. 30(7), pages 777-800, July.
    5. Steven Nahmias, 1975. "Optimal Ordering Policies for Perishable Inventory—II," Operations Research, INFORMS, vol. 23(4), pages 735-749, August.
    6. Z. Lian & L. Liu, 1999. "A discrete‐time model for perishable inventory systems," Annals of Operations Research, Springer, vol. 87(0), pages 103-116, April.
    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. Guillermo Gallego & Özalp Özer, 2001. "Integrating Replenishment Decisions with Advance Demand Information," Management Science, INFORMS, vol. 47(10), pages 1344-1360, October.
    9. 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.
    10. Steven Nahmias, 1976. "Myopic Approximations for the Perishable Inventory Problem," Management Science, INFORMS, vol. 22(9), pages 1002-1008, May.
    11. Zhaotong Lian & Liming Liu & Marcel F. Neuts, 2005. "A Discrete-Time Model for Common Lifetime Inventory Systems," Mathematics of Operations Research, INFORMS, vol. 30(3), pages 718-732, August.
    12. Steven Nahmias, 1978. "The Fixed-Charge Perishable Inventory Problem," Operations Research, INFORMS, vol. 26(3), pages 464-481, June.
    13. Steven Nahmias, 1977. "Higher-Order Approximations for the Perishable-Inventory Problem," Operations Research, INFORMS, vol. 25(4), pages 630-640, August.
    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. Hanukov, Gabi & Avinadav, Tal & Chernonog, Tatyana & Yechiali, Uri, 2019. "Performance improvement of a service system via stocking perishable preliminary services," European Journal of Operational Research, Elsevier, vol. 274(3), pages 1000-1011.
    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. Ketzenberg, Michael & Gaukler, Gary & Salin, Victoria, 2018. "Expiration dates and order quantities for perishables," European Journal of Operational Research, Elsevier, vol. 266(2), pages 569-584.
    4. 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.


    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:64:y:2016:i:2:p:432-440. 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.