Synchronized sweep algorithms for scalable scheduling constraints

Arnaud Letort 1, 2, 3 Mats Carlsson 4 Nicolas Beldiceanu 1
1 TASC - Theory, Algorithms and Systems for Constraints
Inria Rennes – Bretagne Atlantique , Département informatique - EMN, LINA - Laboratoire d'Informatique de Nantes Atlantique
Abstract : This paper 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 resource constraints and 2 million precedences. These algorithms were implemented in both CHOCO and SICStus.
Document type :
Journal articles
Complete list of metadatas

https://hal.inria.fr/hal-01086765
Contributor : Contraintes Lina <>
Submitted on : Monday, November 24, 2014 - 6:19:36 PM
Last modification on : Friday, June 22, 2018 - 9:32:21 AM

Links full text

Identifiers

Citation

Arnaud Letort, Mats Carlsson, Nicolas Beldiceanu. Synchronized sweep algorithms for scalable scheduling constraints. Constraints, Springer Verlag, 2014, pp.52. ⟨10.1007/s10601-014-9172-8⟩. ⟨hal-01086765⟩

Share

Metrics

Record views

524