Chapter 2

Edge Finding: Theory

Edge-finding is a filtering technique used in constraint scheduling problems to strengthen bounds on the possible scheduling time of tasks. Edge-finding was first applied to disjunctive scheduling problems in [2], and since that time several efficient algorithms (O(n log n)) have been developed for the disjunctive case [10, 41]. An efficient edge-finding algorithm for the cumulative case has proved somewhat elusive, however. An O(n²k) algorithm (where k is the number of distinct capacity requirements in the tasks) by Nuijten [23] was later improved to O(n²) [7]; unfortunately, this algorithm was recently demonstrated to be incorrect [22], and while a corrected version of the O(n²k) algorithm was given, the O(n²) algorithm had to be set aside. This chapter shall consider a more recent version of the cumulative edge-finding algorithm [39] with O(kn log n) complexity.

2.1 Overview

The central idea [7] of edge-finding algorithms is to find a set of tasks Θ and a task i ∉ Θ in which it can be demonstrated that i will have to be scheduled before (or after) all tasks in Θ. For example, in Figure 2.1 task D must be scheduled after all the tasks in the set {A, B, C}. The logic of this statement is as follows: no matter how we arrange the tasks in {A, B, C} ∪ D, D cannot be completed before t = 7, but all tasks in {A, B, C} must end before t = 5; therefore , D must end after the end of all tasks in {A, B, C}. Formally:

Unfortunately, figuring out the ect of a set of tasks is generally quite complex in cumulative scheduling. Edge-finding typically uses a simpler rule to determine a good lower bound for ect (which following [39, 40] is denoted here as Ect) by treating the energy of the tasks in Θ as fully elastic (see Figure 2.2). This lower bound may be stated as:

Restating Ect somewhat gives us the standard expression of the edge-finding rule:

Definition 2.1 (Cumulative Edge-Finding Rule). Let T be the set of tasks to be scheduled, Θ ⊂ T, and i ∈ T; i ∉ Θ. Then,

where “” means that all activities in Θ must end before the end of i, and “” means that all activities in Θ must start after the start of i.

Once a set Θ and task i that satisfy the edge-finding rule have been located, it is possible to compute a new bound for i; however, a determination of the exact new bound for i is an NP-hard problem [7]. Once more, an update more easily computed is generally used, as illustrated in Figure 2.3. Once again, the energy of the tasks in Θ is treated as completely elastic, but now it is divided into two portions: the maximum amount of energy that can be scheduled without interfering with i, and the rest of the energy (unnamed in [39], but elsewhere denoted restΘ [23]).

[The remainder of Chapter 2 is not shown.]

Chapter 3

Edge Finding: Implementation

In this chapter, a detailed discussion of a complete implementation for the edge-finder described in [39] is provided. In Section 3.1, the storage requirements of the algorithm are explored, and the pseudo-code of an implementation of that storage is given. In [39], only the algorithm for adjusting earliest start time is discussed, so Section 3.2 provides the symmetric method for adjusting last completion time, along with pseudo-code for a generic algorithm for adjusting both bounds. Finally, in Section 3.3, those parts of the algorithm not explained in [39] are discussed, and some errors in the original paper are noted and corrected.

3.1 Data Structures

3.1.1 Θ-tree

The core of the cumulative edge-finding algorithm in [39] is the data structure called the Θ-tree. Specifically, this is an extended version of the Θ-tree called a Θ-Λ-tree; however , the concept of the Θ-tree is used throughout Vilím’s scheduling algorithms (such as disjunctive not-first/not-last, disjunctive detectable precedences [37, 38], disjunctive edge-finding [42, 38], and cumulative max energy filtering [40]), and as such it is worth considering the general attributes and implementation of Θ-tree structures before moving on to the more specific case.

More familiar tree structures, such as heaps and binary search trees, are designed to facilitate sorting or retrieving items based on a key, but Θ-trees perform a different sort of function. As mentioned above, tasks are stored in the leaves of the Θ-tree, sorted by some criterion. This sorting is required for the proper functioning of the tree, but the tree itself does not implement the sorting; the tasks must be sorted before the Θ-tree can be built. The values for all interior nodes must be calculated when the tree is created, but further single node alterations can be handled in O(log n) time.

[The remainder of Section 3.1.1, Section 3.2, and Section 3.3 are not shown.]

3.4 Experimental Results

3.4.1 Correctness

In In-text citation[22],[/annotax] Mercier and Van Hentenryck present an O(kn²) edge-finder which they demonstrate to be complete, i.e. one that detects all bound updates that would be detected by an edge-finder that checked all subsets of tasks. Vilím shows that the edge-finder in [39] will perform updates at least as strong as those performed by the Mercier and Van Hentenryck algorithm. In order to verify this experimentally, the Θ-tree edge-finder implementation described here was run alongside an implementation of the Mercier and van Hentenryck algorithm.

