Parallel Tabu Search Message-Passing Synchronous Strategies for Task Scheduling under Precedence Constraints

This paper presents parallelization strategies for a tabu search algorithm for the task scheduling problem on heterogeneous processors under task precedence constraints. Parallelization relies exclusively on the decomposition of the solution space exploration. Four different parallel strategies are proposed and implemented on an asynchronous parallel machine under PVM: the master-slave model, with two different schemes for improved load balancing, and the single-program-multiple-data model, with single-token and multiple-token message passing schemes. The comparative analysis of these strategies shows that the tabu search approach for this problem is very suitable to the parallelization of the neighborhood search, with efficiency results almost always close to one for problems over a certain size. Keywords: Task scheduling, tabu search, parallel algorithms, master-slave, SPMD. 1 Introduction When parallel application programs are executed on MIMD machines, the parallel portion of the..