In this paper we tackle the task assignment problem (TSAP) in heterogeneous computer systems. The TSAP consists of assigning a given distributed computer program formed by a number of tasks to a number of processors, subject to a set of constraints, and in such a way a given cost function to be minimized. We introduce a novel formulation of the problem, in which each processor is limited in the number of task it can handle, due to the so called resource constraint. We propose two hybrid meta-heuristic approaches for solving this problem. Both hybrid approaches use a Hopfield neural network to solve the problem's constraints, mixed with a genetic algorithm (GA) and a simulated annealing for improving the quality of the solutions found. We test the performance of the proposed algorithms in several computational TSAP instances, using a GA with a penalty function and a GA with a repairing heuristic for comparison purposes. We will show that both meta-heuristics approaches are very good approaches for solving the TSAP. © 2004 Elsevier Ltd. All rights reserved.
Bibliographical noteDr. Sancho Salcedo-Sanz is supported by a postdoctoral fellowship of Ministerio de Educación Cultura y Deporte of Spain, fellowship number EX2003-0463. The authors would like to thank Prof. G. Laporte and one anonymous referee for their assistance and help in the revision of this paper.
- Genetic algorithms
- Heterogeneous computer systems
- Simulated annealing
- Task assignment