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.

Beldiceanu, NicolasINRIA, France (författare)
Carlsson, MatsRISE,Computer Systems Laboratory(Swepub:ri)MatsCa@ri.se (författare)
INRIA, FranceComputer Systems Laboratory (creator_code:org_t)

Av författaren/redakt...: Letort, Arnaud; Beldiceanu, Nico ...; Carlsson, Mats

Om ämnet

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.