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

A Decomposition-Based Heuristic For The Resource-Constrained Project Scheduling Problem

Author

Listed:
  • D. DEBELS
  • M. VANHOUCKE

Abstract

In the last few decades the resource-constrained project scheduling problem has become a popular problem type in operations research. However, due to its strongly NP-hard status, the effectiveness of exact optimisation procedures is restricted to relatively small instances. In this paper we present a new genetic algorithm (GA) for this problem, able to provide near-optimal heuristic solutions. This GA procedure has been extended by a so-called decomposition-based heuristic (DBH) which iteratively solves subparts of the project. We present computational experiments on two datasets. The first benchmark set is used to illustrate the contribution of both the GA and the DBH. The second set is used to compare the results with current state-of-the-art heuristics, and to show that the procedure is capable of producing consistently good results for challenging instances of the resource-constrained project scheduling problem. We illustrate that GA is currently the best performing RCPSP meta-heuristic, and that the DBH further improves the performance of the GA

Suggested Citation

  • 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.
    • Handle: RePEc:rug:rugwps:05/293
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Mireille Palpant & Christian Artigues & Philippe Michelon, 2004. "LSSPER: Solving the Resource-Constrained Project Scheduling Problem with Large Neighbourhood Search," Annals of Operations Research, Springer, vol. 131(1), pages 237-257, October.
    2. Erik L. Demeulemeester & Willy S. Herroelen, 1997. "New Benchmark Results for the Resource-Constrained Project Scheduling Problem," Management Science, INFORMS, vol. 43(11), pages 1485-1492, November.
    3. 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.
    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. Kolisch, R. & Padman, R., 2001. "An integrated survey of deterministic project scheduling," Omega, Elsevier, vol. 29(3), pages 249-272, June.
    6. 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.
    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. Brucker, Peter & Drexl, Andreas & Mohring, Rolf & Neumann, Klaus & Pesch, Erwin, 1999. "Resource-constrained project scheduling: Notation, classification, models, and methods," European Journal of Operational Research, Elsevier, vol. 112(1), pages 3-41, January.
    10. Arno Sprecher, 2000. "Scheduling Resource-Constrained Projects Competitively at Modest Memory Requirements," Management Science, INFORMS, vol. 46(5), pages 710-723, May.
    11. Erik Demeulemeester & Willy Herroelen, 1992. "A Branch-and-Bound Procedure for the Multiple Resource-Constrained Project Scheduling Problem," Management Science, INFORMS, vol. 38(12), pages 1803-1818, December.
    12. 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.
    13. 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.
    14. Brucker, Peter & Knust, Sigrid & Schoo, Arno & Thiele, Olaf, 1998. "A branch and bound algorithm for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 107(2), pages 272-288, June.
    15. 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).
    16. Fleszar, Krzysztof & Hindi, Khalil S., 2004. "Solving the resource-constrained project scheduling problem by a variable neighbourhood search," European Journal of Operational Research, Elsevier, vol. 155(2), pages 402-413, June.
    17. 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.
    18. Kolisch, Rainer & Sprecher, Arno, 1997. "PSPLIB - A project scheduling problem library : OR Software - ORSEP Operations Research Software Exchange Program," European Journal of Operational Research, Elsevier, vol. 96(1), pages 205-216, January.
    19. 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.
    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. Vanhoucke, Mario & Coelho, José, 2016. "An approach using SAT solvers for the RCPSP with logical constraints," European Journal of Operational Research, Elsevier, vol. 249(2), pages 577-591.
    2. Zamani, Reza, 2013. "A competitive magnet-based genetic algorithm for solving the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 229(2), pages 552-559.
    3. 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 0307, Universidad Privada Boliviana, revised Mar 2007.
    4. 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.
    5. Gonzalo Muñoz & Daniel Espinoza & Marcos Goycoolea & Eduardo Moreno & Maurice Queyranne & Orlando Rivera Letelier, 2018. "A study of the Bienstock–Zuckerberg algorithm: applications in mining and resource constrained project scheduling," Computational Optimization and Applications, Springer, vol. 69(2), pages 501-534, March.
    6. 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.
    7. M. Vanhoucke, 2007. "A genetic algorithm to investigate the trade-off between project lead time and net present value," Working Papers of Faculty of Economics and Business Administration, Ghent University, Belgium 07/456, Ghent University, Faculty of Economics and Business Administration.
    8. Horbach, Andrei, 2009. "A boolean satisfiability approach to the resource-constrained project scheduling problem," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 644, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    9. Deblaere, Filip & Demeulemeester, Erik & Herroelen, Willy, 2011. "Proactive policies for the stochastic resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 214(2), pages 308-316, October.
    10. Lei Lei & Michael Pinedo & Lian Qi & Shengbin Wang & Jian Yang, 2015. "Personnel scheduling and supplies provisioning in emergency relief operations," Annals of Operations Research, Springer, vol. 235(1), pages 487-515, December.
    11. 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.
    12. Nadia Chaudry & Ingunn Vermedal & Kjetil Fagerholt & Maria Fleischer Fauske & Magnus Stålhane, 2020. "A decomposition solution approach to the troops-to-tasks assignment in military peacekeeping operations," The Journal of Defense Modeling and Simulation, , vol. 17(4), pages 357-371, October.
    13. Jiang, Yuanchun & Liu, Yezheng & Shang, Jennifer & Yildirim, Pinar & Zhang, Qingfu, 2018. "Optimizing online recurring promotions for dual-channel retailers: Segmented markets with multiple objectives," European Journal of Operational Research, Elsevier, vol. 267(2), pages 612-627.
    14. 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.
    15. Xichao Su & Wei Han & Yu Wu & Yong Zhang & Jie Liu, 2018. "A Proactive Robust Scheduling Method for Aircraft Carrier Flight Deck Operations with Stochastic Durations," Complexity, Hindawi, vol. 2018, pages 1-38, November.
    16. Jürgen Kuster & Dietmar Jannach & Gerhard Friedrich, 2010. "Applying Local Rescheduling in response to schedule disruptions," Annals of Operations Research, Springer, vol. 180(1), pages 265-282, November.
    17. Hongbo Li & Erik Demeulemeester, 2016. "A genetic algorithm for the robust resource leveling problem," Journal of Scheduling, Springer, vol. 19(1), pages 43-60, February.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    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. Kolisch, R. & Padman, R., 2001. "An integrated survey of deterministic project scheduling," Omega, Elsevier, vol. 29(3), pages 249-272, June.
    7. 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.
    8. 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.
    9. Abdollah Arasteh, 2020. "Considering Project Management Activities for Engineering Design Groups," SN Operations Research Forum, Springer, vol. 1(4), pages 1-29, December.
    10. 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.
    11. Debels, Dieter & Vanhoucke, Mario, 2005. "A Bi-Population Based Genetic Algorithm for the Resource-Constrained Project Scheduling Problem," Vlerick Leuven Gent Management School Working Paper Series 2005-8, Vlerick Leuven Gent Management School.
    12. Guo, Weikang & Vanhoucke, Mario & Coelho, José, 2023. "A prediction model for ranking branch-and-bound procedures for the resource-constrained project scheduling problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 579-595.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    17. 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.
    18. 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.
    19. Amadeu A. Coco & Christophe Duhamel & Andréa Cynthia Santos, 2020. "Modeling and solving the multi-period disruptions scheduling problem on urban networks," Annals of Operations Research, Springer, vol. 285(1), pages 427-443, February.
    20. 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.

    More about this item

    Keywords

    project scheduling; genetic algorithms; decomposition;
    All these keywords.

    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/293. 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.