IDEAS home Printed from https://ideas.repec.org/a/inm/ormnsc/v64y2018i11p5038-5061.html
   My bibliography  Save this article

Approximation Algorithms for Capacitated Perishable Inventory Systems with Positive Lead Times

Author

Listed:
  • Xiuli Chao

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

  • Xiting Gong

    (Department of Systems Engineering and Engineering Management, Faculty of Engineering, Chinese University of Hong Kong, Shatin, N.T., Hong Kong; Department of Decision Sciences and Managerial Economics, CUHK Business School, Chinese University of Hong Kong, Shatin, N.T., Hong Kong)

  • Cong Shi

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

  • Chaolin Yang

    (Research Institute for Interdisciplinary Sciences, School of Information Management and Engineering, Shanghai University of Finance and Economics, 200433 Shanghai, China)

  • Huanan Zhang

    (Harold and Inge Marcus Department of Industrial and Manufacturing Engineering, Pennsylvania State University, University Park, Pennsylvania 16802)

  • Sean X. Zhou

    (Department of Decision Sciences and Managerial Economics, CUHK Business School, Chinese University of Hong Kong, Shatin, N.T., Hong Kong)

Abstract

Managing perishable inventory systems with positive lead times and finite ordering capacities is important but notoriously difficult in both theory and computation. The optimal control policy is extremely complicated, and no effective heuristic policy has been proposed in the literature. In this paper, we develop an easy-to-compute approximation algorithm for this class of problems and prove that it admits a theoretical worst-case performance guarantee under independent and many commonly used positively correlated demand processes. Our worst-case analysis departs significantly from those in the previous studies, requiring several novel ideas. In particular, we introduce a transient unit-matching rule to dynamically match the supply and demand units, and the notion of associated demand processes that provides the right future demand information to establish the desired results. Our numerical study demonstrates the effectiveness of the proposed algorithm.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:ormnsc:v:64:y:2018:i:11:p:5038-5061
    DOI: 10.1287/mnsc.2017.2886
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/mnsc.2017.2886
    Download Restriction: no
    File URL: https://libkey.io/10.1287/mnsc.2017.2886?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. Steven Nahmias & William P. Pierskalla, 1973. "Optimal ordering policies for a product that perishes in two periods subject to stochastic demand," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 20(2), pages 207-229, June.
    2. Morris A. Cohen, 1976. "Analysis of Single Critical Number Ordering Policies for Perishable Inventories," Operations Research, INFORMS, vol. 24(4), pages 726-741, August.
    3. Adachi, Yasuo & Nose, Toyokazu & Kuriyama, Sennosuke, 1999. "Optimal inventory control policy subject to different selling prices of perishable commodities," International Journal of Production Economics, Elsevier, vol. 60(1), pages 389-394, April.
    4. Özalp Özer & Wei Wei, 2004. "Inventory Control with Limited Capacity and Advance Demand Information," Operations Research, INFORMS, vol. 52(6), pages 988-1000, December.
    5. Bryan L. Deuermeyer, 1980. "A single period model for a multiproduct perishable inventory system with economic substitution," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 27(2), pages 177-185, June.
    6. Linwei Xin & David A. Goldberg, 2016. "Optimality Gap of Constant-Order Policies Decays Exponentially in the Lead Time for Lost Sales Models," Operations Research, INFORMS, vol. 64(6), pages 1556-1565, December.
    7. Williams, Craig L. & Eddy Patuwo, B., 2004. "Analysis of the effect of various unit costs on the optimal incoming quantity in a perishable inventory model," European Journal of Operational Research, Elsevier, vol. 156(1), pages 140-147, July.
    8. Tayur, S.R., 1992. "Computing the Optimal Policy for Capacitated Inventory Models," GSIA Working Papers 1992-07, Carnegie Mellon University, Tepper School of Business.
    9. Roman Kapuściński & Sridhar Tayur, 1998. "A Capacitated Production-Inventory Model with Periodic Demand," Operations Research, INFORMS, vol. 46(6), pages 899-911, December.
    10. Jing-Sheng Song & Paul Zipkin, 1993. "Inventory Control in a Fluctuating Demand Environment," Operations Research, INFORMS, vol. 41(2), pages 351-370, April.
    11. Steven Nahmias, 2011. "Perishable Inventory Systems," International Series in Operations Research and Management Science, Springer, edition 1, number 978-1-4419-7999-5, December.
    12. Qing Li & Peiwen Yu & Xiaoli Wu, 2016. "Managing Perishable Inventories in Retailing: Replenishment, Clearance Sales, and Segregation," Operations Research, INFORMS, vol. 64(6), pages 1270-1284, December.
    13. A. Federgruen & P. Zipkin, 1986. "An Inventory Model with Limited Production Capacity and Uncertain Demands II. The Discounted-Cost Criterion," Mathematics of Operations Research, INFORMS, vol. 11(2), pages 208-215, May.
    14. Purushottaman Nandakumar & Thomas E. Morton, 1993. "Near Myopic Heuristics for the Fixed-Life Perishability Problem," Management Science, INFORMS, vol. 39(12), pages 1490-1498, December.
    15. Steven Nahmias, 1975. "Optimal Ordering Policies for Perishable Inventory—II," Operations Research, INFORMS, vol. 23(4), pages 735-749, August.
    16. 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.
    17. Linwei Xin & David A. Goldberg, 2018. "Asymptotic Optimality of Tailored Base-Surge Policies in Dual-Sourcing Inventory Systems," Management Science, INFORMS, vol. 64(1), pages 437-452, January.
    18. Guillermo Gallego & Özalp Özer, 2001. "Integrating Replenishment Decisions with Advance Demand Information," Management Science, INFORMS, vol. 47(10), pages 1344-1360, October.
    19. 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.
    20. Arthur F. Veinott, Jr., 1965. "Optimal Policy for a Multi-Product, Dynamic, Nonstationary Inventory Problem," Management Science, INFORMS, vol. 12(3), pages 206-222, November.
    21. Yanzhi Li & Andrew Lim & Brian Rodrigues, 2009. "Note--Pricing and Inventory Control for a Perishable Product," Manufacturing & Service Operations Management, INFORMS, vol. 11(3), pages 538-542, February.
    22. 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.
    23. 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.
    24. Ganesh Janakiraman & Robin O. Roundy, 2004. "Lost-Sales Problems with Stochastic Lead Times: Convexity Results for Base-Stock Policies," Operations Research, INFORMS, vol. 52(5), pages 795-803, October.
    25. René Haijema & Jan Wal & Nico M. Dijk, 2005. "Blood Platelet Production: a multi-type perishable inventory problem," Operations Research Proceedings, in: Hein Fleuren & Dick Hertog & Peter Kort (ed.), Operations Research Proceedings 2004, pages 84-92, Springer.
    26. Williams, Craig L. & Patuwo, B. Eddy, 1999. "A perishable inventory model with positive order lead times," European Journal of Operational Research, Elsevier, vol. 116(2), pages 352-373, July.
    27. 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.
    28. 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.
    29. Brant E. Fries, 1975. "Optimal Ordering Policy for a Perishable Commodity with Fixed Lifetime," Operations Research, INFORMS, vol. 23(1), pages 46-61, February.
    30. Bryan L. Deuermeyer, 1979. "A Multi-Type Production System for Perishable Inventories," Operations Research, INFORMS, vol. 27(5), pages 935-943, October.
    31. Xin Chen & Zhan Pang & Limeng Pan, 2014. "Coordinating Inventory Control and Pricing Strategies for Perishable Products," Operations Research, INFORMS, vol. 62(2), pages 284-300, April.
    32. Steven Nahmias, 1977. "Technical Note—Comparison between Two Dynamic Perishable Inventory Models," Operations Research, INFORMS, vol. 25(1), pages 168-172, February.
    33. A. Federgruen & P. Zipkin, 1986. "An Inventory Model with Limited Production Capacity and Uncertain Demands I. The Average-Cost Criterion," Mathematics of Operations Research, INFORMS, vol. 11(2), pages 193-207, May.
    34. D. Beyer & S. P. Sethi, 1997. "Average Cost Optimality in Inventory Models with Markovian Demands," Journal of Optimization Theory and Applications, Springer, vol. 92(3), pages 497-526, March.
    35. William L. Cooper, 2001. "Pathwise Properties and Performance Bounds for a Perishable Inventory System," Operations Research, INFORMS, vol. 49(3), pages 455-466, June.
    36. Steven Nahmias, 1976. "Myopic Approximations for the Perishable Inventory Problem," Management Science, INFORMS, vol. 22(9), pages 1002-1008, May.
    37. Steven Nahmias, 1978. "The Fixed-Charge Perishable Inventory Problem," Operations Research, INFORMS, vol. 26(3), pages 464-481, June.
    38. Steven Nahmias, 1977. "Higher-Order Approximations for the Perishable-Inventory Problem," Operations Research, INFORMS, vol. 25(4), pages 630-640, August.
    39. David A. Goldberg & Dmitriy A. Katz-Rogozhnikov & Yingdong Lu & Mayank Sharma & Mark S. Squillante, 2016. "Asymptotic Optimality of Constant-Order Policies for Lost Sales Inventory Models with Large Lead Times," Mathematics of Operations Research, INFORMS, vol. 41(3), pages 898-913, August.
    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. Jake Clarkson & Michael A. Voelkel & Anna‐Lena Sachs & Ulrich W. Thonemann, 2023. "The periodic review model with independent age‐dependent lifetimes," Production and Operations Management, Production and Operations Management Society, vol. 32(3), pages 813-828, March.
    2. Jinzhi Bu & Xiting Gong & Xiuli Chao, 2023. "Asymptotic Optimality of Base-Stock Policies for Perishable Inventory Systems," Management Science, INFORMS, vol. 69(2), pages 846-864, February.
    3. Ding, Jingying & Peng, Zhenkang, 2024. "Heuristics for perishable inventory systems under mixture issuance policies," Omega, Elsevier, vol. 126(C).
    4. 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.
    5. Harun Avci & Kagan Gokbayrak & Emre Nadar, 2020. "Structural Results for Average‐Cost Inventory Models with Markov‐Modulated Demand and Partial Information," Production and Operations Management, Production and Operations Management Society, vol. 29(1), pages 156-173, January.
    6. 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.

    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. 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.
    2. Ding, Jingying & Peng, Zhenkang, 2024. "Heuristics for perishable inventory systems under mixture issuance policies," Omega, Elsevier, vol. 126(C).
    3. Hailun Zhang & Jiheng Zhang & Rachel Q. Zhang, 2020. "Simple Policies with Provable Bounds for Managing Perishable Inventory," Production and Operations Management, Production and Operations Management Society, vol. 29(11), pages 2637-2650, November.
    4. Jinzhi Bu & Xiting Gong & Xiuli Chao, 2023. "Asymptotic Optimality of Base-Stock Policies for Perishable Inventory Systems," Management Science, INFORMS, vol. 69(2), pages 846-864, February.
    5. Shouchang Chen & Yanzhi Li & Yi Yang & Weihua Zhou, 2021. "Managing Perishable Inventory Systems with Age‐differentiated Demand," Production and Operations Management, Production and Operations Management Society, vol. 30(10), pages 3784-3799, October.
    6. 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.
    7. Kouki, Chaaben & Jouini, Oualid, 2015. "On the effect of lifetime variability on the performance of inventory systems," International Journal of Production Economics, Elsevier, vol. 167(C), pages 23-34.
    8. 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.
    9. Xiong‐zhi Wang & Guo‐qing Wang, 2019. "Integrating dynamic pricing and inventory control for fresh‐agri product under consumer choice," Australian Economic Papers, Wiley Blackwell, vol. 58(1), pages 96-111, March.
    10. Hossein Abouee‐Mehrizi & Mahdi Mirjalili & Vahid Sarhangian, 2022. "Data‐driven platelet inventory management under uncertainty in the remaining shelf life of units," Production and Operations Management, Production and Operations Management Society, vol. 31(10), pages 3914-3932, October.
    11. Lian, Zhaotong & Liu, Xiaoming & Zhao, Ning, 2009. "A perishable inventory model with Markovian renewal demands," International Journal of Production Economics, Elsevier, vol. 121(1), pages 176-182, September.
    12. Jake Clarkson & Michael A. Voelkel & Anna‐Lena Sachs & Ulrich W. Thonemann, 2023. "The periodic review model with independent age‐dependent lifetimes," Production and Operations Management, Production and Operations Management Society, vol. 32(3), pages 813-828, March.
    13. Özalp Özer & Wei Wei, 2004. "Inventory Control with Limited Capacity and Advance Demand Information," Operations Research, INFORMS, vol. 52(6), pages 988-1000, December.
    14. Kouki, Chaaben & Jemaï, Zied & Minner, Stefan, 2015. "A lost sales (r, Q) inventory control model for perishables with fixed lifetime and lead time," International Journal of Production Economics, Elsevier, vol. 168(C), pages 143-157.
    15. Qing Li & Peiwen Yu & Xiaoli Wu, 2016. "Managing Perishable Inventories in Retailing: Replenishment, Clearance Sales, and Segregation," Operations Research, INFORMS, vol. 64(6), pages 1270-1284, December.
    16. Puranam, Kartikeya & Novak, David C. & Lucas, Marilyn T. & Fung, Mark, 2017. "Managing blood inventory with multiple independent sources of supply," European Journal of Operational Research, Elsevier, vol. 259(2), pages 500-511.
    17. William L. Cooper, 2001. "Pathwise Properties and Performance Bounds for a Perishable Inventory System," Operations Research, INFORMS, vol. 49(3), pages 455-466, June.
    18. van Donselaar, Karel H. & Broekmeulen, Rob A.C.M., 2012. "Approximations for the relative outdating of perishable products by combining stochastic modeling, simulation and regression modeling," International Journal of Production Economics, Elsevier, vol. 140(2), pages 660-669.
    19. 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.
    20. Hanukov, Gabi & Avinadav, Tal & Chernonog, Tatyana & Yechiali, Uri, 2020. "A service system with perishable products where customers are either fastidious or strategic," International Journal of Production Economics, Elsevier, vol. 228(C).

    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:ormnsc:v:64:y:2018:i:11:p:5038-5061. 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.