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

Worst-Case Analysis for a General Class of Online Lot-Sizing Heuristics

Author

Listed:
  • Wilco Van den Heuvel

    () (Econometric Institute and Erasmus Research Institute of Management, Erasmus University Rotterdam, 3000 DR Rotterdam, The Netherlands)

  • Albert P. M. Wagelmans

    () (Econometric Institute and Erasmus Research Institute of Management, Erasmus University Rotterdam, 3000 DR Rotterdam, The Netherlands)

Abstract

In this paper, we analyze the worst-case performance of heuristics for the classical economic lot-sizing problem with time-invariant cost parameters. We consider a general class of online heuristics that is often applied in a rolling-horizon environment. We develop a procedure to systematically construct worst-case instances for a fixed time horizon and use it to derive worst-case problem instances for an infinite time horizon. Our analysis shows that any online heuristic has a worst-case ratio of at least 2.

Suggested Citation

  • Wilco Van den Heuvel & Albert P. M. Wagelmans, 2010. "Worst-Case Analysis for a General Class of Online Lot-Sizing Heuristics," Operations Research, INFORMS, vol. 58(1), pages 59-67, February.
  • Handle: RePEc:inm:oropre:v:58:y:2010:i:1:p:59-67
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1080.0662
    Download Restriction: no

    Other versions of this item:

    References listed on IDEAS

    as
    1. Sven Axsäter, 1985. "Note---Performance Bounds for Lot Sizing Heuristics," Management Science, INFORMS, vol. 31(5), pages 634-640, May.
    2. Sven Axsäter, 1988. "A Sequential Lot Sizing Heuristic with Optimal Average Performance," Management Science, INFORMS, vol. 34(11), pages 1324-1332, November.
    3. van den Heuvel, W.J. & Wagelmans, A.P.M., 2008. "A holding cost bound for the economic lot-sizing problem with time-invariant cost parameters," Econometric Institute Research Papers EI 2008-10, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    4. Harvey M. Wagner & Thomson M. Whitin, 1958. "Dynamic Version of the Economic Lot Size Model," Management Science, INFORMS, vol. 5(1), pages 89-96, October.
    5. Marshall Fisher & Kamalini Ramdas & Yu-Sheng Zheng, 2001. "Ending Inventory Valuation in Multiperiod Production Scheduling," Management Science, INFORMS, vol. 47(5), pages 679-692, May.
    6. repec:wly:navres:v:39:y:1992:i:6:p:801-813 is not listed on IDEAS
    7. Axsater, Sven, 1982. "Worst case performance for lot sizing heuristics," European Journal of Operational Research, Elsevier, vol. 9(4), pages 339-343, April.
    8. repec:spr:joptap:v:143:y:2009:i:3:d:10.1007_s10957-009-9574-8 is not listed on IDEAS
    9. Hartmut Stadtler, 2000. "Improved Rolling Schedules for the Dynamic Single-Level Lot-Sizing Problem," Management Science, INFORMS, vol. 46(2), pages 318-326, February.
    10. Gabriel R. Bitran & Thomas L. Magnanti & Horacio H. Yanasse, 1984. "Approximation Methods for the Uncapacitated Dynamic Lot Size Problem," Management Science, INFORMS, vol. 30(9), pages 1121-1140, September.
    11. M. Florian & J. K. Lenstra & A. H. G. Rinnooy Kan, 1980. "Deterministic Production Planning: Algorithms and Complexity," Management Science, INFORMS, vol. 26(7), pages 669-679, July.
    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. van den Heuvel, W.J. & Wagelmans, A.P.M., 2008. "A holding cost bound for the economic lot-sizing problem with time-invariant cost parameters," Econometric Institute Research Papers EI 2008-10, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    2. Adam N. Elmachtoub & Retsef Levi, 2016. "Supply Chain Management with Online Customer Selection," Operations Research, INFORMS, vol. 64(2), pages 458-473, April.
    3. repec:eee:ejores:v:279:y:2019:i:2:p:449-458 is not listed on IDEAS
    4. repec:spr:joptap:v:143:y:2009:i:3:d:10.1007_s10957-009-9574-8 is not listed on IDEAS
    5. Adam N. Elmachtoub & Retsef Levi, 2015. "From Cost Sharing Mechanisms to Online Selection Problems," Mathematics of Operations Research, INFORMS, vol. 40(3), pages 542-557, March.
    6. repec:eee:ejores:v:263:y:2017:i:3:p:838-863 is not listed on IDEAS
    7. Jens Leoff & Heiner Ackermann & Karl-Heinz Küfer, 2016. "Time-hierarchical scheduling," Journal of Scheduling, Springer, vol. 19(3), pages 215-225, June.
    8. Niv Buchbinder & Tracy Kimbrel & Retsef Levi & Konstantin Makarychev & Maxim Sviridenko, 2013. "Online Make-to-Order Joint Replenishment Model: Primal-Dual Competitive Algorithms," Operations Research, INFORMS, vol. 61(4), pages 1014-1029, August.

    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:58:y:2010:i:1:p:59-67. 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: http://edirc.repec.org/data/inforea.html .

    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.