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

Benchmark Construction Scheduling

Léa Optimization Scientist August 12, 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.

This page illustrates how Hexaly improves the literature’s best known lower bounds on more than 34% of the instances from a large RCPSP benchmark. For more information on upper bounds, please refer to the benchmark against the CP-SAT solver available in Google OR-Tools on our RCPSP benchmark webpage.

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.

Hexaly’s stronger and faster bounds for scheduling problems

Hexaly 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 Hexaly to compute high-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 with the Energy Precedence propagation and the linear energetic relaxations.

Hexaly’s new records for the Resource-Constrained Project Scheduling Problem (RCPSP)

We consider the lower bound provided by Hexaly 13.0 within 1 minute of running time. We ran the solver on a computer equipped with an AMD Ryzen 7 7700 processor (8 cores, 3.8GHz, 8MB cache) and 32GB RAM to obtain these results. 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, Hexaly improves the best known lower bounds on 34% of the instances from the RG300 RCPSP benchmark (165 instances over 480), with an average improvement of 4.7%. 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 Hexaly compared to the literature.

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

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