Filtering Algorithms for Discrete Cumulative Resources, ch. 6

Chapter 6 Conclusion

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 algorithm. It 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. Recently , Schutt 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.

Different fields of study have different traditions about whether authors can refer to themselves as “I” or “We” when discussing their thoughts and actions. An advantage of using “I/We” is that active verbs may be used. A disadvantage is that emphasis is given to the person or persons performing the action, rather than to the action itself.

The most common way to avoid using the first-person perspective is to write as if the text itself is performing actions.

This paper will analyze…; This section will describe…; This research has demonstrated…;

To avoid using the first person, the passive voice is often used.

Mosquitos were collected from 15 sites in Dalarna.

By measuring gene expressions induced in fish tissues, conclusions concerning aquatic ecosystem health can be made.

If the person or persons doing the research must be invoked, the following type of construction can be used.

The graves containing the artefacts were examined by the author. There were four graves for which no gender attributions have been made, to the author’s knowledge.

The indefinite prounoun one can also be used, even if the paper has several authors.

These results lead one to speculate about the future use of solar panels in Sweden.

Scriptor

Texts, Tools, and Tips for Academic Writing

My collection 0

Filtering Algorithms for Discrete Cumulative Resources, ch. 6

Chapter 6

Conclusion

6.1 Future Work

How to refer to yourself