Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Synchronized sweep algorithms for scalable scheduling constraints
CNRS INRIA, France.
RISE, Swedish ICT, SICS, Computer Systems Laboratory.ORCID iD: 0000-0003-3079-8095
CNRS INRIA, France.
2015 (English)In: Constraints, ISSN 1383-7133, E-ISSN 1572-9354, Vol. 19, p. 183-234Article in journal (Refereed) Published
Abstract [en]

This paper introduces a family of synchronized sweep-based filtering algorithms for handling scheduling problems involving resource and precedence constraints. The key idea is to filter all constraints of a scheduling problem in a synchronized way in order to scale better. In addition to normal filtering mode, the algorithms can run in greedy mode, in which case they perform a greedy assignment of start and end times. The filtering mode achieves a significant speed-up over the decomposition into independent CUMULATIVE and precedence constraints, while the greedy mode can handle up to 1 million tasks with 64 resource constraints and 2 million precedences. These algorithms were implemented in both CHOCO and SICStus.

Place, publisher, year, edition, pages
Springer , 2015, 4. Vol. 19, p. 183-234
Keywords [en]
Global constraint, Cumulative, Scalability, Fixpoint, Sweep
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:ri:diva-24358DOI: 10.1007/s10601-014-9172-8Scopus ID: 2-s2.0-84924759018OAI: oai:DiVA.org:ri-24358DiVA, id: diva2:1043439
Projects
SICStus PrologAvailable from: 2016-10-31 Created: 2016-10-31 Last updated: 2023-05-05Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopushttp

Authority records

Carlsson, Mats

Search in DiVA

By author/editor
Carlsson, Mats
By organisation
Computer Systems Laboratory
In the same journal
Constraints
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 66 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf