An optimal scheduling algorithm for fork-join task graphs

The task duplication based scheduling is a new approach to the scheduling problems. This is known as an NP-complete problem. Although some algorithms are able to find an optimal schedule under certain conditions, they ignored to economize processors and minimize the total completion time. We present a task duplication based balance scheduling (TDBS) algorithm which can schedule a class of fork-join task graph with a complexity of O(|V|²), where |V| is the number of tasks. The proposed algorithm generates an optimal schedule with high speedup and efficiency. Simulation results showed that our algorithm has better scheduling length, less completion time and less number of processors than any of compared algorithms.