IDEAS home Printed from https://ideas.repec.org/p/rug/rugwps/05-294.html
   My bibliography  Save this paper

A Bi-Population Based Genetic Algorithm for the Resource-Constrained Project Scheduling Problem

Author

Listed:
  • D. DEBELS
  • M. VANHOUCKE

Abstract

The resource-constrained project scheduling problem (RCPSP) is one of the most challenging problems in project scheduling. During the last couple of years many heuristic procedures have been developed for this problem, but still these procedures often fail in finding near-optimal solutions for more challenging problem instances. In this paper, we present a new genetic algorithm (GA) that, in contrast of a conventional GA, makes use of two separate populations. This bi-population genetic algorithm (BPGA) operates on both a population of left-justified schedules and a population of right-justified schedules in order to fully exploit the features of the iterative forward/backward local search scheduling technique. Comparative computational results reveal that this procedure can be considered as today’s best performing RCPSP heuristic.

Suggested Citation

  • D. Debels & M. Vanhoucke, 2005. "A Bi-Population Based Genetic Algorithm for the Resource-Constrained Project Scheduling Problem," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/294, Ghent University, Faculty of Economics and Business Administration.
    • Handle: RePEc:rug:rugwps:05/294
    as

    Download full text from publisher

    File URL: http://wps-feb.ugent.be/Papers/wp_05_294.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Hartmann, Sonke & Kolisch, Rainer, 2000. "Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 127(2), pages 394-407, December.
    2. 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.
    3. J. Alcaraz & C. Maroto, 2001. "A Robust Genetic Algorithm for Resource Allocation in Project Scheduling," Annals of Operations Research, Springer, vol. 102(1), pages 83-109, February.
    4. 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).
    5. Valls, Vicente & Quintanilla, Sacramento & Ballestin, Francisco, 2003. "Resource-constrained project scheduling: A critical activity reordering heuristic," European Journal of Operational Research, Elsevier, vol. 149(2), pages 282-301, September.
    6. 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.
    7. Hartmann, Sönke & Kolisch, R., 2000. "Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 11180, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    8. Li, K. Y. & Willis, R. J., 1992. "An iterative scheduling technique for resource-constrained project scheduling," European Journal of Operational Research, Elsevier, vol. 56(3), pages 370-379, February.
    9. 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.
    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. Edgar Gutiérrez Franco & Fernando La Torre Zurita & Gonzalo Mejía Delgadillo, 2007. "A genetic algorithm for the resource constrained project scheduling problem (RCPSP)," Investigación & Desarrollo, Universidad Privada Boliviana, vol. 1(1), pages 41-52.
    2. 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.
    3. 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.
    4. 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.

    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. Kolisch, Rainer & Hartmann, Sonke, 2006. "Experimental investigation of heuristics for resource-constrained project scheduling: An update," European Journal of Operational Research, Elsevier, vol. 174(1), pages 23-37, October.
    2. D. Debels & M. Vanhoucke, 2005. "A Decomposition-Based Heuristic For The Resource-Constrained Project Scheduling Problem," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 05/293, Ghent University, Faculty of Economics and Business Administration.
    3. Dieter Debels & Mario Vanhoucke, 2007. "A Decomposition-Based Genetic Algorithm for the Resource-Constrained Project-Scheduling Problem," Operations Research, INFORMS, vol. 55(3), pages 457-469, June.
    4. 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.
    5. Valls, Vicente & Ballestin, Francisco & Quintanilla, Sacramento, 2008. "A hybrid genetic algorithm for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 185(2), pages 495-508, March.
    6. 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.
    7. 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.
    8. Tseng, Lin-Yu & Chen, Shih-Chieh, 2006. "A hybrid metaheuristic for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 175(2), pages 707-721, December.
    9. Feifei Li & Zhe Xu, 2018. "A multi-agent system for distributed multi-project scheduling with two-stage decomposition," PLOS ONE, Public Library of Science, vol. 13(10), pages 1-24, October.
    10. Moumene, Khaled & Ferland, Jacques A., 2009. "Activity list representation for a generalization of the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 199(1), pages 46-54, November.
    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. 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.
    13. 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.
    14. 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.
    15. 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.
    16. Kolisch, R. & Padman, R., 2001. "An integrated survey of deterministic project scheduling," Omega, Elsevier, vol. 29(3), pages 249-272, June.
    17. Bernardo F. Almeida & Isabel Correia & Francisco Saldanha-da-Gama, 2018. "A biased random-key genetic algorithm for the project scheduling problem with flexible resources," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 26(2), pages 283-308, July.
    18. Debels, D. & Vanhoucke, M., 2006. "Meta-Heuristic resource constrained project scheduling: solution space restrictions and neighbourhood extensions," Vlerick Leuven Gent Management School Working Paper Series 2006-18, Vlerick Leuven Gent Management School.
    19. 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.
    20. 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.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:rug:rugwps:05/294. 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: Nathalie Verhaeghe (email available below). General contact details of provider: https://edirc.repec.org/data/ferugbe.html .

    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.