Optimal task allocation in distributed systems by graph matching and statespace search

We consider the problem of finding an optimal allocation of tasks onto proc essors of a distributed computing system. The processors need not have any particular inter-connection structure. We consider two models, one in which no precedence relations exist between tasks, and another in which there ar e precedence relations between tasks. Each task causes two types of costs t o be incurred by the processor to which it is allocated - the execution cos t of the task (which varies from processor to processor in a heterogeneous system), and communication cost when the task has to communicate with other tasks which are not allocated to the same processor. The aim of the task allocation (problem) is to minimize the total turnaroun d time of ail tasks put together. This problem is known to be NP-hard when there are more than three processors. We use a state space search technique - the A* algorithm to obtain an optimal allocation. We propose a method to reduce the number of nodes generated in the state space search tree. We co mpare our algorithm for the optimal task allocation problem with that of si milar existing algorithms, and show its effectiveness by performing extensi ve simulations over a wide range of parameters. (C) 1999 Elsevier Science I nc. Air rights reserved.