Efficient task assignment for distributed computing system

In this paper, a cost function considering execution time, communication time and even idle time, is employed to measure the performance of task assignment in a distributed computing system. We successfully develop a new mathematical model to describe this kind of cost function. The task assignment problem is formulated as one of directed-to-undirected graph mapping (DU-mapping) which maps a directed acyclic task graph onto an undirected system graph. The search of optimal DU-mapping is NP-complete and is transformed into a state space search problem. Using an underestimation to A* algorithm, we can obtain an optimal DU-mapping and prune the most nodes in a state space tree. An alternative overestimation is applied to prune more nodes but also obtain a suboptimal DU-mapping. Results of a wide range of experiments reveal that both estimates perform very well due to close evaluation of the real cost. © 1989 Taylor & Francis Group, LLC.