Filtering Algorithms for Discrete Cumulative Resources, ch. 6

Chapter 6


The application of the Θ-tree to cumulative scheduling problems brings to cumulative scheduling filters a substantial reduction in time complexity, but comes at the cost of a significantly more complicated algorithm. Without a prior understanding of edge-finding , parts of the algorithm presented in [39] can be quite opaque; it would be unfortunate if this opacity were to discourage potential implementors from tackling this quite beautiful algorithmIt is Referring to yourselfthe author’s hope that[/annotax] this thesis can serve those uninitiated in edge-finding as both an introduction to the theory as well as a clarification of some of the more challenging sections of the original paper.

Of the latter, the update calculation section [39, Section 7] is perhaps most in need of further explanation. Towards this end significant space has been spent here attempting to shed light on both the idea underlying this portion of the algorithm (including a revision to the proof in the original paper), and to dealing with those parts of the update procedure omitted from the original.

Additionally , several new contributions to the algorithm are presented here, perhaps the most significant being the non-cutting algorithm for calculating the values of the α and β subtrees during the calculation of Envc.

The results of the parallel version of the edge-finding algorithm were encouraging, and perhaps merit further investigation. Also, the combination of the edge-finding and max energy algorithms allows for some handling of variable task resource requirements and durations in the filter, helping to broaden the range of real-world applications for this scheduling algorithm.

6.1 Future Work

The most interesting additional work in this area is probably the application of similar methods to other relaxations of the cumulative constraint. RecentlySchutt and Wolf have proposed an algorithm for cumulative not-first/not-last filtering that uses an innovative modification of the Θ-tree to achieve O(n² log n) complexity [33]. As the authors note there, the existence of an O(kn log n) cumulative edge-finding algorithm suggests that the complexity of cumulative not-first/not-last might be reducible to that same point. There is also a stronger variant of the edge-finding rule, commonly called extended edge-finding. Mercier and Van Hentenryck [22]  provide an extended edge-finding algorithm with the same complexity as their (non-extended) edge-finding algorithm (On²k); this suggests that, using the Θ-tree, it might be possible to develop an O(kn log n) algorithm for extended edge-finding as well.