RCPSP

Resource-constrained project scheduling

The resource-constrained project scheduling problem (RCPSP) is the basic problem type in project scheduling and aims at the minimization of the total project duration. It is one of the most widely studied project scheduling problem in literature, and it has resulted in an overwhelming amount of papers with solution procedures to solve the problem.

Data instances

In the RCPSP research community, a lot a comparisons have been made, mostly done on the PSPLIB data instances generated by ProGen. However, we have also created a lot of project data in different papers, for which a short summary is given below

  • CV: We have created a set of 623 project instances that cannot be solved with the current state-of-the-art branch-and-bound procedures (Coelho and Vanhoucke (2020)).
  • NetRes: The NetRes data must be generated by the user using the MT dataset (network data) and the ResSet data file (resource data), resulting in almost 4 million instances. The 1kNetRes is a subset of this huge database (Vanhoucke and Coelho (2018)).
  • RG30: This dataset contains a set of projects with 30 activities created to test our second version of our random network generator RanGen2 (Vanhoucke et al. (2008)).
  • RG300: For our paper published in Operations Research, we had to create a new set RG300 with instances with up to 300 activities per projects (Debels and Vanhoucke (2007)).
  • DC1: For our paper published in Management Science, we created a dataset of project instances with 10 to 50 activities (Vanhoucke et al. (2001)) to solve the RCPSP with cash flows (cash flow data not in the dataset).
  • DC2: In Vanhoucke (2010), we created a new dataset to solve the RCPSP with cash flows (cash flow data not in the dataset).
  • MT: The dataset MT was originally constructed to test the algorithms proposed in the book "Measuring Time" (Vanhoucke, 2010) but has been used in many of our project control papers ever since. These projects contain no relevant resource data (only network data).

Solution procedures

OR&S has spent a lot of work on the challenging RCPSP problem in different ways. A short summary is given below:

  • Meta-heuristics (2000 - 2010): OR&S has proposed different meta-heuristic solution procedures for the RCPSP, including genetic algorithms, scatter search and electromagnetism.
  • Satisfiability solutions (2011 - 2019): OR&S has proposed a new meta-heuristic search procedure using a SAT solver to solve the RCPSP with different extensions. Visit this SAT page here.
  • Branch-and-bound procedure (2020): OR&S has programmed all branch-and-bound procedures from the literature, and proposed a new set of difficult instances
  • New! Priority-rules (2020): A new paper on selecting the best possible priority rules to solve large RCPSP instances is proposed using decision trees. The code of this paper can be accessed here

Software

Resource-constrained project scheduling is integrated with Schedule Risk Analysis (SRA) assess the schedule sensitivity and Earned Value Management (EVM) to control projects in our software tool ProTrack that can be used in educational and business settings. Visit the ProTrack website here.

Extensions

Many extensions on the classical RCPCP have been investigated to make the problem formulation more realistic. On this website, three important extensions are discussed:

  • The RCPSP with Discounted Cash flows, abbreviated as the RCPSP-DC that maximizes the net present value of the project
  • The Multi-Mode RCPSP, abbreviated as the MMRCPSP, that assumes that activities have multiple possible durations, each with a different resource requirement
  • The Resource Availability Cost Problem, abbreviated as the RACP, that aims at determining the optimal level of resource availability at a minimal cost.

Education

When you teach a Project Management course, resource-constrained project scheduling is probably on of the topics you discuss. In the book "Project Management with Dynamic Scheduling: Baseline Scheduling, Risk Analysis and Project Control", an overview is given of Project Management, including the RCPSP and its extensions, and possibilities to solve case studies by ProTrack that is freely available to students.

 

Learn more about Dynamic Scheduling: Watch YouTube video here

References

  • Debels, D. and Vanhoucke, M., 2005, “A Bi-population Based Genetic Algorithm for the Resource-Constrained Project Scheduling Problem”, Lecture Notes in Computer Science, 3483, 378-387.
  • Debels, D., De Reyck, B., Leus, R. and Vanhoucke, M., 2006, “A hybrid scatter search/electromagnetism meta-heuristic for project scheduling”, European Journal of Operational Research, 169, 638-653.
  • Debels, D. and Vanhoucke, M., 2006, “The Electromagnetism Meta-heuristic Applied to the Resource-Constrained Project Scheduling Problem”, Lecture Notes in computer Science, 3871, 259-270.
  • Debels, D. and Vanhoucke, M., 2007, “A decomposition-based genetic algorithm for the resource-constrained project scheduling problem”, Operations Research, 55, 457-469.
  • Read the full list of publications here.