A greedy algorithm for scheduling fork-join task graphs

The goal of task scheduling algorithm is to allocate the tasks of a parallel program to processors in order to minimize the completion time of the program. This is known as an NP-complete problem. Although a large number of scheduling heuristics have been presented in the literature, most of them ignored to economize processors and minimize total completion time. In this paper, we present a greedy algorithm for scheduling fork-join task graph, which can generate better schedule results. The time complexity of the proposed algorithm is O(v²), where v is the number of tasks. Experimental comparisons with other algorithms show very favorable results.