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

An Efficient Algorithm for Computing Optimal ( s , S ) Policies

Author

Listed:
  • Awi Federgruen

    (Columbia University, New York, New York)

  • Paul Zipkin

    (Columbia University, New York, New York)

Abstract

This paper presents an algorithm to compute an optimal ( s , S ) policy under standard assumptions (stationary data, well-behaved one-period costs, discrete demand, full backlogging, and the average-cost criterion). The method is iterative, starting with an arbitrary, given ( s , S ) policy and converging to an optimal policy in a finite number of iterations. Any of the available approximations can thus be used as an initial solution. Each iteration requires only modest computations. Also, a lower bound on the true optimal cost can be computed and used in a termination test. Empirical testing suggests very fast convergence.

Suggested Citation

  • Awi Federgruen & Paul Zipkin, 1984. "An Efficient Algorithm for Computing Optimal ( s , S ) Policies," Operations Research, INFORMS, vol. 32(6), pages 1268-1285, December.
    • Handle: RePEc:inm:oropre:v:32:y:1984:i:6:p:1268-1285
    DOI: 10.1287/opre.32.6.1268
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.32.6.1268
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.32.6.1268?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
    ---><---

    Citations

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


    Cited by:

    1. Pisch, Frank, 2020. "Managing global production: theory and evidence from just-in-time supply chains," LSE Research Online Documents on Economics 108488, London School of Economics and Political Science, LSE Library.
    2. Tunc, Huseyin & Kilic, Onur A. & Tarim, S. Armagan & Eksioglu, Burak, 2011. "The cost of using stationary inventory policies when demand is non-stationary," Omega, Elsevier, vol. 39(4), pages 410-415, August.
    3. D. Beyer & S. P. Sethi, 1999. "The Classical Average-Cost Inventory Models of Iglehart and Veinott–Wagner Revisited," Journal of Optimization Theory and Applications, Springer, vol. 101(3), pages 523-555, June.
    4. Lee, Jun-Yeon & Ren, Louie, 2011. "Vendor-managed inventory in a global environment with exchange rate uncertainty," International Journal of Production Economics, Elsevier, vol. 130(2), pages 169-174, April.
    5. Chou, Mabel & Sim, Chee-Khian & Yuan, Xue-Ming, 2013. "Optimal policies for inventory systems with two types of product sharing common hardware platforms: Single period and finite horizon," European Journal of Operational Research, Elsevier, vol. 224(2), pages 283-292.
    6. Gah-Yi Ban, 2020. "Confidence Intervals for Data-Driven Inventory Policies with Demand Censoring," Operations Research, INFORMS, vol. 68(2), pages 309-326, March.
    7. 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.
    8. Y. Feng & J. Sun, 2001. "Computing the Optimal Replenishment Policy for Inventory Systems with Random Discount Opportunities," Operations Research, INFORMS, vol. 49(5), pages 790-795, October.
    9. 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.
    10. Chan, Gin Hor & Song, Yuyue, 2003. "A dynamic analysis of the single-item periodic stochastic inventory system with order capacity," European Journal of Operational Research, Elsevier, vol. 146(3), pages 529-542, May.
    11. 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.
    12. Kleijnen, J.P.C. & Wan, J., 2007. "Optimization of simulated systems : OptQuest and alternatives [also see “Simulation for the optimization of (s, S) inventory system with random lead times and a service level constraint by using Arena," Other publications TiSEM ffaee312-9f6a-4452-9ccc-9, Tilburg University, School of Economics and Management.
    13. 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.
    14. Xie, Xiaolan, 1998. "Stability analysis and optimization of an inventory system with bounded orders," European Journal of Operational Research, Elsevier, vol. 110(1), pages 126-149, October.
    15. 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.
    16. B S Maddah & M Y Jaber & N E Abboud, 2004. "Periodic review (s, S) inventory model with permissible delay in payments," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(2), pages 147-159, February.
    17. Bijvank, Marco & Vis, Iris F.A., 2011. "Lost-sales inventory theory: A review," European Journal of Operational Research, Elsevier, vol. 215(1), pages 1-13, November.
    18. Nir Halman & Diego Klabjan & Mohamed Mostagir & Jim Orlin & David Simchi-Levi, 2009. "A Fully Polynomial-Time Approximation Scheme for Single-Item Stochastic Inventory Control with Discrete Demand," Mathematics of Operations Research, INFORMS, vol. 34(3), pages 674-685, August.
    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. 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.
    21. Chen, Zhen & Rossi, Roberto, 2021. "A dynamic ordering policy for a stochastic inventory problem with cash constraints," Omega, Elsevier, vol. 102(C).
    22. Kilic, Onur A. & Tarim, S. Armagan, 2024. "A simple heuristic for computing non-stationary inventory policies based on function approximation," European Journal of Operational Research, Elsevier, vol. 316(3), pages 899-905.
    23. 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).

    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:32:y:1984:i:6:p:1268-1285. 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.

    We have no bibliographic references for this item. You can help adding them by using 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.