IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v294y2021i1p91-99.html
   My bibliography  Save this article

Computing optimal (R,s,S) policy parameters by a hybrid of branch-and-bound and stochastic dynamic programming

Author

Listed:
  • Visentin, Andrea
  • Prestwich, Steven
  • Rossi, Roberto
  • Tarim, S. Armagan

Abstract

A well-known control policy in stochastic inventory control is the (R,s,S) policy, in which inventory is raised to an order-up-to-level S at a review instant R whenever it falls below reorder-level s. To date, little or no work has been devoted to developing approaches for computing (R,s,S) policy parameters. In this work, we introduce a hybrid approach that exploits tree search to compute optimal replenishment cycles, and stochastic dynamic programming to compute (s,S) levels for a given cycle. Up to 99.8% of the search tree is pruned by a branch-and-bound technique with bounds generated by dynamic programming. A numerical study shows that the method can solve instances of realistic size in a reasonable time.

Suggested Citation

  • Visentin, Andrea & Prestwich, Steven & Rossi, Roberto & Tarim, S. Armagan, 2021. "Computing optimal (R,s,S) policy parameters by a hybrid of branch-and-bound and stochastic dynamic programming," European Journal of Operational Research, Elsevier, vol. 294(1), pages 91-99.
    • Handle: RePEc:eee:ejores:v:294:y:2021:i:1:p:91-99
    DOI: 10.1016/j.ejor.2021.01.012
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722172100014X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.01.012?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Kilic, Onur A. & Tunc, Huseyin, 2019. "Heuristics for the stochastic economic lot sizing problem with remanufacturing under backordering costs," European Journal of Operational Research, Elsevier, vol. 276(3), pages 880-892.
    2. Rossi, Roberto & Tarim, S. Armagan & Hnich, Brahim & Prestwich, Steven, 2010. "Computing the non-stationary replenishment cycle inventory policy under stochastic supplier lead-times," International Journal of Production Economics, Elsevier, vol. 127(1), pages 180-189, September.
    3. Zied Babai, M. & Syntetos, Aris A. & Teunter, Ruud, 2010. "On the empirical performance of (T, s, S) heuristics," European Journal of Operational Research, Elsevier, vol. 202(2), pages 466-472, April.
    4. Özen, Ulaş & Doğru, Mustafa K. & Armagan Tarim, S., 2012. "Static-dynamic uncertainty strategy for a single-item stochastic inventory control problem," Omega, Elsevier, vol. 40(3), pages 348-357.
    5. M. Fattahi & M. Mahootchi & S.M. Moattar Husseini & E. Keyvanshokooh & F. Alborzi, 2015. "Investigating replenishment policies for centralised and decentralised supply chains using stochastic programming approach," International Journal of Production Research, Taylor & Francis Journals, vol. 53(1), pages 41-69, January.
    6. Bijvank, Marco & Vis, Iris F.A., 2012. "Lost-sales inventory systems with a service level criterion," European Journal of Operational Research, Elsevier, vol. 220(3), pages 610-618.
    7. James H. Bookbinder & Jin-Yan Tan, 1988. "Strategies for the Probabilistic Lot-Sizing Problem with Service-Level Constraints," Management Science, INFORMS, vol. 34(9), pages 1096-1108, September.
    8. 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.
    9. Peter C. Verhoef & Laurens M. Sloot, 2006. "Out-of-Stock: Reactions, Antecedents, Management Solutions, and a Future Perspective," Springer Books, in: Manfred Krafft & Murali K. Mantrala (ed.), Retailing in the 21st Century, pages 239-253, Springer.
    10. M Bijvank & I F A Vis, 2012. "Inventory control for point-of-use locations in hospitals," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 63(4), pages 497-510, April.
    11. Monthatipkul, Chumpol & Yenradee, Pisal, 2008. "Inventory/distribution control system in a one-warehouse/multi-retailer supply chain," International Journal of Production Economics, Elsevier, vol. 114(1), pages 119-133, July.
    12. Sridhar Bashyam & Michael C. Fu, 1998. "Optimization of (s, S) Inventory Systems with Random Lead Times and a Service Level Constraint," Management Science, INFORMS, vol. 44(12-Part-2), pages 243-256, December.
    13. Schneider, Helmut & Rinks, Dan B., 1991. "Empirical study of a new procedure for allocating safety stock in a wholesale inventory system," International Journal of Production Economics, Elsevier, vol. 24(1-2), pages 181-189, November.
    14. Guillermo Cabrera & Pablo A. Miranda & Enrique Cabrera & Ricardo Soto & Broderick Crawford & Jose Miguel Rubio & Fernando Paredes, 2013. "Solving a Novel Inventory Location Model with Stochastic Constraints and Inventory Control Policy," Mathematical Problems in Engineering, Hindawi, vol. 2013, pages 1-12, November.
    15. Rossi, Roberto & Tarim, S. Armagan & Hnich, Brahim & Prestwich, Steven, 2011. "A state space augmentation algorithm for the replenishment cycle inventory policy," International Journal of Production Economics, Elsevier, vol. 133(1), pages 377-384, September.
    16. Alejandro Gutierrez-Alcoba & Roberto Rossi & Belen Martin-Barragan & Eligius M.T. Hendrix, 2017. "A simple heuristic for perishable item inventory control under non-stationary stochastic demand," International Journal of Production Research, Taylor & Francis Journals, vol. 55(7), pages 1885-1897, April.
    17. A.G. Lagodimos & I.T. Christou & K. Skouri, 2012. "Optimal (, , ) batch-ordering policy under stationary demand," International Journal of Systems Science, Taylor & Francis Journals, vol. 43(9), pages 1774-1784.
    18. Lopez Alvarez, Jose A. & Buijs, Paul & Kilic, Onur A. & Vis, Iris F.A., 2020. "An inventory control policy for liquefied natural gas as a transportation fuel," Omega, Elsevier, vol. 90(C).
    19. Kilic, Onur A. & Tarim, S. Armagan, 2011. "An investigation of setup instability in non-stationary stochastic inventory systems," International Journal of Production Economics, Elsevier, vol. 133(1), pages 286-292, September.
    20. Claudio Araya-Sassi & Pablo A. Miranda & Germán Paredes-Belmar, 2018. "Lagrangian Relaxation for an Inventory Location Problem with Periodic Inventory Control and Stochastic Capacity Constraints," Mathematical Problems in Engineering, Hindawi, vol. 2018, pages 1-27, October.
    21. Wang, Huihui & Yu, Yimin & Zhang, Wei & Hua, Zhongsheng, 2019. "Procurement strategies for lost-sales inventory systems with all-units discounts," European Journal of Operational Research, Elsevier, vol. 272(2), pages 539-548.
    22. Tarim, S. Armagan & Kingsman, Brian G., 2004. "The stochastic dynamic production/inventory lot-sizing problem with service-level constraints," International Journal of Production Economics, Elsevier, vol. 88(1), pages 105-119, March.
    23. Huseyin Tunc & Onur A. Kilic & S. Armagan Tarim & Roberto Rossi, 2018. "An Extended Mixed-Integer Programming Formulation and Dynamic Cut Generation Approach for the Stochastic Lot-Sizing Problem," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 492-506, August.
    24. Placido dos Santos, Felipe Silva & Oliveira, Fabricio, 2019. "An enhanced L-Shaped method for optimizing periodic-review inventory control problems modeled via two-stage stochastic programming," European Journal of Operational Research, Elsevier, vol. 275(2), pages 677-693.
    25. Dillon, Mary & Oliveira, Fabricio & Abbasi, Babak, 2017. "A two-stage stochastic programming model for inventory management in the blood supply chain," International Journal of Production Economics, Elsevier, vol. 187(C), pages 27-41.
    26. Powell, Warren B., 2019. "A unified framework for stochastic optimization," European Journal of Operational Research, Elsevier, vol. 275(3), pages 795-821.
    27. Roberto Rossi & S. Tarim & Brahim Hnich & Steven Prestwich, 2012. "Constraint programming for stochastic inventory systems under shortage cost," Annals of Operations Research, Springer, vol. 195(1), pages 49-71, May.
    28. 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.
    29. Paul Zipkin, 2008. "Old and New Methods for Lost-Sales Inventory Systems," Operations Research, INFORMS, vol. 56(5), pages 1256-1263, October.
    30. Edward A. Silver, 1981. "Operations Research in Inventory Management: A Review and Critique," Operations Research, INFORMS, vol. 29(4), pages 628-645, August.
    31. Maxim A Bushuev & Alfred Guiffrida & M. Y. Jaber & Mehmood Khan, 2015. "A review of inventory lot sizing review papers," Management Research Review, Emerald Group Publishing Limited, vol. 38(3), pages 283-298, March.
    32. Lagodimos, A.G. & Christou, I.T. & Skouri, K., 2012. "Computing globally optimal (s,S,T) inventory policies," Omega, Elsevier, vol. 40(5), pages 660-671.
    33. Rossi, Roberto & Kilic, Onur A. & Tarim, S. Armagan, 2015. "Piecewise linear approximations for the static–dynamic uncertainty strategy in stochastic lot-sizing," Omega, Elsevier, vol. 50(C), pages 126-140.
    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. Angelos Kourepis & Alexandros Diamantidis & Stylianos Koukoumialos, 2022. "Exact analysis of a push–pull system with multiple non identical retailers, a distribution center and multiple non identical unreliable suppliers with supply disruptions," Operational Research, Springer, vol. 22(5), pages 4801-4827, November.
    2. Ma, Xiyuan & Rossi, Roberto & Archibald, Thomas Welsh, 2022. "Approximations for non-stationary stochastic lot-sizing under (s,Q)-type policy," European Journal of Operational Research, Elsevier, vol. 298(2), pages 573-584.

    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. Rossi, Roberto & Kilic, Onur A. & Tarim, S. Armagan, 2015. "Piecewise linear approximations for the static–dynamic uncertainty strategy in stochastic lot-sizing," Omega, Elsevier, vol. 50(C), pages 126-140.
    2. Dural-Selcuk, Gozdem & Rossi, Roberto & Kilic, Onur A. & Tarim, S. Armagan, 2020. "The benefit of receding horizon control: Near-optimal policies for stochastic inventory control," Omega, Elsevier, vol. 97(C).
    3. Ma, Xiyuan & Rossi, Roberto & Archibald, Thomas Welsh, 2022. "Approximations for non-stationary stochastic lot-sizing under (s,Q)-type policy," European Journal of Operational Research, Elsevier, vol. 298(2), pages 573-584.
    4. Huseyin Tunc & Onur A. Kilic & S. Armagan Tarim & Roberto Rossi, 2018. "An Extended Mixed-Integer Programming Formulation and Dynamic Cut Generation Approach for the Stochastic Lot-Sizing Problem," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 492-506, August.
    5. Gurkan, M. Edib & Tunc, Huseyin & Tarim, S. Armagan, 2022. "The joint stochastic lot sizing and pricing problem," Omega, Elsevier, vol. 108(C).
    6. Chen, Zhen & Rossi, Roberto, 2021. "A dynamic ordering policy for a stochastic inventory problem with cash constraints," Omega, Elsevier, vol. 102(C).
    7. Roberto Rossi & S. Armagan Tarim & Ramesh Bollapragada, 2012. "Constraint-Based Local Search for Inventory Control Under Stochastic Demand and Lead Time," INFORMS Journal on Computing, INFORMS, vol. 24(1), pages 66-80, February.
    8. Liu, Kanglin & Zhang, Zhi-Hai, 2018. "Capacitated disassembly scheduling under stochastic yield and demand," European Journal of Operational Research, Elsevier, vol. 269(1), pages 244-257.
    9. Tunc, Huseyin & Kilic, Onur A. & Tarim, S. Armagan & Eksioglu, Burak, 2013. "A simple approach for assessing the cost of system nervousness," International Journal of Production Economics, Elsevier, vol. 141(2), pages 619-625.
    10. Sereshti, Narges & Adulyasak, Yossiri & Jans, Raf, 2021. "The value of aggregate service levels in stochastic lot sizing problems," Omega, Elsevier, vol. 102(C).
    11. 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.
    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. Choudhary, Devendra & Shankar, Ravi, 2015. "The value of VMI beyond information sharing in a single supplier multiple retailers supply chain under a non-stationary (Rn, Sn) policy," Omega, Elsevier, vol. 51(C), pages 59-70.
    14. Koca, Esra & Yaman, Hande & Selim Aktürk, M., 2015. "Stochastic lot sizing problem with controllable processing times," Omega, Elsevier, vol. 53(C), pages 1-10.
    15. Pauls-Worm, Karin G.J. & Hendrix, Eligius M.T. & Haijema, René & van der Vorst, Jack G.A.J., 2014. "An MILP approximation for ordering perishable products with non-stationary demand and service level constraints," International Journal of Production Economics, Elsevier, vol. 157(C), pages 133-146.
    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—Discrete‐time case," Production and Operations Management, Production and Operations Management Society, vol. 32(1), pages 131-153, January.
    17. Rossi, Roberto & Tarim, S. Armagan & Hnich, Brahim & Prestwich, Steven, 2010. "Computing the non-stationary replenishment cycle inventory policy under stochastic supplier lead-times," International Journal of Production Economics, Elsevier, vol. 127(1), pages 180-189, September.
    18. Roberto Rossi & S. Tarim & Brahim Hnich & Steven Prestwich, 2012. "Constraint programming for stochastic inventory systems under shortage cost," Annals of Operations Research, Springer, vol. 195(1), pages 49-71, May.
    19. Tarim, S. Armagan & Smith, Barbara M., 2008. "Constraint programming for computing non-stationary (R, S) inventory policies," European Journal of Operational Research, Elsevier, vol. 189(3), pages 1004-1021, September.
    20. Özen, Ulaş & Doğru, Mustafa K. & Armagan Tarim, S., 2012. "Static-dynamic uncertainty strategy for a single-item stochastic inventory control problem," Omega, Elsevier, vol. 40(3), pages 348-357.

    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:eee:ejores:v:294:y:2021:i:1:p:91-99. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.