SODA

Synchronized sweep algorithms for scalable scheduling constraints

Letort, Arnaud and Carlsson, Mats and Beldiceanu, Nicolas (2014) Synchronized sweep algorithms for scalable scheduling constraints. Constraints, 19 (4). pp. 1-52. ISSN 1383-7133 (Print) 1572-9354 (Online)

Full text not available from this repository.

Official URL: http://link.springer.com/article/10.1007/s10601-01...

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.

Item Type:Article
Uncontrolled Keywords:Global constraint, Cumulative, Scalability, Fixpoint, Sweep
ID Code:5723
Deposited By:Mats Carlsson
Deposited On:04 Nov 2014 09:06
Last Modified:04 Nov 2014 09:06

Repository Staff Only: item control page