Parallelizing Constraint Solvers for Hard RCPSP Instances

Roberto Amadini 1, 2 Maurizio Gabbrielli 2, 1 Jacopo Mauro 3
1 FOCUS - Foundations of Component-based Ubiquitous Systems
CRISAM - Inria Sophia Antipolis - Méditerranée , DISI - Dipartimento di Informatica - Scienza e Ingegneria [Bologna]
Abstract : 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.
Document type :
Reports
Complete list of metadatas

Cited literature [34 references]  Display  Hide  Download

https://hal.inria.fr/hal-01295061
Contributor : Jacopo Mauro <>
Submitted on : Wednesday, March 30, 2016 - 12:34:25 PM
Last modification on : Wednesday, October 10, 2018 - 10:09:23 AM
Long-term archiving on : Monday, November 14, 2016 - 8:56:19 AM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01295061, version 1

Collections

Citation

Roberto Amadini, Maurizio Gabbrielli, Jacopo Mauro. Parallelizing Constraint Solvers for Hard RCPSP Instances. [Technical Report] Inria Sophia Antipolis. 2016. ⟨hal-01295061⟩

Share

Metrics

Record views

315

Files downloads

508