| 1. |
- Letort, Arnaud, et al.
(author)
-
A Scalable Sweep Algorithm for the Cumulative Constraint
- 2012. - 6
-
Conference paper (peer-reviewed)abstract
- 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.
|
|
| 2. |
- Letort, Arnaud, et al.
(author)
-
A Synchronized Sweep Algorithm for the k-Dimensional Cumulative Constraint
- 2013. - 9
-
In: CPAIOR. - Berlin, Heidelberg : Springer. ; , s. 144-159
-
Conference paper (peer-reviewed)abstract
- This paper presents a sweep based algorithm for the k-dimensional Cumulative constraint, which can operate in filtering mode as well as in greedy assignment mode. Given n tasks and k resources, this algorithm has a worst-case time complexity of O(kn^2) but scales well in practice. In greedy assignment mode, it handles up to 1 million tasks with 64 resources in one single constraint in SICStus. In filtering mode, on our benchmarks, it yields a speed-up of about k^(3/4) when compared to its decomposition into k independent Cumulative constraints.
|
|
| 3. |
- Letort, Arnaud, et al.
(author)
-
Synchronized sweep algorithms for scalable scheduling constraints
- 2013. - 7
-
Reports (other academic/artistic)abstract
- This report 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 resources constraints and 2 million precedences. These algorithms were implemented in both CHOCO and SICStus.
|
|
| 4. |
- Letort, Arnaud, et al.
(author)
-
Synchronized sweep algorithms for scalable scheduling constraints
- 2015. - 4
-
In: Constraints. - : Springer. - 1383-7133 .- 1572-9354. ; 19, s. 183-234
-
Journal article (peer-reviewed)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.
|
|
