A TABU SEARCH APPROACH TO TASK-SCHEDULING ON HETEROGENEOUS PROCESSORSUNDER PRECEDENCE CONSTRAINTS

Parallel programs may be represented as a set of interrelated sequenti al tasks. When multiprocessors are used to execute such programs, the parallel portion of the application can be speeded up by an appropriat e allocation of processors to the tasks of the application. Given a pa rallel application defined by a task precedence graph, the goal of tas k scheduling (or processor assignment) is thus the minimization of the makespan of the application. In a heterogeneous multiprocessor system , task scheduling consists of determining which tasks will be assigned to each processor, as well as the execution order of the tasks assign ed to each processor. In this work, we apply the tabu search metaheuri stic to the solution of the task scheduling problem on a heterogeneous multiprocessor environment under precedence constraints. The topology of the Mean Value Analysis solution package for product form queueing networks is used as the framework for performance evaluation. We show that tabu search obtains much better results, i.e., shorter completio n times, improving from 20 to 30% the makespan obtained by the most ap propriate algorithm previously published in the literature.