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. 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.
    5. 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.
    6. Peter Brucker, 2007. "Scheduling Algorithms," Springer Books, Springer, edition 0, number 978-3-540-69516-5, March.
    7. Cheng, T. C. E. & Sin, C. C. S., 1990. "A state-of-the-art review of parallel-machine scheduling research," European Journal of Operational Research, Elsevier, vol. 47(3), pages 271-292, August.
    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. 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.
    2. 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.
    3. Hesham K. Alfares, 2022. "Plant shutdown maintenance workforce team assignment and job scheduling," Journal of Scheduling, Springer, vol. 25(3), pages 321-338, June.
    4. 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.
    5. 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.
    6. 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.
    7. Fanjul-Peyro, Luis & Ruiz, Rubén, 2010. "Iterated greedy local search methods for unrelated parallel machine scheduling," European Journal of Operational Research, Elsevier, vol. 207(1), pages 55-69, November.
    8. 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.
    9. 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.
    10. 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.
    11. Yalaoui, F. & Chu, C., 2006. "New exact method to solve the Pm/rj/[summation operator]Cj schedule problem," International Journal of Production Economics, Elsevier, vol. 100(1), pages 168-179, March.
    12. Parreño, F. & Alvarez-Valdes, R., 2021. "Mathematical models for a cutting problem in the glass manufacturing industry," Omega, Elsevier, vol. 103(C).
    13. Lin, Hung-Tso & Liao, Ching-Jong, 2003. "A case study in a two-stage hybrid flow shop with setup time and dedicated machines," International Journal of Production Economics, Elsevier, vol. 86(2), pages 133-143, November.
    14. Biber Nurit & Mor Baruch & Schlissel Yitzhak & Shapira Dana, 2023. "Lot scheduling involving completion time problems on identical parallel machines," Operational Research, Springer, vol. 23(1), pages 1-29, March.
    15. Zoltán Varga & Pál Simon, 2014. "Examination Of Scheduling Methods For Production Systems," Advanced Logistic systems, University of Miskolc, Department of Material Handling and Logistics, vol. 8(1), pages 111-120, December.
    16. Pei, Shunshun & Zhai, Changhai & Hu, Jie, 2024. "Surrogate model-assisted seismic resilience assessment of the interdependent transportation and healthcare system considering a two-stage recovery strategy," Reliability Engineering and System Safety, Elsevier, vol. 244(C).
    17. 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.
    18. 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.
    19. George L. Vairaktarakis, 2003. "The Value of Resource Flexibility in the Resource-Constrained Job Assignment Problem," Management Science, INFORMS, vol. 49(6), pages 718-732, June.
    20. 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.

    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.