Treffer: Performance Evaluation of a Parallel Tabu Search Task Scheduling Algorithm

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 tabu search algorithm is superior to the greedy algorithm in many cases where the latter is not capable of profiting from the inherent application parallelism and system heterogeneity. Keywords: Parallel algorithms, task scheduling, greedy algorithm, tabu search, solution quality. 1 Introduction In parallel processing, the parallel portion of the application can be accelerated according to the number of processors allocated to it. In a homogeneous architecture, where all processors are identical, the sequential portion of the app.