A Scalable Sweep Algorithm for the Cumulative Constraint

• 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)