next up previous contents
Next: ``Bound'' Up: Program Design Previous: Program Design

Partial Schedule Tree

My last algorithm uses branch and bound techniques to solve the scheduling optimization problem. The algorithm searches a schedule tree for the lowest cost schedule, each node in the tree contains a partial schedule of the tasks on the three processors. Below is a visual description of the tree:

tex2html_wrap82

This is what a tree would look like containing all the orderings of 2 tasks. In a node there is a string of 0s, 1s, and 2s which represent the placement of the tasks on the three processors 0, 1, and 2. A 0 in the left most position means that task one is done by processor 0, a 1 in the next left most position would mean task two is done by processor 1, and so on.



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