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
    DOI: 10.1287/opre.1080.0662
    as

    Download full text from publisher

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

    Other versions of this item:

    References listed on IDEAS

    as
    1. Stadtler, Hartmut, 2000. "Improved rolling schedules for the dynamic single level lot sizing problem," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 14079, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    2. Sven Axsäter, 1985. "Note---Performance Bounds for Lot Sizing Heuristics," Management Science, INFORMS, vol. 31(5), pages 634-640, May.
    3. Sven Axsäter, 1988. "A Sequential Lot Sizing Heuristic with Optimal Average Performance," Management Science, INFORMS, vol. 34(11), pages 1324-1332, November.
    4. 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.
    5. 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.
    6. 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.
    7. J. Brinkhuis, 2009. "Convex Duality and Calculus: Reduction to Cones," Journal of Optimization Theory and Applications, Springer, vol. 143(3), pages 439-453, December.
    8. Rita Vachani, 1992. "Performance of heuristics for the uncapacitated lot‐size problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 39(6), pages 801-813, October.
    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. Axsater, Sven, 1982. "Worst case performance for lot sizing heuristics," European Journal of Operational Research, Elsevier, vol. 9(4), pages 339-343, April.
    11. 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.
    12. 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. Guanqun Ni, 2023. "An improved online replenishment policy and its competitive ratio analysis for a purchase-to-order seller," Journal of Combinatorial Optimization, Springer, vol. 46(2), pages 1-14, September.
    3. Wenqiang Dai & Meng Zheng & Xu Chen & Zhuolin Yang, 0. "Online economic ordering problem for deteriorating items with limited price information," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-23.
    4. Adam N. Elmachtoub & Retsef Levi, 2016. "Supply Chain Management with Online Customer Selection," Operations Research, INFORMS, vol. 64(2), pages 458-473, April.
    5. Absi, Nabil & van den Heuvel, Wilco, 2019. "Worst case analysis of Relax and Fix heuristics for lot-sizing problems," European Journal of Operational Research, Elsevier, vol. 279(2), pages 449-458.
    6. J. Brinkhuis, 2009. "Convex Duality and Calculus: Reduction to Cones," Journal of Optimization Theory and Applications, Springer, vol. 143(3), pages 439-453, December.
    7. 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.
    8. Brahimi, Nadjib & Absi, Nabil & Dauzère-Pérès, Stéphane & Nordli, Atle, 2017. "Single-item dynamic lot-sizing problems: An updated survey," European Journal of Operational Research, Elsevier, vol. 263(3), pages 838-863.
    9. 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.
    10. Massonnet, G. & Gayon, J.-P. & Rapine, C., 2014. "Approximation algorithms for deterministic continuous-review inventory lot-sizing problems with time-varying demand," European Journal of Operational Research, Elsevier, vol. 234(3), pages 641-649.
    11. Wenqiang Dai & Meng Zheng & Xu Chen & Zhuolin Yang, 2022. "Online economic ordering problem for deteriorating items with limited price information," Journal of Combinatorial Optimization, Springer, vol. 44(4), pages 2246-2268, November.

    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. Charles, Mehdi & Dauzère-Pérès, Stéphane & Kedad-Sidhoum, Safia & Mazhoud, Issam, 2022. "Motivations and analysis of the capacitated lot-sizing problem with setup times and minimum and maximum ending inventories," European Journal of Operational Research, Elsevier, vol. 302(1), pages 203-220.
    2. Nguyen, Christine & Dessouky, Maged & Toriello, Alejandro, 2014. "Consolidation strategies for the delivery of perishable products," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 69(C), pages 108-121.
    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. Brahimi, Nadjib & Absi, Nabil & Dauzère-Pérès, Stéphane & Nordli, Atle, 2017. "Single-item dynamic lot-sizing problems: An updated survey," European Journal of Operational Research, Elsevier, vol. 263(3), pages 838-863.
    5. Jans, R.F. & Degraeve, Z., 2005. "Modeling Industrial Lot Sizing Problems: A Review," ERIM Report Series Research in Management ERS-2005-049-LIS, Erasmus Research Institute of Management (ERIM), ERIM is the joint research institute of the Rotterdam School of Management, Erasmus University and the Erasmus School of Economics (ESE) at Erasmus University Rotterdam.
    6. Mohammad Ebrahim Arbabian & Shi Chen & Kamran Moinzadeh, 2021. "Capacity Expansions with Bundled Supplies of Attributes: An Application to Server Procurement in Cloud Computing," Manufacturing & Service Operations Management, INFORMS, vol. 23(1), pages 191-209, 1-2.
    7. Karimi, B. & Fatemi Ghomi, S. M. T. & Wilson, J. M., 2003. "The capacitated lot sizing problem: a review of models and algorithms," Omega, Elsevier, vol. 31(5), pages 365-378, October.
    8. Wilco van den Heuvel & Albert P.M. Wagelmans, 2002. "A Note on Ending Inventory Valuation in Multiperiod Production Scheduling," Tinbergen Institute Discussion Papers 02-067/4, Tinbergen Institute.
    9. Toy, Ayhan Özgür & Berk, Emre, 2013. "Dynamic lot sizing for a warm/cold process: Heuristics and insights," International Journal of Production Economics, Elsevier, vol. 145(1), pages 53-66.
    10. Sahin, Funda & Powell Robinson, E. & Gao, Li-Lian, 2008. "Master production scheduling policy and rolling schedules in a two-stage make-to-order supply chain," International Journal of Production Economics, Elsevier, vol. 115(2), pages 528-541, October.
    11. Chung-Yee Lee & Sila Çetinkaya & Wikrom Jaruphongsa, 2003. "A Dynamic Model for Inventory Lot Sizing and Outbound Shipment Scheduling at a Third-Party Warehouse," Operations Research, INFORMS, vol. 51(5), pages 735-747, October.
    12. Narayanan, Arunachalam & Robinson, Powell, 2010. "Evaluation of joint replenishment lot-sizing procedures in rolling horizon planning systems," International Journal of Production Economics, Elsevier, vol. 127(1), pages 85-94, September.
    13. Christopher Suerie & Hartmut Stadtler, 2003. "The Capacitated Lot-Sizing Problem with Linked Lot Sizes," Management Science, INFORMS, vol. 49(8), pages 1039-1054, August.
    14. G. Rius-Sorolla & J. Maheut & S. Estellés-Miguel & J. P. García-Sabater, 2021. "Operations planning test bed under rolling horizons, multiproduct, multiechelon, multiprocess for capacitated production planning modelling with strokes," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 29(4), pages 1289-1315, December.
    15. repec:dau:papers:123456789/2078 is not listed on IDEAS
    16. Hartmut Stadtler & Malte Meistering, 2019. "Model formulations for the capacitated lot-sizing problem with service-level constraints," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(4), pages 1025-1056, December.
    17. Massonnet, G. & Gayon, J.-P. & Rapine, C., 2014. "Approximation algorithms for deterministic continuous-review inventory lot-sizing problems with time-varying demand," European Journal of Operational Research, Elsevier, vol. 234(3), pages 641-649.
    18. Suresh Chand & Vernon Ning Hsu & Suresh Sethi, 2002. "Forecast, Solution, and Rolling Horizons in Operations Management Problems: A Classified Bibliography," Manufacturing & Service Operations Management, INFORMS, vol. 4(1), pages 25-43, September.
    19. Jeunet, Jully, 2006. "Demand forecast accuracy and performance of inventory policies under multi-level rolling schedule environments," International Journal of Production Economics, Elsevier, vol. 103(1), pages 401-419, September.
    20. Chung-Yee Lee & Sila Çetinkaya & Albert P. M. Wagelmans, 2001. "A Dynamic Lot-Sizing Model with Demand Time Windows," Management Science, INFORMS, vol. 47(10), pages 1384-1395, October.
    21. Jans, Raf & Degraeve, Zeger, 2007. "Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1855-1875, March.

    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.

    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.