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

A hybrid rank-based evolutionary algorithm applied to multi-mode resource-constrained project scheduling problem

Author

Listed:
  • Elloumi, Sonda
  • Fortemps, Philippe

Abstract

We consider the multi-mode resource-constrained project scheduling problem (MRCPSP), where a task has different execution modes characterized by different resource requirements. Due to the nonrenewable resources and the multiple modes, this problem is NP-hard; therefore, we implement an evolutionary algorithm looking for a feasible solution minimizing the makespan. In this paper, we propose and investigate two new ideas. On the one hand, we transform the problem of single objective MRCPSP to bi-objective one to cope with the potential violation of nonrenewable resource constraints. Relaxing the latter constraints allows to visit a larger solution set and thus to simplify the evolutionary operators. On the other hand, we build the fitness function not on a priori grid of the bi-objective space, but on an adaptive one relying on clustering techniques. This proposed idea aims at more relevant fitness values. We show that a clustering-based fitness function can be an appealing feature in multi-objective evolutionary algorithms since it may promote diversity and avoid premature convergence of the algorithms. Clustering heuristics require certainly computation time, but they are still competitive with respect to classical niche formation multi-objective genetic algorithm.

Suggested Citation

  • 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.
  • Handle: RePEc:eee:ejores:v:205:y:2010:i:1:p:31-41
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(09)00942-4
    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. Slowinski, Roman & Soniewicki, Boleslaw & Weglarz, Jan, 1994. "DSS for multiobjective project scheduling," European Journal of Operational Research, Elsevier, vol. 79(2), pages 220-229, December.
    2. Patterson, James H. & Brian Talbot, F. & Slowinski, Roman & Weglarz, Jan, 1990. "Computational experience with a backtracking algorithm for solving a general class of precedence and resource-constrained scheduling problems," European Journal of Operational Research, Elsevier, vol. 49(1), pages 68-79, November.
    3. 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.
    4. Kolisch, Rainer, 1996. "Serial and parallel resource-constrained project scheduling methods revisited: Theory and computation," European Journal of Operational Research, Elsevier, vol. 90(2), pages 320-333, April.
    5. Sönke Hartmann, 2001. "Project Scheduling with Multiple Modes: A Genetic Algorithm," Annals of Operations Research, Springer, vol. 102(1), pages 111-135, February.
    6. Boctor, Fayez F., 1996. "A new and efficient heuristic for scheduling projects with resource restrictions and multiple execution modes," European Journal of Operational Research, Elsevier, vol. 90(2), pages 349-361, April.
    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. Valls, Vicente & Ballestin, Francisco & Quintanilla, Sacramento, 2005. "Justification and RCPSP: A technique that pays," European Journal of Operational Research, Elsevier, vol. 165(2), pages 375-386, September.
    10. 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.
    11. 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.
    12. Debels, Dieter & De Reyck, Bert & Leus, Roel & Vanhoucke, Mario, 2006. "A hybrid scatter search/electromagnetism meta-heuristic for project scheduling," European Journal of Operational Research, Elsevier, vol. 169(2), pages 638-653, March.
    13. De Reyck, Bert & Herroelen, Willy, 1999. "The multi-mode resource-constrained project scheduling problem with generalized precedence relations," European Journal of Operational Research, Elsevier, vol. 119(2), pages 538-556, December.
    14. Bianco, L. & Dell'Olmo, P. & Grazia Speranza, M., 1998. "Heuristics for multimode scheduling problems with dedicated resources," European Journal of Operational Research, Elsevier, vol. 107(2), pages 260-271, June.
    15. 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.
    16. Sprecher, Arno & Drexl, Andreas, 1998. "Multi-mode resource-constrained project scheduling by a simple, general and powerful sequencing algorithm," European Journal of Operational Research, Elsevier, vol. 107(2), pages 431-450, June.
    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. 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.
    2. Karen Puttkammer & Rainer Kleber & Tobias Schulz & Karl Inderfurth, 2011. "Simultane Maschinenbelegungs- und Personaleinsatzplanung in KMUs anhand eines Fallbeispiels aus der Druckereibranche," FEMM Working Papers 110010, Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
    3. Xue Li & Zhengwen He & Nengmin Wang & Mario Vanhoucke, 2022. "Multimode time-cost-robustness trade-off project scheduling problem under uncertainty," Journal of Combinatorial Optimization, Springer, vol. 43(5), pages 1173-1202, July.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. Ramírez Palencia, Alberto E. & Mejía Delgadillo, Gonzalo E., 2012. "A computer application for a bus body assembly line using Genetic Algorithms," International Journal of Production Economics, Elsevier, vol. 140(1), pages 431-438.
    9. 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.
    10. Siqing Shan & Zhongjun Hu & Zhilian Liu & Jihong Shi & Li Wang & Zhuming Bi, 2017. "An adaptive genetic algorithm for demand-driven and resource-constrained project scheduling in aircraft assembly," Information Technology and Management, Springer, vol. 18(1), pages 41-53, March.

    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. 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.
    2. 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.
    3. V. Van Peteghem & M. Vanhoucke, 2008. "A Genetic Algorithm for the Multi-Mode Resource-Constrained Project Scheduling Problem," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 08/494, Ghent University, Faculty of Economics and Business Administration.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    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. 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.
    10. 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.
    11. Abdollah Arasteh, 2020. "Considering Project Management Activities for Engineering Design Groups," SN Operations Research Forum, Springer, vol. 1(4), pages 1-29, December.
    12. 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.
    13. Kolisch, R. & Padman, R., 2001. "An integrated survey of deterministic project scheduling," Omega, Elsevier, vol. 29(3), pages 249-272, June.
    14. 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.
    15. Hartmann, Sönke & Briskorn, Dirk, 2008. "A survey of variants and extensions of the resource-constrained project scheduling problem," Working Paper Series 02/2008, Hamburg School of Business Administration (HSBA).
    16. 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.
    17. Chen, Jiaqiong & Askin, Ronald G., 2009. "Project selection, scheduling and resource allocation with time dependent returns," European Journal of Operational Research, Elsevier, vol. 193(1), pages 23-34, February.
    18. Kadri, Roubila Lilia & Boctor, Fayez F., 2018. "An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times: The single mode case," European Journal of Operational Research, Elsevier, vol. 265(2), pages 454-462.
    19. Dayal Madhukar & Verma, Sanjay, 2015. "Multi-processor Exact Procedures for Regular Measures of the Multi-mode RCPSP," IIMA Working Papers WP2015-03-25, Indian Institute of Management Ahmedabad, Research and Publication Department.
    20. V. Van Peteghem & M. Vanhoucke, 2009. "Using Resource Scarceness Characteristics to Solve the Multi-Mode Resource-Constrained Project Scheduling Problem," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 09/595, Ghent University, Faculty of Economics and Business Administration.

    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:205:y:2010:i:1:p:31-41. 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.