A* scheduling algorithm

A* is a tree search algorithm that may be used to solve the task scheduling problem. It is also an optimal search algorithm [2]. It begins the search with an empty solution space and is then incrementally grown. A* employs a best-first search technique and is guided by a problem specific cost function. A* keeps all the nodes in memory and it usually runs out of memory before it runs out of time making it unusable for medium and large sized problem instances. This memory problem of the A* search approach has been recognised earlier and alternative approaches overcoming this problem have been proposed making trade-offs between memory requirement and performance.

Iterative Deepening A* (IDA*) scheduling algorithm

The proposed IDA* scheduling algorithm in [1] follows the depth-first iterative deepening methodology to traverse its search space. It sets the initial threshold to a value that is below the optimal schedule length and it is then successively increased. When the optimal schedule length is found, the IDA* scheduling algorithm terminates. It limits the initial depth of the search tree to a number that is a lower bound on the schedule length. If a feasible schedule is not found for the given search depth (I.e. schedule length) on the present iteration, the next iteration increments the lower bound (threshold) on the schedule length. The IDA* scheduling algorithm for any given iteration regenerates all the states for the previous iteration along with the new states generated for the present iteration. The main motivation for proposing the IDA* scheduling algorithm is that it has a memory requirement of the order of number of tasks in the task graph. This gives IDA* an extremely small memory footprint when compared to the A* scheduling algorithm. On the downside, IDA* generates more states than A* due to iterative deepening.

Depth First - Branch and Bound A* (BBA*) scheduling algorithm

BBA* is another memory bound algorithm that searches the state space in depth first order. The initial feasible solution is an overestimate on the optimal solution. As such it approaches the optimal solution from above, successively improving the best found solution. The proposed BBA* scheduling algorithm [1] has a memory requirement of the order of number of tasks in the graph. This gives BBA* an extremely small memory footprint when compared to the A* scheduling algorithm, however at the cost of exploring more states in general.

The list of optimal schedules obtained in [1] by experimentation for a one minute time out (I.e. all the optimal schedules generated within 1 minute) from a database of 207 graphs may be accessed here.

Reference

[1]. Sarad Venugopalan and Oliver Sinnen. Memory Limited Algorithms for Optimal Task Scheduling on Parallel Systems. Submitted to Journal of Parallel and Distributed Computing.

[2]. Oliver Sinnen, Reducing the solution space of optimal task scheduling. Computers & OR 43: 201-214 (2014) [Abstract] .