Study of the task assignment problem in the distributed systems: cost functions and resolution methods

• José Lisandro Aguilar Castro Universidad de los Andes-Venezuela
• Leila Kloul Université de Versailles-Francia

Abstract

In the Distributed Systems, the task allocation is one of the most important problem to take into account. This problem is NP-complete, that is why the researchers have reduced the problem dimensions deleting criteria and/ or imposing constraints. In this paper, we present the problem and we define one basic objective function, which can be used to make an optimal allocation. The definition of this function uses the fol1owtng criteria: the communication cost between the processors, the task execution time, the interference cost, the load balancing cost and the reference cost to files in other sites. An adaptation of the costs to several type of architectures is presented. Finally, we present several techniques of combinatorial optimization and we apply two of them, Simulated Annealing and Genetic Algorithm, to salve the task assignment problem.