Synchronized sweep algorithms for scalable scheduling constraints
Number of Authors: 3
2013 (English)Report (Other academic)
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.
Place, publisher, year, edition, pages
Kista, Sweden: Swedish Institute of Computer Science , 2013, 7.
SICS Technical Report, ISSN 1100-3154 ; 2013:05
Computer and Information Science
IdentifiersURN: urn:nbn:se:ri:diva-15377OAI: oai:DiVA.org:ri-15377DiVA: diva2:1036694