Tests were run on randomly generated task data, for problems of sizes between n = 4 and n = 100. In each test, the same test data was run in each edge-finder; the results were compared to determine whether one implementation had performed a stronger update. Over the course of 100,000 tests, the two algorithms performed exactly the same updates in approximately 99.5% of all cases. In all observed cases in which the algorithms made different adjustments, the Θ-tree edge-finder was the source of the stronger update. Manual calculations performed on these differing results failed to find an instance where the stronger update generated by the Θ-tree edge-finder was invalid.

A preliminary analysis of the test cases with different results seems to indicate that the stronger updates generated by the Θ-tree algorithm are due to the detection improvement proposed in [39, Section 6.2], and discussed further in 3.3.1. This improvement detects some precedences that would not be detected by a standard edge-finder, resulting in stronger updates. While the idea behind this improvement Verbs and the -s endingseems sound, and no experimental case was found in which it resulted in an incorrect update, it is nonetheless important to bear in mind that no proof of the correctness of this improvement is included in [39]. [/annotax] An implementation that includes this modification is, strictly speaking, no longer an edge-finder, but rather a slightly tighter relaxation of the cumulative constraint.

3.4.2 Complexity and Execution Time

For edge-finding algorithms, problem size is dependent not just on the number of tasks (n), but also on the number of distinct resource requirements among the tasks (k). Because the problem is discrete, k ≤ min {C,n}.

Tests were run on problems randomly generated as follows. First, the resource capacity was fixed to C ∈ {2, 5, 10, 20}. For each C, tests were run for all 1 ≤ k ≤ C. With each value of k, twenty tests were run for each value n ∈ [10, 15, 20, … 100]. The value of k was ensured by first randomly selecting k unique values in the range [1..C], and then assigning these values to the tasks by random draw (taking care to verify that each value was used at least once). Once all tests for a given n and k were complete, the two highest and lowest times were discarded, and the remaining times averaged. The results are given in Appendix A.

The results include times for both the Θ-tree edge-finding algorithm and standard edge-finding. For the latter, the algorithm from [22] was used. To make the timing comparison more informative, the standard implementation was developed to utilize the same data structures (excepting, of course, the Θ-tree itself) and memory allocation as the Θ-tree implementation described here. The difference in the execution times can be clearly seen in Figure 3.4. Here, mean execution times for tests of size n are plotted alongside best fit curves of n² and n log n for the standard and Θ-tree implementations respectively (the value of k is constant in each plot). It is clear that the lower complexity of the Θ-tree algorithm quickly pays off as problem size increases, resulting in substantially lower execution times. However , it is also worth noting that for problems of n < 35 the standard edge-finder outperformed the Θ-tree implementation. In [39], the Θ-tree edge-finder was tested alongside the O(n²) algorithm from [7], which is demonstrated to be incomplete in [22]; nevertheless , even against this lower complexity algorithm, Vilím reports a speedup factor of 1.34 for n = 20, and by a factor of over 4 by n = 100. These results are clearly stronger than the speed increases shown here; most likely the implementation discussed in this thesis requires further optimization to equal the original author’s results.

Figure 3.4. Comparison of execution times for edge-finding using a Θ-tree implementation versus the standard algorithm from [22]. [Figure not shown]

Figures 3.5 and 3.6 show the link between k and the complexity of the Θ-tree algorithm. In Figure 3.6 the value of n is fixed while k varies, and the resulting distribution of times is essentially linear.

Figure 3.5. Effect of increasing values of k on execution time for tests where C = 20. [Figure omitted]
Figure 3.6. Execution times for Θ-tree edge-finding for tests of C = 20, in terms of k, the number of distinct capacity requirements among the tasks in each test. The number of tasks is fixed to n = 50 for the lower set, and n = 100 for the upper. [Figure not shown]

3.5 Summary

In the course of outlining the implementation of the Θ-tree edge-finding algorithm given in this chapter , several clarifications to the description given in [39] have been made, and some errors in that paper have been described. For ease of reference, these clarifications and errors are summarized here:

Section 3.1.1 It is noted in [39] that any balanced binary tree may be used to implement the Θ-tree; however , the static structure of the Θ-tree suggests that in practice the nodes may be efficiently stored in an array. Furthermore , if the nodes are populated in the right order, the construction of the Θ-tree becomes an O(n) operation.

Section 3.1.2 An algorithm is specified here to record the leaf responsible for the lambda values of an interior node, and to pass these values up the tree to the root, making it possible to eliminate the O(log n) check procedure used in [39] to locate the responsible leaf node after the fact.

Section 3.2.2 A sign error in [39, algorithm 3] is corrected.

Section 3.3.1 The improvement to order detection outlined in [39, section 6.2] leads to an incorrect strengthening of bounds for fully constrained tasks. To eliminate this problem, it is necessary to ensure that the algorithm does not set prec[i] = lcti.

[The remainder of Section 3.5 is not shown]