Synchronized sweep algorithms for scalable scheduling constraints

Arnaud Letort 1 Mats Carlsson 2 Nicolas Beldiceanu 1
1 TASC - Theory, Algorithms and Systems for Constraints
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
Abstract : This report introduces a family of synchronized sweep based filtering algorithms for handling scheduling problems involving resource and precedence constraints. The key idea is to filter all constraints of a scheduling problem in a synchronized way in order to scale better. In addition to normal filtering mode, the algorithms can run in greedy mode, in which case they perform a greedy assignment of start and end times. The filtering mode achieves a significant speed-up over the decomposition into independent cumulative and precedence constraints, while the greedy mode can handle up to 1 million tasks with 64 resources constraints and 2 million precedences. These algorithms were implemented in both CHOCO and SICStus.
Type de document :
Rapport
[Research Report] 2013, pp.49
Liste complète des métadonnées

https://hal.inria.fr/hal-00874331
Contributeur : Contraintes Lina <>
Soumis le : jeudi 17 octobre 2013 - 15:36:04
Dernière modification le : vendredi 22 juin 2018 - 09:32:23

Identifiants

  • HAL Id : hal-00874331, version 1

Citation

Arnaud Letort, Mats Carlsson, Nicolas Beldiceanu. Synchronized sweep algorithms for scalable scheduling constraints. [Research Report] 2013, pp.49. 〈hal-00874331〉

Partager

Métriques

Consultations de la notice

354