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

摘要

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