IDEAS home Printed from https://ideas.repec.org/a/spr/jsched/v24y2021i4d10.1007_s10951-021-00696-5.html
   My bibliography  Save this article

A memetic algorithm to address the multi-node resource-constrained project scheduling problem

Author

Listed:
  • Luis F. Machado-Domínguez

    (Universidad del Norte)

  • Carlos D. Paternina-Arboleda

    (Universidad del Norte)

  • Jorge I. Vélez

    (Universidad del Norte)

  • Agustin Barrios-Sarmiento

    (Universidad del Norte)

Abstract

The multi-mode resource-constrained project scheduling problem (MRCPSP) is a very general scheduling model. The MRCPSP covers problems where activities can be executed in several ways or modes, and is affected by parameters such as their duration, temporary relationships with other activities, and renewable and non-renewable resource requirements. The objective of the MRCPSP is to select a combination of time/resources to minimize the duration of the project and complete all activities while satisfying all resource constraints and precedence relationships. Here, we describe a memetic algorithm to solve the MRCPSP. This algorithm uses the components of genetic algorithms and variable neighborhoods search to implement (1) an adaptation of the uniform crossover operator, and (2) a local search to assess agents’ performance that appropriately guides the evolution of the algorithm and hence generate better solutions. We implement a metaheuristic strategy and compare its performance for solving different instances of the standard PSPLIB and MMLIB libraries. Overall, our memetic algorithm provides suitable solutions for the MRCPSP and shows outstanding performance in all tested instances.

