期刊
PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING, CP 2015
卷 9255, 期 -, 页码 149-157出版社
SPRINGER-VERLAG BERLIN
DOI: 10.1007/978-3-319-23219-5_11
关键词
Constraint programming; Large-scale; Scheduling; Cumulative constraint; Time-table
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 O(n log n) introduced by Ouellet and Quimper. We show a new algorithm able to run in O(n), 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 O(n 2), 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 O(n 2) 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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据