Sökning: WFRF:(Beldiceanu Nicolas)
> (2010-2014) >
A Scalable Sweep Al...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
Nyckelord
- Average-case complexity
- Bin-packing
- Sweep algorithms
- Time complexity
- Worst-case complexity
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)