Suggested Citation

  • Luis F. Machado-Domínguez & Carlos D. Paternina-Arboleda & Jorge I. Vélez & Agustin Barrios-Sarmiento, 2021. "A memetic algorithm to address the multi-node resource-constrained project scheduling problem," Journal of Scheduling, Springer, vol. 24(4), pages 413-429, August.
    • Handle: RePEc:spr:jsched:v:24:y:2021:i:4:d:10.1007_s10951-021-00696-5
    DOI: 10.1007/s10951-021-00696-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10951-021-00696-5
    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/s10951-021-00696-5?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. A. Alan B. Pritsker & Lawrence J. Waiters & Philip M. Wolfe, 1969. "Multiproject Scheduling with Limited Resources: A Zero-One Programming Approach," Management Science, INFORMS, vol. 16(1), pages 93-108, September.
    2. Lova, Antonio & Tormos, Pilar & Cervantes, Mariamar & Barber, Federico, 2009. "An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes," International Journal of Production Economics, Elsevier, vol. 117(2), pages 302-316, February.
    3. Sönke Hartmann, 2001. "Project Scheduling with Multiple Modes: A Genetic Algorithm," Annals of Operations Research, Springer, vol. 102(1), pages 111-135, February.
    4. Geiger, Martin Josef, 2017. "A multi-threaded local search algorithm and computer implementation for the multi-mode, resource-constrained multi-project scheduling problem," European Journal of Operational Research, Elsevier, vol. 256(3), pages 729-741.
    5. Christofides, Nicos & Alvarez-Valdes, R. & Tamarit, J. M., 1987. "Project scheduling with resource constraints: A branch and bound approach," European Journal of Operational Research, Elsevier, vol. 29(3), pages 262-273, June.
    6. Van Peteghem, Vincent & Vanhoucke, Mario, 2014. "An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances," European Journal of Operational Research, Elsevier, vol. 235(1), pages 62-72.
    7. F. Brian Talbot, 1982. "Resource-Constrained Project Scheduling with Time-Resource Tradeoffs: The Nonpreemptive Case," Management Science, INFORMS, vol. 28(10), pages 1197-1210, October.
    8. Joanna Józefowska & Marek Mika & Rafał Różycki & Grzegorz Waligóra & Jan Węglarz, 2001. "Simulated Annealing for Multi-Mode Resource-Constrained Project Scheduling," Annals of Operations Research, Springer, vol. 102(1), pages 137-155, February.
    9. Coelho, José & Vanhoucke, Mario, 2011. "Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers," European Journal of Operational Research, Elsevier, vol. 213(1), pages 73-82, August.
    10. Bouleimen, K. & Lecocq, H., 2003. "A new efficient simulated annealing algorithm for the resource-constrained project scheduling problem and its multiple mode version," European Journal of Operational Research, Elsevier, vol. 149(2), pages 268-281, September.
    11. V. Van Peteghem & M. Vanhoucke, 2009. "An Artificial Immune System for the Multi-Mode Resource-Constrained Project Scheduling Problem," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 09/555, Ghent University, Faculty of Economics and Business Administration.
    12. Olaguibel, Ramon Alvarez-Valdes & Goerlich, JoseManuel Tamarit, 1993. "The project scheduling polyhedron: Dimension, facets and lifting theorems," European Journal of Operational Research, Elsevier, vol. 67(2), pages 204-220, June.
    13. J Alcaraz & C Maroto & R Ruiz, 2003. "Solving the Multi-Mode Resource-Constrained Project Scheduling Problem with genetic algorithms," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(6), pages 614-626, June.
    14. M H Sebt & Y Alipouri & Y Alipouri, 2013. "Solving resource-constrained project scheduling problem with evolutionary programming," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(9), pages 1327-1335, September.
    15. Aristide Mingozzi & Vittorio Maniezzo & Salvatore Ricciardelli & Lucio Bianco, 1998. "An Exact Algorithm for the Resource-Constrained Project Scheduling Problem Based on a New Mathematical Formulation," Management Science, INFORMS, vol. 44(5), pages 714-729, May.
    16. Ranjbar, Mohammad & De Reyck, Bert & Kianfar, Fereydoon, 2009. "A hybrid scatter search for the discrete time/resource trade-off problem in project scheduling," European Journal of Operational Research, Elsevier, vol. 193(1), pages 35-48, February.
    17. Kolisch, Rainer & Sprecher, Arno, 1996. "PSPLIB - a project scheduling problem library," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 396, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    18. Peteghem, Vincent Van & Vanhoucke, Mario, 2010. "A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 201(2), pages 409-418, March.
    19. Elloumi, Sonda & Fortemps, Philippe, 2010. "A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 205(1), pages 31-41, August.
    20. Kolisch, Rainer & Hartmann, Sönke, 1999. "Heuristic algorithms for the resource-constrained project scheduling problem: classification and computational analysis," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 10966, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    21. De Reyck, Bert & Herroelen, willy, 1998. "A branch-and-bound procedure for the resource-constrained project scheduling problem with generalized precedence relations," European Journal of Operational Research, Elsevier, vol. 111(1), pages 152-174, November.
    22. Pilar Tormos & Antonio Lova, 2001. "A Competitive Heuristic Solution Technique for Resource-Constrained Project Scheduling," Annals of Operations Research, Springer, vol. 102(1), pages 65-81, February.
    23. Weglarz, Jan & Józefowska, Joanna & Mika, Marek & Waligóra, Grzegorz, 2011. "Project scheduling with finite or infinite number of activity processing modes - A survey," European Journal of Operational Research, Elsevier, vol. 208(3), pages 177-205, February.
    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. Shadi Sadri & S. M. T. Fatemi Ghomi & Amin Dehghanian, 2024. "Analysis of a time–cost trade-off in a resource-constrained GERT project scheduling problem using the Markov decision process," Annals of Operations Research, Springer, vol. 338(1), pages 535-568, July.
    2. Raúl Mencía & Carlos Mencía, 2021. "One-Machine Scheduling with Time-Dependent Capacity via Efficient Memetic Algorithms," Mathematics, MDPI, vol. 9(23), pages 1-24, November.
    3. Maryam Sadeghloo & Saeed Emami & Ali Divsalar, 2024. "A Benders decomposition algorithm for the multi-mode resource-constrained multi-project scheduling problem with uncertainty," Annals of Operations Research, Springer, vol. 339(3), pages 1637-1677, August.

    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. Alireza Etminaniesfahani & Hanyu Gu & Leila Moslemi Naeni & Amir Salehipour, 2024. "An efficient relax-and-solve method for the multi-mode resource constrained project scheduling problem," Annals of Operations Research, Springer, vol. 338(1), pages 41-68, July.
    2. Van Peteghem, Vincent & Vanhoucke, Mario, 2014. "An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances," European Journal of Operational Research, Elsevier, vol. 235(1), pages 62-72.
    3. Weglarz, Jan & Józefowska, Joanna & Mika, Marek & Waligóra, Grzegorz, 2011. "Project scheduling with finite or infinite number of activity processing modes - A survey," European Journal of Operational Research, Elsevier, vol. 208(3), pages 177-205, February.
    4. Nima Zoraghi & Aria Shahsavar & Babak Abbasi & Vincent Peteghem, 2017. "Multi-mode resource-constrained project scheduling problem with material ordering under bonus–penalty policies," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 25(1), pages 49-79, April.
    5. Alfredo S. Ramos & Pablo A. Miranda-Gonzalez & Samuel Nucamendi-Guillén & Elias Olivares-Benitez, 2023. "A Formulation for the Stochastic Multi-Mode Resource-Constrained Project Scheduling Problem Solved with a Multi-Start Iterated Local Search Metaheuristic," Mathematics, MDPI, vol. 11(2), pages 1-25, January.
    6. Geiger, Martin Josef, 2017. "A multi-threaded local search algorithm and computer implementation for the multi-mode, resource-constrained multi-project scheduling problem," European Journal of Operational Research, Elsevier, vol. 256(3), pages 729-741.
    7. Abdollah Arasteh, 2020. "Considering Project Management Activities for Engineering Design Groups," SN Operations Research Forum, Springer, vol. 1(4), pages 1-29, December.
    8. T Wauters & K Verbeeck & G Vanden Berghe & P De Causmaecker, 2011. "Learning agents for the multi-mode project scheduling problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(2), pages 281-290, February.
    9. Peteghem, Vincent Van & Vanhoucke, Mario, 2010. "A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 201(2), pages 409-418, March.
    10. Kellenbrink, Carolin & Helber, Stefan, 2015. "Scheduling resource-constrained projects with a flexible project structure," European Journal of Operational Research, Elsevier, vol. 246(2), pages 379-391.
    11. Luis F. Machado-Domínguez & Carlos D. Paternina-Arboleda & Jorge I. Vélez & Agustín Barrios-Sarmiento, 2022. "An adaptative bacterial foraging optimization algorithm for solving the MRCPSP with discounted cash flows," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(2), pages 221-248, July.
    12. Hartmann, Sönke & Briskorn, Dirk, 2022. "An updated survey of variants and extensions of the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 297(1), pages 1-14.
    13. Coelho, José & Vanhoucke, Mario, 2011. "Multi-mode resource-constrained project scheduling using RCPSP and SAT solvers," European Journal of Operational Research, Elsevier, vol. 213(1), pages 73-82, August.
    14. Hartmann, Sönke & Briskorn, Dirk, 2010. "A survey of variants and extensions of the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 207(1), pages 1-14, November.
    15. Elloumi, Sonda & Fortemps, Philippe, 2010. "A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 205(1), pages 31-41, August.
    16. He, Naihui & Zhang, David Z. & Yuce, Baris, 2022. "Integrated multi-project planning and scheduling - a multiagent approach," European Journal of Operational Research, Elsevier, vol. 302(2), pages 688-699.
    17. Felix Hübner & Patrick Gerhards & Christian Stürck & Rebekka Volk, 2021. "Solving the nuclear dismantling project scheduling problem by combining mixed-integer and constraint programming techniques and metaheuristics," Journal of Scheduling, Springer, vol. 24(3), pages 269-290, June.
    18. Kolisch, R. & Padman, R., 2001. "An integrated survey of deterministic project scheduling," Omega, Elsevier, vol. 29(3), pages 249-272, June.
    19. Alexander Tesch, 2020. "A polyhedral study of event-based models for the resource-constrained project scheduling problem," Journal of Scheduling, Springer, vol. 23(2), pages 233-251, April.
    20. Maryam Sadeghloo & Saeed Emami & Ali Divsalar, 2024. "A Benders decomposition algorithm for the multi-mode resource-constrained multi-project scheduling problem with uncertainty," Annals of Operations Research, Springer, vol. 339(3), pages 1637-1677, 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:spr:jsched:v:24:y:2021:i:4:d:10.1007_s10951-021-00696-5. 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.