Performance evaluation of a parallel tabu search task scheduling algorithm

Abstract This paper presents the solution quality analysis of a parallel tabu search algorithm for the task scheduling problem on heterogeneous processors under precedence constraints. We evaluate the achieved makespan reduction of different parallel applications, relatively to the results obtained by the best greedy algorithm in the literature, as a function of parameters such as problem size, system heterogeneity, and number of processors. Our results show that the parallel tabu search algorithm leads to much better solutions than the greedy algorithm in many cases where the latter is not capable of profiting from the inherent application parallelism and system heterogeneity.