Heuristic Functions

Algorithm Heuristic Functions

The A* implementation that was used in this algorithm relied on a set of heuristic functions that determined a partial schedule's cost function; this cost function represents the lower bound of the finishing time of a partial schedule.

The lower bound is calculated by finding the maximum of all three heuristic functions to set an underestimate of the potential lower bound.

costFunction = maximum{maxDRT, maxBL, maxIdleTime}

---

1. Bottom Level

This function is based on tasks that have already been scheduled. The bottom level cost encapsulates the longest path in the task graph for the current partial schedule. It uses the critical path of the next node to be scheduled. This way, the lower bound can be determined by the longest path to the schedule without communication cost.

f_BL(s) = max_{n∈partialSchedule}{t_s(n) + bl_w(n)}

where t_s(n) is

2. Data Ready Time

3. Idle Time