An improved algorithm for task assignment

The goal of task assignment problem is to map tasks on different processors such that system wide objective function is optimized. This problem is known to be NP-complete for assigning a number of tasks and processors. The algorithm proposed in this paper reduces the size of A* explanation tree and thus obtaining the optimal solution faster. The other features of the improved algorithm are: 1) The depth of the created searching tree which represents the number of levels in that tree is small compared to any other existing algorithm. The reason is: if m is the number of tasks in a given problem then, all the existing task-assignment algorithms that use some heuristic functions for search need m levels to achieve the optimal solution, while our algorithm needs for sure a number of levels less than m. 2) Since the searching tree has a few number of levels, the number of expanded and generated nodes are very small compared to most of the other algorithms and consequently a faster solution is accomplished. 3) In a given task problem, if the values of processing and communication costs are multiplied by constant values alpha and I-alpha; respectively, where O<alpha l, then both the number of expanded and generated nodes in the searching tree are completely beyond their values before multiplication. In fact, this is not the case in our algorithm where these values are approximately independent from alpha. The effectiveness of this algorithm is demonstrated by solving several examples and comparing the results with other existing schemes.