Parallel tabu search message-passing synchronous strategies for task scheduling under precedence constraints

Parallel tabu search message-passing synchronous strategies for task scheduling under precedence constraints

0.00 Avg rating0 Votes
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: ,
Keywords: scheduling
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.