One of the important steps in software development for distributed computing systems is to allocate tasks efficiently. This task allocation problem also known as a scheduling problem or as a resource allocation problem has been widely studied, but this problem is extremely difficult to solve and is well known that some simplified subproblems still fall in the class of NP-hard problems. Therefore, efficient heuristics are necessary that will take into account more practical models of communication costs.
In this thesis, I propose a simple efficient heuristic algorithm that minimizes the sum of execution and communication costs for arbitrarily connected distributed systems with arbitrary numbers of processors connected with different communication link speeds, provided the interconnection pattern of the modules forms a graph. This algorithm turns out to be more effective and using less computation time than the existing heuristic algorithms.
