IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v358y2026i2d10.1007_s10479-024-05938-1.html

An application of mathematical programming to a real case of the unrelated parallel machine problem

Author

Listed:
  • Guillermo A. Durán

    (Universidad de Buenos Aires, Buenos Aires, Instituto de Cálculo, Facultad de Ciencias Exactas y Naturales
    Universidad de Buenos Aires, Departamento de Matemática, Facultad de Ciencias Exactas y Naturales
    Consejo Nacional de Investigaciones Científicas y Técnicas
    Universidad de Chile, Departamento de Ingeniería Industrial, Facultad de Ciencias Físicas y Matemáticas)

  • Manuel Durán

    (Universidad de Buenos Aires, Departamento de Tecnología Industrial, Facultad de Ingeniería)

  • Nazareno A. Faillace Mullen

    (Universidad de Buenos Aires, Buenos Aires, Instituto de Cálculo, Facultad de Ciencias Exactas y Naturales
    Consejo Nacional de Investigaciones Científicas y Técnicas)

  • Juan Velásquez

    (Universidad de Buenos Aires, Departamento de Tecnología Industrial, Facultad de Ingeniería)

Abstract

Mathematical programming techniques are used in a tool developed to solve a real unrelated parallel machine problem in a bottle closures manufacturing plant. The tool is able to define the production process planning for a scheduling horizon of up to one month while satisfying all relevant constraints. The planning problem is a multi-objective one of minimizing production completion times, overproduction and machine idle time. Due to the problem’s complexity, the approach adopted for obtaining good solutions in reasonable execution times is based on dividing it into three subproblems or stages, each solved by a different MILP model. In the first stage, the model performs a lexicographic minimization to assign closure injection molds to the plant’s machines; in the second stage, the model corrects the machine stoppage times for mold changes; and in the third stage, the model determines the assignment of different colors to the closures or its parts produced with a given mold. Results are presented for instances of up to 100 jobs, showing how different characteristics of the problem influence the performance of the proposed solution approach. A comparison is also presented between our model’s result and the manual scheduling carried out by the factory staff for a real instance, demonstrating that our method enabled significant enhancements in the aforementioned objectives.

