Broken records for the Resource-Constrained Project Scheduling Problem (RCPSP)

Benchmark Project Scheduling

Léa Optimization Scientist October 30, 2023

In the Resource-Constrained Project Scheduling Problem (RCPSP), a project consists of a set of tasks that have to be scheduled. Each task has a given duration and cannot be interrupted. There are precedence constraints between the tasks: each task must end before any of its successors can start. There are a set of renewable resources. Each task has a given resource requirement or weight (possibly zero) on each resource, representing the amount of resource it consumes while it is being processed. Each resource has a given maximum capacity: it can process several tasks at once, but the sum of the processed tasks’ weights can never exceed this maximum capacity. The goal is to find a schedule that minimizes the makespan: the time when all tasks have been processed.

This page illustrates how LocalSolver improves the literature’s best known lower bounds on more than a quarter of the instances from a large RCPSP benchmark. For more information on upper bounds, the results of our benchmark against CP-SAT solver Google OR-Tools 9.5 are also available on our RCPSP benchmark page.

Input data

This benchmark focuses on large-scale instances of the Resource-Constrained Project Scheduling Problem (RCPSP). We use the RG300 instances introduced by Debels and Vanhoucke in [1]. There are 480 instances comprising 300 tasks each, representing different situations and configurations.

Fast Bounds for Scheduling Problems in LocalSolver

LocalSolver is built upon various primal and dual techniques to find quality solutions and lower bounds in short running times. Here, we focus on a series of fast algorithms enabling LocalSolver to compute good-quality lower bounds for scheduling problems minimizing the makespan. These lower bounds are computed using energetic relaxations and rely on the techniques described in [2].

Energy Precedence propagation. We ensure that for every subset P of the task x predecessors, the resource has enough energy to schedule all of P between P earliest start time and x earliest start time. If not, we increase x earliest start time.

Linear energetic relaxation. We solve linear relaxations of the problem, in which the decision variables are the tasks’ presences. The start times and durations of the tasks are fixed to their lower bounds.

Reformulation of almost-disjunctive cumulatives. When three tasks have weights whose sum is higher than the cumulative resource’s capacity, these three tasks cannot be executed together on this resource. We then add a redundant cumulative constraint with capacity 2 on these three tasks. This reformulation is combined both with the Energy Precedence propagation and the linear energetic relaxations.

Broken records for the Resource-Constrained Project Scheduling Problem (RCPSP)

We consider the lower bound provided by LocalSolver 12.0 after 1 minute of running time. To obtain these results, we ran the solver on a computer equipped with an Intel i7-12700H (14 cores, 2.3 GHz, 20 threads) and 32GB RAM. The model we used for the Resource-Constrained Project Scheduling Problem (RCPSP) relies on interval variables to represent the tasks. It is available on our Example Tour page.

Thanks to the energetic relaxation algorithms mentioned above, LocalSolver improves the best known lower bounds on 25% of the instances from the RG300 benchmark (121 instances over 480), with an average improvement of 6%. These new lower bounds are now available on the official solutions update page of the RG300 benchmark. In the table below, we present the best improvements given by LocalSolver compared to the literature.

The complete list of improvements can be found in the following data file: RG300_LB.csv

Are you interested in trying out LocalSolver? Get free trial licenses here. In the meantime, feel free to contact us; we will be glad to talk about your optimization problems.

[1] D. Debels, M. Vanhoucke (2007). A Decomposition-Based Genetic Algorithm for the Resource-Constrained Project-Scheduling Problem. Operations Research 55(3), pp. 457-469.

[2] P. Laborie (2023). Fast Bounds for Scheduling Problems in LocalSolver. ROADEF 2023.