An efficient scheduling algorithm for dependent tasks
Youlin Ruan, Gan Liu, Qinghua Li, Tingyao Jiang · 2004
Scheduling for dependent tasks is NP-hard. In this paper, we propose a greedy algorithm that can generate a shorter schedule than other major algorithms. The time complexity of our algorithm is O(dv/sup 2/ logv), where v represents the number of tasks and d represents the maximum in degree of tasks. Simulation results show that the proposed algorithm achieves considerable performance improvement over other important algorithms.