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

Lagrangean relaxation based heuristics for lot sizing with setup times

Author

Listed:
  • Süral, Haldun
  • Denizel, Meltem
  • Van Wassenhove, Luk N.

Abstract

We consider a lot sizing problem with setup times where the objective is to minimize the total inventory carrying cost only. The demand is dynamic over time and there is a single resource of limited capacity. We show that the approaches implemented in the literature for more general versions of the problem do not perform well in this case. We examine the Lagrangean relaxation (LR) of demand constraints in a strong reformulation of the problem. We then design a primal heuristic to generate upper bounds and combine it with the LR problem within a subgradient optimization procedure. We also develop a simple branch and bound heuristic to solve the problem. Computational results on test problems taken from the literature show that our relaxation procedure produces consistently better solutions than the previously developed heuristics in the literature.

Suggested Citation

  • Süral, Haldun & Denizel, Meltem & Van Wassenhove, Luk N., 2009. "Lagrangean relaxation based heuristics for lot sizing with setup times," European Journal of Operational Research, Elsevier, vol. 194(1), pages 51-63, April.
    • Handle: RePEc:eee:ejores:v:194:y:2009:i:1:p:51-63
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(07)01149-6
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. William W. Trigeiro & L. Joseph Thomas & John O. McClain, 1989. "Capacitated Lot Sizing with Setup Times," Management Science, INFORMS, vol. 35(3), pages 353-366, March.
    2. Gerard M. Campbell & Vincent A. Mabert, 1991. "Cyclical Schedules for Capacitated Lot Sizing with Dynamic Demands," Management Science, INFORMS, vol. 37(4), pages 409-427, April.
    3. 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.
    4. Horst Tempelmeier & Matthias Derstroff, 1996. "A Lagrangean-Based Heuristic for Dynamic Multilevel Multiitem Constrained Lotsizing with Setup Times," Management Science, INFORMS, vol. 42(5), pages 738-757, May.
    5. Alan S. Manne, 1958. "Programming of Economic Lot Sizes," Management Science, INFORMS, vol. 4(2), pages 115-135, January.
    6. Diaby, M. & Bahl, H. C. & Karwan, M. H. & Zionts, S., 1992. "Capacitated lot-sizing and scheduling by Lagrangean relaxation," European Journal of Operational Research, Elsevier, vol. 59(3), pages 444-458, June.
    7. Uday S. Karmarkar, 1987. "Lot Sizes, Lead Times and In-Process Inventories," Management Science, INFORMS, vol. 33(3), pages 409-418, March.
    8. Kuik, Roelof & Salomon, Marc & van Wassenhove, Luk N., 1994. "Batching decisions: structure and models," European Journal of Operational Research, Elsevier, vol. 75(2), pages 243-263, June.
    9. Bezalel Gavish & Robert E. Johnson, 1990. "A Fully Polynomial Approximation Scheme for Single-Product Scheduling in a Finite Capacity Facility," Operations Research, INFORMS, vol. 38(1), pages 70-83, February.
    10. Elena Katok & Holly S. Lewis & Terry P. Harrison, 1998. "Lot Sizing in General Assembly Systems with Setup Costs, Setup Times, and Multiple Constrained Resources," Management Science, INFORMS, vol. 44(6), pages 859-877, June.
    11. Lozano, Sebastian & Larraneta, Juan & Onieva, Luis, 1991. "Primal-dual approach to the single level capacitated lot-sizing problem," European Journal of Operational Research, Elsevier, vol. 51(3), pages 354-366, April.
    12. Brahimi, Nadjib & Dauzere-Peres, Stephane & Najid, Najib M. & Nordli, Atle, 2006. "Single item lot sizing problems," European Journal of Operational Research, Elsevier, vol. 168(1), pages 1-16, January.
    13. Sural, H. & van Wassenhove, L.N. & Potts, C.N., 1997. "The Bounded Knapsack Problem with Setups," INSEAD 97/71, INSEAD, Centre for the Management of Environmental Resources. The European Institute of Business Administration..
    14. 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.
    15. Terry P. Harrison & Holly S. Lewis, 1996. "Lot Sizing in Serial Assembly Systems with Multiple Constrained Resources," Management Science, INFORMS, vol. 42(1), pages 19-36, January.
    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. 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. Silvio Alexandre de Araujo & Bert De Reyck & Zeger Degraeve & Ioannis Fragkos & Raf Jans, 2015. "Period Decompositions for the Capacitated Lot Sizing Problem with Setup Times," INFORMS Journal on Computing, INFORMS, vol. 27(3), pages 431-448, August.
    3. Melega, Gislaine Mara & de Araujo, Silvio Alexandre & Jans, Raf, 2018. "Classification and literature review of integrated lot-sizing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 271(1), pages 1-19.
    4. Kerem Akartunalı & Ioannis Fragkos & Andrew J. Miller & Tao Wu, 2016. "Local Cuts and Two-Period Convex Hull Closures for Big-Bucket Lot-Sizing Problems," INFORMS Journal on Computing, INFORMS, vol. 28(4), pages 766-780, November.
    5. Neves-Moreira, Fábio & Almada-Lobo, Bernardo & Cordeau, Jean-François & Guimarães, Luís & Jans, Raf, 2019. "Solving a large multi-product production-routing problem with delivery time windows," Omega, Elsevier, vol. 86(C), pages 154-172.
    6. Tao Wu, 2022. "Predictive Search for Capacitated Multi-Item Lot Sizing Problems," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 385-406, January.
    7. Cunha, Artur Lovato & Santos, Maristela Oliveira & Morabito, Reinaldo & Barbosa-Póvoa, Ana, 2018. "An integrated approach for production lot sizing and raw material purchasing," European Journal of Operational Research, Elsevier, vol. 269(3), pages 923-938.
    8. Zhang, Zhi-Hai & Jiang, Hai & Pan, Xunzhang, 2012. "A Lagrangian relaxation based approach for the capacitated lot sizing problem in closed-loop supply chain," International Journal of Production Economics, Elsevier, vol. 140(1), pages 249-255.
    9. Muller, Laurent Flindt & Spoorendonk, Simon & Pisinger, David, 2012. "A hybrid adaptive large neighborhood search heuristic for lot-sizing with setup times," European Journal of Operational Research, Elsevier, vol. 218(3), pages 614-623.
    10. Dziuba, Daryna & Almeder, Christian, 2023. "New construction heuristic for capacitated lot sizing problems," European Journal of Operational Research, Elsevier, vol. 311(3), pages 906-920.
    11. Ioannis Fragkos & Zeger Degraeve & Bert De Reyck, 2016. "A Horizon Decomposition Approach for the Capacitated Lot-Sizing Problem with Setup Times," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 465-482, August.
    12. Taş, Duygu & Gendreau, Michel & Jabali, Ola & Jans, Raf, 2019. "A capacitated lot sizing problem with stochastic setup times and overtime," European Journal of Operational Research, Elsevier, vol. 273(1), pages 146-159.
    13. Diego Fiorotto & Silvio Araujo, 2014. "Reformulation and a Lagrangian heuristic for lot sizing problem on parallel machines," Annals of Operations Research, Springer, vol. 217(1), pages 213-231, June.

    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. Brahimi, Nadjib & Dauzere-Peres, Stephane & Najid, Najib M. & Nordli, Atle, 2006. "Single item lot sizing problems," European Journal of Operational Research, Elsevier, vol. 168(1), pages 1-16, January.
    2. 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.
    3. Helber, Stefan & Sahling, Florian, 2010. "A fix-and-optimize approach for the multi-level capacitated lot sizing problem," International Journal of Production Economics, Elsevier, vol. 123(2), pages 247-256, February.
    4. Toledo, Franklina Maria Bragion & Armentano, Vinicius Amaral, 2006. "A Lagrangian-based heuristic for the capacitated lot-sizing problem in parallel machines," European Journal of Operational Research, Elsevier, vol. 175(2), pages 1070-1083, December.
    5. Melega, Gislaine Mara & de Araujo, Silvio Alexandre & Jans, Raf, 2018. "Classification and literature review of integrated lot-sizing and cutting stock problems," European Journal of Operational Research, Elsevier, vol. 271(1), pages 1-19.
    6. Berretta, Regina & Rodrigues, Luiz Fernando, 2004. "A memetic algorithm for a multistage capacitated lot-sizing problem," International Journal of Production Economics, Elsevier, vol. 87(1), pages 67-81, January.
    7. Kerem Akartunalı & Andrew Miller, 2012. "A computational analysis of lower bounds for big bucket production planning problems," Computational Optimization and Applications, Springer, vol. 53(3), pages 729-753, December.
    8. Nascimento, Mariá C.V. & Resende, Mauricio G.C. & Toledo, Franklina M.B., 2010. "GRASP heuristic with path-relinking for the multi-plant capacitated lot sizing problem," European Journal of Operational Research, Elsevier, vol. 200(3), pages 747-754, February.
    9. 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.
    10. Wolosewicz, Cathy & Dauzère-Pérès, Stéphane & Aggoune, Riad, 2015. "A Lagrangian heuristic for an integrated lot-sizing and fixed scheduling problem," European Journal of Operational Research, Elsevier, vol. 244(1), pages 3-12.
    11. Nadjib Brahimi & Stéphane Dauzère-Pérès & Najib M. Najid, 2006. "Capacitated Multi-Item Lot-Sizing Problems with Time Windows," Operations Research, INFORMS, vol. 54(5), pages 951-967, October.
    12. Okhrin, Irena & Richter, Knut, 2011. "The linear dynamic lot size problem with minimum order quantity," International Journal of Production Economics, Elsevier, vol. 133(2), pages 688-693, October.
    13. 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.
    14. Sônia Poltroniere & Kelly Poldi & Franklina Toledo & Marcos Arenales, 2008. "A coupling cutting stock-lot sizing problem in the paper industry," Annals of Operations Research, Springer, vol. 157(1), pages 91-104, January.
    15. 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.
    16. 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.
    17. Sahling, Florian & Buschkühl, Lisbeth & Tempelmeier, Horst & Helber, Stefan, 2008. "Solving a Multi-Level Capacitated Lot Sizing Problem with Multi-Period Setup Carry-Over via a Fix-and-Optimize Heuristic," Hannover Economic Papers (HEP) dp-400, Leibniz Universität Hannover, Wirtschaftswissenschaftliche Fakultät.
    18. Elena Katok & Holly S. Lewis & Terry P. Harrison, 1998. "Lot Sizing in General Assembly Systems with Setup Costs, Setup Times, and Multiple Constrained Resources," Management Science, INFORMS, vol. 44(6), pages 859-877, June.
    19. Drexl, A. & Kimms, A., 1997. "Lot sizing and scheduling -- Survey and extensions," European Journal of Operational Research, Elsevier, vol. 99(2), pages 221-235, June.
    20. Yves Pochet & Mathieu Van Vyve, 2004. "A General Heuristic for Production Planning Problems," INFORMS Journal on Computing, INFORMS, vol. 16(3), pages 316-327, 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:eee:ejores:v:194:y:2009:i:1:p:51-63. 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.