A greedy clustering and scheduling algorithm

The task duplication based scheduling in a new approach to the scheduling problems. Although the task duplication based scheduling (TDS) algorithm proposed by Darbha and Agrawal generates an optimal schedule, the optimality condition is very restricted. Thus, Park and Choe proposed an extended TDS algorithm whose optimality condition is less restricted than that of the algorithm, but the condition is very complex. In this paper, we provide a greedy algorithm whose schedule length is shorter than both of the algorithms. The time complexity of our algorithm is in O(|V|²), where |V| represents the number of tasks.