同构环境中Join任务图的一个调度算法

摘要

任务调度问题是一个NP完全问题.Join结构是一种并行处理的基本结构,虽然许多算法对Join任务图能产生最优调度,但大多都忽略了节省处理机个数和最小化程序总的完成时间等问题.因此,专门针对Join任务图,提出一个能产生最优调度的同构贪心调度算法,该算法具有高的加速比和总体效率,时间复杂度为O(v2),其中,v表示任务集中任务的个数.实验结果表明,相比其他算法,该算法具有较短的调度长度、较短的完成时间,使用的处理机数较少.