Hexaly, Gurobi, OR-Tools on the Resource-Constrained Project Scheduling Problem (RCPSP)

Benchmark Construction Scheduling

Léa Optimization Scientist August 21, 2024

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.

On large-scale instances of the RCPSP, Hexaly reaches an average gap of 1.9% within 1 minute of running time. This page illustrates how Hexaly outperforms traditional general-purpose optimization solvers on this challenging problem. We compare Hexaly’s performance with Gurobi, a state-of-the-art Mixed Integer Linear Programming (MILP) solver, and the CP-SAT solver of Google OR-Tools 9.10, a state-of-the-art Constraint Programming (CP) solver.

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, each comprising 300 tasks, representing different situations and configurations.

Mathematical models of the Resource-Constrained Project Scheduling Problem (RCPSP)

Mixed Integer Linear Programming (MILP) model

The results reported for Gurobi are obtained by running several MILP models proposed in the literature: Koné et al., Tesch, Rihm and Trautmann, Melo and Queiroz.

Constraint Programming (CP) model

The results reported for OR-Tools are obtained using the RCPSP example provided with the OR-Tools library. The model uses interval decision variables to represent the tasks and cumulative constraints to represent the resources.

Hexaly model

The Hexaly model relies on interval decisions to model the tasks. The cumulative resource constraints can be formulated as follows: for each resource, the amount consumed by the tasks being processed must never exceed the resource’s capacity. To model these constraints, we sum up, for each resource and each instant t, the weights of the tasks that start before t and end after t. To ensure that the constraint is respected at each instant, we use a variadic and operator over the whole time horizon.

function model() {
    // Interval decisions: time range of each task
    tasks[i in 0...nbTasks] <- interval(0, horizon);

    // Task duration constraints
    for [i in 0...nbTasks]
        constraint length(tasks[i]) == duration[i];

    // Precedence constraints between the tasks
    for[i in 0...nbTasks][s in 0...nbSuccessors[i]] {
        constraint tasks[i] < tasks[successors[i][s]];
    }

    // Makespan: end of the last task
    makespan <- max[i in 0...nbTasks] (end(tasks[i]));

    // Cumulative resource constraints
    for [r in 0...nbResources] {
        constraint and(0...makespan,
                t => sum[i in 0...nbTasks](weight[i][r] * contains(tasks[i], t)) <= capacity[r]);
    }

    // Minimize the makespan
    minimize makespan;
}

Hexaly, Gurobi, OR-Tools results on the Resource-Constrained Project Scheduling Problem (RCPSP)

We compare solvers’ solutions obtained within 1 minute of running time. The measure of solutions’ quality is the gap in % to the best solution known in the literature. We use Hexaly 13.0, Gurobi 11.0, and the CP-SAT solver of Google OR-Tools 9.10. All are used with default parameters. We ran them on a server equipped with an AMD Ryzen 7 7700 processor (8 cores, 3.8GHz, 8MB cache) and 32GB RAM.

On average, Hexaly achieves a 1.9% gap, while OR-Tools reaches a 3.3% gap. Whatever the MILP formulation used, Gurobi doesn’t provide any feasible solutions for all instances; this remains the same for a time limit extended to 1 hour.

The table below shows the number of instances where each solver reaches a solution below a particular gap. For example, Hexaly finds a solution with a gap to the best known solution below 5% for 91% of the instances; OR-Tools does so for 66% of the instances.

Conclusion

Hexaly offers a concise and straightforward approach to the Resource-Constrained Project Scheduling Problem (RCPSP) based on interval decision variables. The resulting model provides better solutions than the state-of-the-art Mixed Integer Linear Programming (MILP) solver Gurobi and the state-of-the-art Constraint Programming (CP) solver from OR-Tools on large-scale instances of the RCPSP.

You can find the complete model of the Resource-Constrained Project Scheduling Problem (RCPSP) and many other scheduling problems in Python, Java, C#, and C++ in our Example Tour.

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