IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v31y2025i1d10.1007_s10732-024-09539-w.html
   My bibliography  Save this article

Lagrangian-based heuristics for production planning with perishable products, scarce resources, and sequence-dependent setup times

Author

Listed:
  • Willy A. Oliveira Soler

    (Universidade Federal de Mato Grosso do Sul
    Universidade de São Paulo)

  • Maristela O. Santos

    (Universidade de São Paulo)

  • Kerem Akartunalı

    (University of Strathclyde)

Abstract

In this paper, we study a lot-sizing and scheduling problem apparent in the food industry that stemmed originally from the Brazilian meat production sector. More specifically, we consider a production environment in which various production lines share a set of scarce production resources. Therefore, only a subset of the existing production lines can simultaneously operate in each period under the limitations of the availability of resources. Moreover, we consider sequence-dependent setup times and costs, significant inventory holding costs, backlogging, and perishable products. The problem is formulated as a mixed integer programming model, and we propose four Lagrangian-based heuristics to find high-quality solutions for challenging instances. A computational study shows that proposed approaches are very competitive in solving the problem, outperforming methods already established in the literature.

Suggested Citation

  • Willy A. Oliveira Soler & Maristela O. Santos & Kerem Akartunalı, 2025. "Lagrangian-based heuristics for production planning with perishable products, scarce resources, and sequence-dependent setup times," Journal of Heuristics, Springer, vol. 31(1), pages 1-35, March.
    • Handle: RePEc:spr:joheur:v:31:y:2025:i:1:d:10.1007_s10732-024-09539-w
    DOI: 10.1007/s10732-024-09539-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-024-09539-w
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10732-024-09539-w?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
    ---><---

    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. 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.
    3. Millar, Harvey H. & Yang, Minzhu, 1994. "Lagrangian heuristics for the capacitated multi-item lot-sizing problem with backordering," International Journal of Production Economics, Elsevier, vol. 34(1), pages 1-15, February.
    4. Fleischmann, B. & Meyr, H., 1997. "The General Lotsizing and Scheduling Problem," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 36068, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    5. 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.
    6. 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.
    7. 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.
    8. Fleischmann, Bernhard, 1994. "The discrete lot-sizing and scheduling problem with sequence-dependent setup costs," European Journal of Operational Research, Elsevier, vol. 75(2), pages 395-404, June.
    9. Guimarães, Luis & Klabjan, Diego & Almada-Lobo, Bernardo, 2014. "Modeling lotsizing and scheduling problems with sequence dependent setups," European Journal of Operational Research, Elsevier, vol. 239(3), pages 644-662.
    10. 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.
    11. Willy A. O. Soler & Maristela O. Santos & Kerem Akartunalı, 2021. "MIP approaches for a lot sizing and scheduling problem on multiple production lines with scarce resources, temporary workstations, and perishable products," Journal of the Operational Research Society, Taylor & Francis Journals, vol. 72(8), pages 1691-1706, August.
    12. Fleischmann, Bernhard, 1990. "The discrete lot-sizing and scheduling problem," European Journal of Operational Research, Elsevier, vol. 44(3), pages 337-348, February.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    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. Karina Copil & Martin Wörbelauer & Herbert Meyr & Horst Tempelmeier, 2017. "Simultaneous lotsizing and scheduling problems: a classification and review of models," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(1), pages 1-64, January.
    4. Sungmin Kang & Kavindra Malik & L. Joseph Thomas, 1999. "Lotsizing and Scheduling on Parallel Machines with Sequence-Dependent Setup Costs," Management Science, INFORMS, vol. 45(2), pages 273-289, February.
    5. Drexl, Andreas & Jordan, Carsten & Kimms, Alf, 1997. "Gruppierungs- und Reihenfolgeprobleme in der Fertigung," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 447, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    6. 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.
    7. Rohaninejad, Mohammad & Hanzálek, Zdeněk, 2023. "Multi-level lot-sizing and job shop scheduling with lot-streaming: Reformulation and solution approaches," International Journal of Production Economics, Elsevier, vol. 263(C).
    8. 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.
    9. Meyr, H., 2000. "Simultaneous lotsizing and scheduling by combining local search with dual reoptimization," European Journal of Operational Research, Elsevier, vol. 120(2), pages 311-326, January.
    10. 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.
    11. Gaetan Belvaux & Laurence A. Wolsey, 2000. "bc --- prod: A Specialized Branch-and-Cut System for Lot-Sizing Problems," Management Science, INFORMS, vol. 46(5), pages 724-738, May.
    12. Wu, Tao & Shi, Leyuan & Geunes, Joseph & AkartunalI, Kerem, 2011. "An optimization framework for solving capacitated multi-level lot-sizing problems with backlogging," European Journal of Operational Research, Elsevier, vol. 214(2), pages 428-441, October.
    13. Chen, Haoxun, 2015. "Fix-and-optimize and variable neighborhood search approaches for multi-level capacitated lot sizing problems," Omega, Elsevier, vol. 56(C), pages 25-36.
    14. Drexl, Andreas & Kimms, Alf, 1996. "Lot sizing and scheduling: Survey and extensions," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 421, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    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. Józefowska, J. & Zimniak, A., 2008. "Optimization tool for short-term production planning and scheduling," International Journal of Production Economics, Elsevier, vol. 112(1), pages 109-120, March.
    17. Tao Wu & Zhe Liang & Canrong Zhang, 2018. "Analytics Branching and Selection for the Capacitated Multi-Item Lot Sizing Problem with Nonidentical Machines," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 236-258, May.
    18. Christopher Suerie & Hartmut Stadtler, 2003. "The Capacitated Lot-Sizing Problem with Linked Lot Sizes," Management Science, INFORMS, vol. 49(8), pages 1039-1054, August.
    19. Drexl, Andreas & Haase, Knut, 1995. "Proportional lotsizing and scheduling," International Journal of Production Economics, Elsevier, vol. 40(1), pages 73-87, June.
    20. Fumero, Francesca & Vercellis, Carlo, 1997. "Integrating distribution, machine assignment and lot-sizing via Lagrangean relaxation," International Journal of Production Economics, Elsevier, vol. 49(1), pages 45-54, 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:spr:joheur:v:31:y:2025:i:1:d:10.1007_s10732-024-09539-w. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.