Synchronized sweep algorithms for scalable scheduling constraints

Letort, Arnaud and Carlsson, Mats and Beldiceanu, Nicolas (2013) Synchronized sweep algorithms for scalable scheduling constraints. [SICS Report]



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.

Item Type:SICS Report
ID Code:5504
Deposited By:Vicki Carleson
Deposited On:12 Apr 2013 18:42
Last Modified:12 Apr 2013 18:42

Repository Staff Only: item control page