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

Benchmarks Construction Scheduling

Léa, Ph.D. Senior Optimization Scientist July 23, 2026

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 its successors can start. There is a set of renewable resources. Each task has a resource requirement or weight (possibly zero) for each resource, representing the amount of that resource it consumes during processing. 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 Resource-Constrained Project Scheduling Problem (RCPSP), Hexaly achieves an average gap of 2.0% to the best known solutions in the research community (BKS) within 1 minute of runtime. This page illustrates how Hexaly outperforms traditional general-purpose optimization solvers on this challenging problem. We compare Hexaly’s performance with Gurobi, a Mixed Integer Linear Programming (MILP) solver, and the CP-SAT solver of Google OR-Tools 9.14, a 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 BKS. We use Hexaly 15.0, Gurobi 11.0, and the CP-SAT solver of Google OR-Tools 9.14. All are used with default parameters. We ran them on a server equipped with an AMD Ryzen 7 7700 processor (8 cores, 3.8 GHz, 8 MB cache) and 32 GB of RAM.

On average, Hexaly achieves a 2.0% gap to BKS. Whatever the MILP formulation used, Gurobi doesn’t provide any feasible solutions for all instances; this holds even with a time limit extended to 1 hour.

The table below shows the number of instances in which each solver reaches a solution with a gap below a given threshold. For example, Hexaly finds a solution with a gap to the BKS below 5% for 90% of instances; OR-Tools does so for 66% of instances.

Conclusion

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

Our Code Templates include the Resource-Constrained Project Scheduling Problem (RCPSP) model and many other Scheduling problems written using Hexaly Modeler or programming languages like Python, Java, C#, and C++.

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