System disruptions
We are currently experiencing disruptions on the search portals due to high traffic. We are working to resolve the issue, you may temporarily encounter an error message.
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: 74 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