Letort, Arnaud and Beldiceanu, Nicolas and Carlsson, Mats (2012) A Scalable Sweep Algorithm for the "cumulative" Constraint. In: CP.
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/978-3-642-33558-7_33
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(n 2). In practice, we use a variant with better average-case complexity but worst-case complexity of O(n 2 log n), which goes down to O(n log n) 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.
|Item Type:||Conference or Workshop Item (Paper)|
|Deposited By:||Mats Carlsson|
|Deposited On:||17 Jan 2013 11:45|
|Last Modified:||17 Jan 2013 11:45|
Repository Staff Only: item control page