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

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.

Hexaly | OR-Tools | |
---|---|---|

Average gap | 2.6% | 8.1% |

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.

Hexaly | OR-Tools | |
---|---|---|

Gap < 20% | 100% | 97% |

Gap < 15% | 100% | 81% |

Gap < 10% | 100% | 59% |

Gap < 5% | 81% | 43% |

Gap < 2.5% | 54% | 28% |

Gap < 1% | 35% | 18% |

## 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.