一个新的相关任务调度算法

现已有许多调度算法在某些特定条件下能产生最优调度。Darbha和Agrawal提出的TDS算法能产生最优调度，其最优条件比较苛刻，实用性不强。Park和Choe提出一种扩展调度算法（Extended TDS），虽然其最优条件比TDS算法的约束条件宽松些，但在任务数较多时难以满足，并且形式过于复杂。因此，本文提出一种能产生最优调度的新算法，该算法既考虑合并其它父任务以减少通讯时间，同时尽可能少地合并其它任务，从而尽量减小任务的启动时间。该算法不仅最优条件简单、宽松，而且具有与TDS算法相同的时间复杂度O（v^2）。

A New Scheduling Algorithm for Dependent Tasks

There are some algorithms that are able to find an optimal schedule under certain conditions. The task duplication based scheduling (TDS) algorithm proposed by Darbha and Agrawal generates an optimal schedule,but its optimality condition is so restricted that it cannot be applied. Thus, Park and Choe proposed an extended TDS algorithm whose optimality condition is less restricted than that of TDS algorithm, but the condition is very complex and is difficult to satisfy when the number of tasks is large. In this paper, we propose a new algorithm that can generate an optimal schedule,which attempts to merge tasks of parent clusters as little as possible in order to reduce the start time of task The propose algorithm not only has a simple and loose optimality condition, but has the same time complexity as TDS algorithm that is O(v2).