next up previous contents
Next: ``Branch'' Up: Program Design Previous: Partial Schedule Tree

``Bound''

Branch and bound is a way of searching the tree of partial schedules where at each node the next best node is searched. The ``next best'' information is obtained from a lower bound calculation of the partial schedule, the ``bound'' of branch and bound. The bound is calculated by finding a cost histogram of the partial schedule where one bar of the histogram is the time of that partial schedule for that processor. Perhaps a picture will help:

tex2html_wrap98

Here (A) is the cost histogram for some partial schedule, c is the cost of this partial schedule. In (B) we have applied the lower bound calculation to the histogram. We took the lowest cost on any one of the processors for the remaining tasks and distributed them across (A) in the best possible manner. First fill in the valleys of the histogram with some time, c becomes the height of all three bars. Then divide the remaining time among the 3 processors that height, e, of the histogram is the best possible extension of this partial schedule can have. The lower bound on the complete schedule is e+c. The function that does this calculation of the lower bound is called rank in my algorithm.



Jamie Marconi
Thu May 23 19:44:07 PDT 1996