Filtering Algorithms for Discrete Cumulative Resources, Abstract


Edge finding is an algorithm commonly used in constraint-based scheduling. For problems of n tasks, several O(n log(n)) algorithms exist for edge finding in unary resource scheduling; however , edge finding with cumulative resources is more complicated, resulting in O(kn2) complexity at best (where k is the number of distinct resource demands). Recently Vilím [40] proposed a new algorithm for cumulative edge finding, which uses a novel data structure called the theta tree to improve the complexity to O(kn log(n)). This thesis presents work performed while implementing this new algorithm . Several areas not covered in the original paper, such as the choice of tree structure and best loop order in the adjustment phase, are discussed here. Additionally , several minor improvements to the algorithm are described, and two significant errors in the original paper identified. The symmetry of adjusting each task’s upper and lower bounds is considered in detail, and a proof of the monotonicity of the algorithm is provided. Also, issues in creating a parallel version of this algorithm are discussed , and implementation details for several parallel version are provided . In a separate paper , Vilím used the theta tree to design a max energy filtering algorithm, which handles tasks with variable durations and resource demands; this algorithm is also implemented here, and combined with the edge-finding algorithm.