Pruning

Pruning

Pruning was used to reduce the search space of partial schedules, reducing memory consumption and speeding up execution time as fewer schedules have to be explored by the algorithm.

Three pruning techniques were used:

1. Duplicate Detection
2. Processor Normalisation
3. Identical Tasks

Duplicate Detection

Duplicate partial schedules occur when taking into consideration the order of scheduling each task. However we do not care about the order of scheduling tasks as the partial schedules will be equivalent in state, unnecessarily expanding the search state.

When implementing partial scheduling, we used hash sets to store the partial schedules. By the nature of hash sets in Java, duplicate objects are not stored in a set. This was done by overriding the hash code and equals methods within the Processor and PartialSchedule classes to ensure that if a partial schedule had already been generated, no other duplicate partial schedules are added to the search space.

Normalisation

As all processors are identical and exchangeable, if there are two partial schedules that are different but become the same when swapping the processor names in the schedule, this means one of the schedules can be pruned. This is because there is no preference for the processor names in the partial schedule.

To prune these "identical" partial schedules, we normalise by not taking into consideration the processor names when doing equality checks when deciding whether to add partial schedules into OPEN.

Identical Tasks

Identical tasks are represented in our implementation as identical nodes where the following conditions are met:

• Same task weights
• Same parent nodes
• Same children nodes
• Same incoming edge weights
• Same outgoing edge weights

As the nodes are identical, the order of scheduling these nodes does not matter. As the nodes are independent of each other, our A* algorithm will consider all possible permutations. However, this is unnecessary and by chaining these identical nodes, this means the search space will be significantly pruned.