A quadratic edge-finding filtering algorithm for cumulative resource constraints

摘要

The cumulative scheduling constraint, which enforces the sharing of a finite resource by several tasks, is widely used in constraint-based scheduling applications. Propagation of the cumulative constraint can be performed by several different filtering algorithms, often used in combination. One of the most important and successful of these filtering algorithms is edge-finding. Recent work by Vilim has resulted in a O(kn log n) algorithm for cumulative edge-finding (where n is the number of tasks and k is the number of distinct capacity requirements), as well as a new related filter, timetable edge-finding, with a complexity of O(n~2). We present a sound O(n~2) filtering algorithm for standard cumulative edge-finding, orthogonal to the work of Vilim; we also show how this algorithm's filtering may be improved by incorporating some reasoning from extended edge-finding, with no increase in complexity. The complexity of the new algorithm does not strictly dominate previous edge-finders for small k, and it sometimes requires more iterations to reach the same fixpoint; nevertheless, results from Project Scheduling Problem Library benchmarks show that in practice this algorithm consistently outperforms earlier edge-finding filters, and remains competitive with timetable edge-finding, despite the latter algorithm's generally stronger filtering.