A priority based algorithm for task graph scheduling in multiprocessor systems

In this paper a method has been proposed for priority based task graph scheduling which utilize the mixture of genetic and simulated annealing algorithms for prioritizing the tasks. This method tries to find a near-optimal sequence for scheduling that is not rely on a specific parameter for prioritizing the tasks. Priority of the tasks is determine during the scheduling algorithm using simulated annealing. The simulated annealing is trying to search over problem space to find the best sequence of the tasks for execution. Simulation results and comparisons in different scenarios are shown the appropriate performance of the introduced task scheduling scheme.

Keywords:

Static task scheduling , directed acyclic graph , genetic algorithm , Simulated annealing