Article ID: | iaor20002949 |
Country: | United States |
Volume: | 1 |
Issue: | 3 |
Start Page Number: | 207 |
End Page Number: | 223 |
Publication Date: | Jul 1995 |
Journal: | Journal of Heuristics |
Authors: | Ribeiro Celso C., Porto Stella C.S. |
Keywords: | scheduling |
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 show 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.