A task duplication based scheduling algorithm with optimality condition in heterogeneous systems

The task scheduling problem is NP-hard in heterogeneous systems. We propose a task scheduling algorithm based on task duplication with an optimality condition to determine whether or not the resulting schedule has the shortest schedule length. The optimality condition is that, given any join task, the completion time of a parent task is longer than the maximum message arrival times from the other parent tasks. An illustrative example is given to show how our algorithm differs from existing algorithms.