Exact algorithms for a task assignment problem

Kamer Kaya and Bora Uçar

Abstract. We consider the following task assignment problem. Communicating tasks are to be assigned to heterogeneous processors interconnected with a heterogeneous network. The objective is to minimize the total sum of the execution and communication costs. The problem is NP-hard. We present an exact algorithm based on the well-known A* search. We report simulation results over a wide range of parameters where the largest solved instance contains about three hundred tasks to be assigned to eight processors.

Key words. Task assignment, heterogeneous computing systems, task interaction graph, A* search