ON THE TASK ASSIGNMENT PROBLEM - 2 NEW EFFICIENT HEURISTIC ALGORITHMS

We study the problem of task allocation in heterogeneous distributed s ystems. The objective is the minimization of the sum of processor exec ution and intertask communication costs. We transform the problem to a maximization one, where we try to determine and avoid large communica tion costs and inefficient allocations. After an appropriate graph tra nsformation, we propose two fast algorithms, the Matching based and Ma x Edge heuristics, in order to consider tradeoffs between task cluster ing and task processor assignment. Their performance is evaluated thro ugh an experimental study where solution quality is compared with one of the best up-to-date heuristics for the problem. Results prove that algorithm Max Edge provides greatly improved solutions within short co mputational time even for large size instances. (C) 1997 Academic Pres s.