Synchronized sweep algorithms for scalable scheduling constraints - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2013

Synchronized sweep algorithms for scalable scheduling constraints

Résumé

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.
Fichier non déposé

Dates et versions

hal-00874331 , version 1 (17-10-2013)

Identifiants

  • HAL Id : hal-00874331 , version 1

Citer

Arnaud Letort, Mats Carlsson, Nicolas Beldiceanu. Synchronized sweep algorithms for scalable scheduling constraints. [Research Report] 2013, pp.49. ⟨hal-00874331⟩
263 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More