Sökning: onr:"swepub:oai:DiVA.org:ri-24091" >
A Scalable Sweep Al...
-
Letort, ArnaudINRIA, France
(författare)
A Scalable Sweep Algorithm for the Cumulative Constraint
- Artikel/kapitelEngelska2012
Förlag, utgivningsår, omfång ...
-
Berlin, Heidelberg :Springer,2012
-
printrdacarrier
Nummerbeteckningar
-
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
Kompletterande språkuppgifter
-
Språk:engelska
-
Sammanfattning på:engelska
Ingår i deldatabas
Klassifikation
-
Ämneskategori:ref swepub-contenttype
-
Ämneskategori:kon swepub-publicationtype
Anmärkningar
-
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 och genrebeteckningar
Biuppslag (personer, institutioner, konferenser, titlar ...)
-
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)
Internetlänk