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

The Dynamic Lot-Sizing Problem with Startup and Reservation Costs

Author

Listed:
  • Uday S. Karmarkar

    (University of Rochester, Rochester, New York)

  • Sham Kekre

    (Eastman Kodak Company, Rochester, New York)

  • Sunder Kekre

    (Carnegie-Mellon University, Pittsburgh, Pennsylvania)

Abstract

Dynamic lot-sizing models often assume that a production system incurs a fixed cost in each period that production is positive. In this paper, we consider a model with a startup cost incurred for switching on the production facility and a separate reservation cost charged for keeping the facility on whether or not it is used for production. Computationally, this problem is as hard as the usual model; the general capacitated case is NP-hard. We present a dynamic programming algorithm for the uncapacitated case, and a branch-and-bound approach using Lagrangian relaxation for the capacitated problem. We report computational experience on both the quality of the bounds employed and the effectiveness of the algorithm.

Suggested Citation

  • Uday S. Karmarkar & Sham Kekre & Sunder Kekre, 1987. "The Dynamic Lot-Sizing Problem with Startup and Reservation Costs," Operations Research, INFORMS, vol. 35(3), pages 389-398, June.
    • Handle: RePEc:inm:oropre:v:35:y:1987:i:3:p:389-398
    DOI: 10.1287/opre.35.3.389
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.35.3.389
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.35.3.389?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. Hoesel C.P.M. van & Wagelmans A.P.M., 1997. "Fully polynomial approximation schemes for single-item capacitated economic lot-sizing problems," Research Memorandum 014, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    2. 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.
    3. van Hoesel, C.P.M. & Wagelmans, A.P.M., 1997. "Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems," Econometric Institute Research Papers EI 9735/A, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
    4. Drexl, Andreas & Haase, Knut, 1995. "Proportional lotsizing and scheduling," International Journal of Production Economics, Elsevier, vol. 40(1), pages 73-87, June.
    5. Hadi Farhangi, 2021. "Multi-Echelon Supply Chains with Lead Times and Uncertain Demands," SN Operations Research Forum, Springer, vol. 2(3), pages 1-25, September.
    6. Berk, Emre & Toy, Ayhan Ozgur & Hazir, Oncu, 2008. "Single item lot-sizing problem for a warm/cold process with immediate lost sales," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1251-1267, June.
    7. Cakanyildirim, Metin & Bookbinder, James H. & Gerchak, Yigal, 2000. "Continuous review inventory models where random lead time depends on lot size and reserved capacity," International Journal of Production Economics, Elsevier, vol. 68(3), pages 217-228, December.
    8. Rapine, Christophe & Goisque, Guillaume & Akbalik, Ayse, 2018. "Energy-aware lot sizing problem: Complexity analysis and exact algorithms," International Journal of Production Economics, Elsevier, vol. 203(C), pages 254-263.
    9. Drexl, Andreas & Haase, Knut, 1992. "A new type of model for multi-item capacitated dynamic lotsizing and scheduling," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 286, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    10. Kimms, A., 1996. "Multi-level, single-machine lot sizing and scheduling (with initial inventory)," European Journal of Operational Research, Elsevier, vol. 89(1), pages 86-99, February.
    11. Vernon Ning Hsu, 2000. "Dynamic Economic Lot Size Model with Perishable Inventory," Management Science, INFORMS, vol. 46(8), pages 1159-1169, August.
    12. 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.
    13. van Hoesel, C.P.M. & Wagelmans, A., 1997. "Fully polynomial approximation schemes for single-item capacitated economic lot-sizing problems," Research Memorandum 029, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    14. Haase, Knut & Kimms, Alf, 1996. "Lot sizing and scheduling with sequence dependent setup costs and times and efficient rescheduling opportunities," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 393, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    15. Ishwar Murthy, 1993. "Solving the multiperiod assignment problem with start‐up costs using dual ascent," Naval Research Logistics (NRL), John Wiley & Sons, vol. 40(3), pages 325-344, April.
    16. C. P. M. van Hoesel & A. P. M. Wagelmans, 2001. "Fully Polynomial Approximation Schemes for Single-Item Capacitated Economic Lot-Sizing Problems," Mathematics of Operations Research, INFORMS, vol. 26(2), pages 339-357, May.
    17. Leonardo Lozano & J. Cole Smith, 2017. "A Backward Sampling Framework for Interdiction Problems with Fortification," INFORMS Journal on Computing, INFORMS, vol. 29(1), pages 123-139, February.
    18. 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.
    19. Yevgenia Mikhaylidi & Hussein Naseraldin & Liron Yedidsion, 2015. "Operations scheduling under electricity time-varying prices," International Journal of Production Research, Taylor & Francis Journals, vol. 53(23), pages 7136-7157, December.

    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:35:y:1987:i:3:p:389-398. 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.