Hexaly vs Google OR-Tools on the Resource-Constrained Project Scheduling Problem (RCPSP)

Benchmark Project Scheduling

Léa Optimization Scientist March 27, 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.

Hexaly Optimizer reaches an average gap of 2.6% within 60 seconds of running time on large instances of the RCPSP. This page illustrates how Hexaly Optimizer outperforms traditional general-purpose optimization solvers on this challenging problem. Since MIP solvers like Gurobi struggle to reach feasibility on this problem, we compare Hexaly’s performance with the CP-SAT solver of Google OR-Tools 9.5, known as 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 comprising 300 tasks each, representing different situations and configurations.

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

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;
}

Google OR-Tools and Hexaly results on the Resource-Constrained Project Scheduling Problem (RCPSP)

We compare both solvers’ performance in 1 minute of running time, after which we measure the gap to the best known solution in %. We use Hexaly 12.0 and the CP-SAT solver of Google OR-Tools 9.5. Both are used with default parameters. We ran them on a server equipped with an Xeon 8375C (8 cores, 2.9 GHz, 55MB cache) and 32GB RAM.

On average, Hexaly achieves a 2.6% gap to the best known solution, while OR-Tools only reaches an 8.1% gap.

The table below shows the number of instances where each solver reaches a solution below a particular gap. For example, Hexaly always finds a solution with a gap to the best known solution below 10%, but OR-Tools only does so for 59% of the instances.

Conclusion

Hexaly offers a concise and straightforward approach to the Resource-Constrained Project Scheduling Problem (RCPSP) based on integer decision variables. The resulting model provides much better solutions than OR-Tools 9.5 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.

Are you interested in trying it out? Get free trial licenses here. In the meantime, feel free to contact us; we will be glad to exchange 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):457-469.