A Tabu search for the heterogeneous dag scheduling problem

Abstract—Scheduling parallel applications on heterogeneous processors/architectures with different computational speed is a difficult problem. Here, a tabu search metaheuristic is developed to improve the schedule generated by list scheduling. Three neighbourhoods variants are proposed and examined, including a novel neighbourhood that takes the shape of the task graph into account. The effectiveness is evaluated based on a set of modified random benchmark graphs, including task graphs of real-world applications. Factors affecting algorithm performance are also examined. We have found that the variants proposed were able to reduce the schedule length produced by HEFT up to an average of 30 % and up to on average 20 % for the standard graphs. The results also show that using information about the shape of the task graph is a viable strategy. Keywords-scheduling; heterogeneous; tabu search; meta-heuristic; directed acyclic graphs; DAG; I