Menu
The problem of task allocation in distributed systems has been studied by many researchers. Several approaches have been used to model and study the problem, including integer programming, heuristic methods, and graph theoretic models. These approaches considered only restricted forms of the general problem. In this paper, we introduce a new model to represent the problem of allocating tasks on heterogeneous distributed systems. The model consists of a complete split graph that represents the communication cost among tasks as well as the execution cost of each task on the system processors. This model allows the incorporation of various constraints into the allocation problem. We show that the task allocation problem is equivalent to the problem of weighted clique partitioning in complete split graphs, which we proved to be NP-complete. We present a clique partitioning algorithm that employs the properties of split graphs for solving the problem in its general form. We show that the algorithm generates optimal solutions in some cases, while performing fairly well in general.