-
Notifications
You must be signed in to change notification settings - Fork 2
Algorithm Approach
Our implementation of this project relied primarily on a standard A* algorithm (adapted to the problem space) for the first milestone, but has been replaced by the DFS / BB A* algorithm. This is because it is more efficient in all regards (memory wise and computationally).
Our A* implementation is based heavily on the work of Oliver Sinnen (see: Reducing the solution space of optimal task scheduling https://researchspace.auckland.ac.nz/handle/2292/30213). Thanks to Oliver's research, we were able to implement several pruning techniques to greatly reduce the search space and therefore improve both speed and resource use. The pruning techniques for this algorithm are:
- Closed List
- Processor Normalization
- Identical Tasks
- Equivalent Schedules
Our Branch and Bound A* algorithm started as a normal DFS algorithm but evolved when the cost function used for the default A* algorithm was assigned to it. This was based on the DFS algorithm in the slides, and also gained inspiration from the same resource detailed above. The pruning techniques used for this algorithm are:
- Closed List
- Processor Normalization
- Identical Tasks
- Equivalent Schedules
During algorithm runs, a list of all "closed" states is kept. These are states whose children have either been fully explored or discarded, meaning the state is no longer of any use to explore. Any state about to be explored can be checked if it is on the closed list, and discarded if so.
As the processors for scheduling are in theory homogeneous, schedules with the exact same task allocation but with processors in different orders/with different names can be counted as the same schedule. This pruning technique allows processor-equivalent schedules to be discarded, thus reducing the search space greatly. This normalization process is used to check if a state or its processor-equivalent states have already been added to the closed list, as when a state is added to closed list, its normalized form (processors in specific fixed order) is added.
Schedules that differ only on the arrangement of tasks which can be said to be "identical" (exact same weights and ingoing/outgoing dependency edges) are also equivalent. Therefore there is no point to explore every variation of this type. These extra states can be pruned by forcing identical tasks to be added in a fixed order (by adding virtual 0-cost edges between them at initialization). This also reduces search space.
Equivalent Schedule pruning discards states that have an "equivalent" i.e a state with the exact same finish time "shape" and earliest starting time on all processors for all free tasks (same scheduling horizon). If a state has one or more equivalents, and is NOT in topological order, it will be ignored, meaning that only equivalent states in topological order (one per set of equivalents) is explored, thereby reducing search space greatly on certain shaped graphs.
The fixed task order pruning technique has been implemented, but was deprecated due to its conflicting nature with the Equivalent Schedules pruning technique. Topological ordering of the tasks could not be guaranteed, and therefore they could not coexist.