Task scheduling by limited duplication on a bounded set of heterogeneous processors

This paper addresses the static scheduling of a directed acyclic task graph (DAG) on a heterogeneous, bounded set of distributed processors to minimize the makespan. By analyzing the task scheduling model, we present a new heuristic, known as Dynamic Critical Path Duplication (DCPD), for scheduling DAG on a set of heterogeneous processors. DCPD assigns the tasks on the dynamic critical path to the suitable processor which minimizes the earliest finish time for them, combining insertion-based scheduling and task duplication techniques. The comparison study by simulation on Simgrid, based on randomly generated DAG, shows that DCPD surpasses previous approaches in terms of both quality and cost of schedules, which are mainly presented with schedule length, frequency of best result, and scheduling time metrics.