Task scheduling for heterogeneous systems using an incremental approach

Effective scheduling of the tasks of a distributed application is one of the key factors in achieving improved performance. It results in an adequate utilization of the underlying resources and also reduces the total execution time of the application. Generating an optimal schedule for a distributed application is not a trivial task as it exists in the class of NP-complete problems. In this paper, a novel strategy called incremental subgraph earliest finish time (INCSEFT) is proposed. It is aimed at scheduling tasks on heterogeneous systems. It incorporates the use of a subgraph that grows incrementally by adding critical paths. At each step, the scheduling strategy attempts to minimize the schedule length. Considering a large set of nodes at an instance makes this approach perform better than other scheduling strategies used for heterogeneous systems. The experiments performed with several graphs show that the INCSEFT strategy produces significant improvement over the well-known HEFT, LOOKAHEAD and CEFT strategies used for scheduling heterogeneous systems.