Suggested Citation

  • Guillermo A. Durán & Manuel Durán & Nazareno A. Faillace Mullen & Juan Velásquez, 2026. "An application of mathematical programming to a real case of the unrelated parallel machine problem," Annals of Operations Research, Springer, vol. 358(2), pages 815-843, March.
    • Handle: RePEc:spr:annopr:v:358:y:2026:i:2:d:10.1007_s10479-024-05938-1
    DOI: 10.1007/s10479-024-05938-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10479-024-05938-1
    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/s10479-024-05938-1?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

    for a different version of it.

    References listed on IDEAS

    as
    1. Jianzhong Du & Joseph Y.-T. Leung, 1990. "Minimizing Total Tardiness on One Machine is NP-Hard," Mathematics of Operations Research, INFORMS, vol. 15(3), pages 483-495, August.
    2. Wu, Lingxiao & Wang, Shuaian, 2018. "Exact and heuristic methods to solve the parallel machine scheduling problem with multi-processor tasks," International Journal of Production Economics, Elsevier, vol. 201(C), pages 26-40.
    3. Mokotoff, E. & Chretienne, P., 2002. "A cutting plane algorithm for the unrelated parallel machine scheduling problem," European Journal of Operational Research, Elsevier, vol. 141(3), pages 515-525, September.
    4. Fanjul-Peyro, Luis & Perea, Federico & Ruiz, Rubén, 2017. "Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources," European Journal of Operational Research, Elsevier, vol. 260(2), pages 482-493.
    5. Peter Brucker, 2007. "Scheduling Algorithms," Springer Books, Springer, edition 0, number 978-3-540-69516-5, January.
    6. Chunfeng Liu, 2013. "A Hybrid Genetic Algorithm to Minimize Total Tardiness for Unrelated Parallel Machine Scheduling with Precedence Constraints," Mathematical Problems in Engineering, Hindawi, vol. 2013, pages 1-11, July.
    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. Yorie Nakahira & Andres Ferragut & Adam Wierman, 2023. "Generalized Exact Scheduling: A Minimal-Variance Distributed Deadline Scheduler," Operations Research, INFORMS, vol. 71(2), pages 433-470, March.
    2. Bentao Su & Naiming Xie & Yingjie Yang, 2021. "Hybrid genetic algorithm based on bin packing strategy for the unrelated parallel workgroup scheduling problem," Journal of Intelligent Manufacturing, Springer, vol. 32(4), pages 957-969, April.
    3. Yanıkoğlu, İhsan & Yavuz, Tonguc, 2022. "Branch-and-price approach for robust parallel machine scheduling with sequence-dependent setup times," European Journal of Operational Research, Elsevier, vol. 301(3), pages 875-895.
    4. Agnetis, Alessandro & Billaut, Jean-Charles & Pinedo, Michael & Shabtay, Dvir, 2025. "Fifty years of research in scheduling — Theory and applications," European Journal of Operational Research, Elsevier, vol. 327(2), pages 367-393.
    5. Farbod Farhadi & Sina Ansari & Francisco Jara-Moroni, 2023. "Optimization models for patient and technician scheduling in hemodialysis centers," Health Care Management Science, Springer, vol. 26(3), pages 558-582, September.
    6. Prahalad Venkateshan & Joseph Szmerekovsky & George Vairaktarakis, 2020. "A cutting plane approach for the multi-machine precedence-constrained scheduling problem," Annals of Operations Research, Springer, vol. 285(1), pages 247-271, February.
    7. Enrique Gerstl & Gur Mosheiov, 2020. "Single machine scheduling to maximize the number of on-time jobs with generalized due-dates," Journal of Scheduling, Springer, vol. 23(3), pages 289-299, June.
    8. Fleszar, Krzysztof & Hindi, Khalil S., 2018. "Algorithms for the unrelated parallel machine scheduling problem with a resource constraint," European Journal of Operational Research, Elsevier, vol. 271(3), pages 839-848.
    9. Parreño, F. & Alvarez-Valdes, R., 2021. "Mathematical models for a cutting problem in the glass manufacturing industry," Omega, Elsevier, vol. 103(C).
    10. Derya Deliktaş, 2022. "Self-adaptive memetic algorithms for multi-objective single machine learning-effect scheduling problems with release times," Flexible Services and Manufacturing Journal, Springer, vol. 34(3), pages 748-784, September.
    11. Baruch Mor & Gur Mosheiov & Dvir Shabtay, 2021. "Minimizing the total tardiness and job rejection cost in a proportionate flow shop with generalized due dates," Journal of Scheduling, Springer, vol. 24(6), pages 553-567, December.
    12. Camila Ramos & Alejandro Cataldo & Juan–Carlos Ferrer, 2020. "Appointment and patient scheduling in chemotherapy: a case study in Chilean hospitals," Annals of Operations Research, Springer, vol. 286(1), pages 411-439, March.
    13. Quang Chieu Ta & Jean-Charles Billaut & Jean-Louis Bouquard, 2018. "Matheuristic algorithms for minimizing total tardiness in the m-machine flow-shop scheduling problem," Journal of Intelligent Manufacturing, Springer, vol. 29(3), pages 617-628, March.
    14. Gerardo Minella & Rubén Ruiz & Michele Ciavotta, 2008. "A Review and Evaluation of Multiobjective Algorithms for the Flowshop Scheduling Problem," INFORMS Journal on Computing, INFORMS, vol. 20(3), pages 451-471, August.
    15. Vincent T’kindt & Federico Della Croce & Mathieu Liedloff, 2022. "Moderate exponential-time algorithms for scheduling problems," 4OR, Springer, vol. 20(4), pages 533-566, December.
    16. Hesham K. Alfares, 2022. "Plant shutdown maintenance workforce team assignment and job scheduling," Journal of Scheduling, Springer, vol. 25(3), pages 321-338, June.
    17. C N Potts & V A Strusevich, 2009. "Fifty years of scheduling: a survey of milestones," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 41-68, May.
    18. Ali Kordmostafapour & Javad Rezaeian & Iraj Mahdavi & Mahdi Yar Farjad, 2022. "Scheduling unrelated parallel machine problem with multi-mode processing times and batch delivery cost," OPSEARCH, Springer;Operational Research Society of India, vol. 59(4), pages 1438-1470, December.
    19. Peter Bodnar & René de Koster & Kaveh Azadeh, 2017. "Scheduling Trucks in a Cross-Dock with Mixed Service Mode Dock Doors," Transportation Science, INFORMS, vol. 51(1), pages 112-131, February.
    20. Elham Ziar & Mehdi Seifbarghy & Mahdi Bashiri & Benny Tjahjono, 2023. "An efficient environmentally friendly transportation network design via dry ports: a bi-level programming approach," Annals of Operations Research, Springer, vol. 322(2), pages 1143-1166, March.

    More about this item

    Keywords

    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:annopr:v:358:y:2026:i:2:d:10.1007_s10479-024-05938-1. 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.