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.
Type de document :
Rapport
[Technical Report] Inria Sophia Antipolis. 2016
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01295061
Contributeur : Jacopo Mauro <>
Soumis le : mercredi 30 mars 2016 - 12:34:25
Dernière modification le : samedi 27 janvier 2018 - 01:31:38
Document(s) archivé(s) le : lundi 14 novembre 2016 - 08:56:19

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

272

Téléchargements de fichiers

268