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

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.

Keywords

• task allocation
• distributed systems
• performance evaluation
• genetic algorithm. simulated annealing