Paper Info
Title
A scalable sweep algorithm for the cumulative constraint
Abstract
This paper presents a sweep based algorithm for the cumulative constraint, which can operate in filtering mode as well as in greedy assignment mode. Given n tasks, this algorithm has a worst-case time complexity of O(n2). In practice, we use a variant with better average-case complexity but worst-case complexity of O(n2 logn), which goes down to O(n logn) when all tasks have unit duration, i.e. in the bin-packing case. Despite its worst-case time complexity, this algorithm scales well in practice, even when a significant number of tasks can be scheduled in parallel. It handles up to 1 million tasks in one single cumulative constraint in both Choco and SICStus.
Year
DOI
Venue
2012
10.1007/978-3-642-33558-7_33
CP
Keywords
Field
DocType
scalable sweep algorithm,n task,better average-case complexity,worst-case time complexity,worst-case complexity,cumulative constraint,n2 logn,n logn,algorithm scale,single cumulative constraint,greedy assignment mode
Mathematical optimization,Computer science,Filter (signal processing),Algorithm,Theoretical computer science,Time complexity,Scalability
Conference
Citations 
PageRank 
References 
11
1.06
15
Authors
3
Name
Order
Citations
PageRank
Arnaud Letort1121.76
Nicolas Beldiceanu254751.14
Mats Carlsson397579.24