Name
Abstract | ||
|---|---|---|
Cumulative is an essential constraint in the CP framework, and is present in scheduling and packing applications. The lightest filtering for the cumulative constraint is time-tabling. It has been improved several times over the last decade. The best known theoretical time complexity for time-table is $$On \\log n$$Onlogn introduced by Ouellet and Quimper. We show a new algorithm able to run in On, by relying on range min query algorithms. This approach is more of theoretical rather than practical interest, because of the generally larger number of iterations needed to reach the fixed point. On the practical side, the recent synchronized sweep algorithm of Letort et al, with a time-complexity of $$On^2$$On2, requires fewer iterations to reach the fix-point and is considered as the most scalable approach. Unfortunately this algorithm is not trivial to implement. In this work we present a $$On^2$$On2 simple two step alternative approach: first building the mandatory profile, then updating all the bounds of the activities. Our experimental results show that our algorithm outperforms synchronized sweep and the time-tabling implementations of other open-source solvers on large scale scheduling instances, sometimes significantly. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-319-23219-5_11 | International Conference on Principles and Practice of Constraint Programming |
Keywords | Field | DocType |
Constraint programming, Large-scale, Scheduling, Cumulative constraint, Time-table | Mathematical optimization,Scheduling (computing),Computer science,Constraint programming,Algorithm,Filter (signal processing),Implementation,Fixed point,Time complexity,Scalability | Conference |
Volume | ISSN | Citations |
9255 | 0302-9743 | 3 |
PageRank | References | Authors |
0.48 | 6 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Steven Gay | 1 | 10 | 1.02 |
| Renaud Hartert | 2 | 56 | 4.15 |
| Pierre Schaus | 3 | 127 | 24.63 |