Parallelizing Constraint Solvers for Hard RCPSP Instances
- Others:
- Foundations of Component-based Ubiquitous Systems (FOCUS) ; Inria Sophia Antipolis - Méditerranée (CRISAM) ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Dipartimento di Informatica - Scienza e Ingegneria [Bologna] (DISI) ; Alma Mater Studiorum Università di Bologna [Bologna] (UNIBO)-Alma Mater Studiorum Università di Bologna [Bologna] (UNIBO)
- Department of Computer Science and Engineering [Bologna] (DISI) ; Alma Mater Studiorum Università di Bologna [Bologna] (UNIBO)
- University of Oslo (UiO)
- Inria Sophia Antipolis
Description
The Resource-Constrained Project Scheduling Problem (RCPSP) is a well-known scheduling problem aimed at minimizing the makespan of a project subject to temporal and resource constraints. Constraint Programming allows to model and solve RCPSPs in a natural and efficient way, especially when Lazy Clause Generation (LCG) techniques are employed. In this paper we show that hard RCPSPs can be efficiently tackled by a portfolio approach that combines the strengths of different —not necessarily LCG-based— solvers by exploiting their parallel execution on multiple cores. Our approach seeks to predict and run the best solvers for a new, unseen RCPSP instance and also enables the bounds communication between them. This on-average allows to outperform the oracle solver that always chooses the best available solver for any given instance.
Additional details
- URL
- https://hal.inria.fr/hal-01295061
- URN
- urn:oai:HAL:hal-01295061v1
- Origin repository
- UNICA