In this thesis, I propose a new static scheduling algorithm for allocating task graphs to fully connected multiprocessors. I discuss three reported scheduling algorithms and show that they possess at least one drawback which can lead to poor performance. The proposed algorithm, which uses the Cluster-Merge technique, is different from the previosly proposed algorithms in a number of ways. First, it can schedules any node before its parents are scheduled. Second, it can configurate various strategys for a given DAG.
The proposed algorithm outperforms the previous algorithms by a considerable margin. Despite having a number of new features, the proposed algorithm has admissble time complexity and is suitable for a wide range of graph structures.
