onr:"swepub:oai:DiVA.org:ri-24091"
Search: onr:"swepub:oai:DiVA.org:ri-24091" > A Scalable Sweep Al...
- 1 of 1
- Previous record
- Next record
- To hitlist
- Letort, ArnaudINRIA, France (author)
A Scalable Sweep Algorithm for the Cumulative Constraint
- 6
- Article/chapterEnglish2012
Publisher, publication year, extent ...
- Berlin, Heidelberg :Springer,2012
- printrdacarrier
Numbers
- LIBRIS-ID:oai:DiVA.org:ri-24091
- https://urn.kb.se/resolve?urn=urn:nbn:se:ri:diva-24091URI
- https://doi.org/10.1007/978-3-642-33558-7_33DOI
Supplementary language notes
- Language:English
- Summary in:English
Part of subdatabase
- SwePubSwePub
Classification
Notes
- 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.
Subject headings and genre
- NATURVETENSKAP Data- och informationsvetenskap hsv//swe
- NATURAL SCIENCES Computer and Information Sciences hsv//eng
- Average-case complexity
- Bin-packing
- Sweep algorithms
- Time complexity
- Worst-case complexity
Added entries (persons, corporate bodies, meetings, titles ...)
- Beldiceanu, NicolasINRIA, France (author)
- Carlsson, MatsRISE,Computer Systems Laboratory(Swepub:ri)MatsCa@ri.se (author)
- INRIA, FranceComputer Systems Laboratory (creator_code:org_t)
Internet link
To the university's database
- 1 of 1
- Previous record
- Next record
- To hitlist
Find more in SwePub
- By the author/editor
- Letort, Arnaud
- Beldiceanu, Nico ...
- Carlsson, Mats
- About the subject
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- By the university
- RISE
Search outside SwePub
- Extend your search to:
- Google Book Search
- Google Scholar
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.
- Copyright © LIBRIS - National Library Systems
- LIBRIS.kb.se
