Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1007/s10601-014-9172-8 | Constraints |
Keywords | Field | DocType |
Global constraint,Cumulative,Scalability,Fixpoint,Sweep | Mathematical optimization,Job shop scheduling,Computer science,Scheduling (computing),Filter (signal processing),Algorithm,Fixed point,Scalability | Journal |
Volume | Issue | ISSN |
20 | 2 | 1383-7133 |
Citations | PageRank | References |
0 | 0.34 | 14 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Arnaud Letort | 1 | 12 | 1.76 |
Mats Carlsson | 2 | 975 | 79.24 |
Nicolas Beldiceanu | 3 | 547 | 51.14 |