基于dag图解-重构的机群系统静态调度算法

机群系统静态任务调度是np-完全问题,通常的算法是通过一些启发式算法得到多项式次优解.该文提出的图解-子图重构算法实现了对分布在有向无环图(directedacyclicgraph,简称dag)上的并行任务的快速有效调度.该算法的复杂性为o(log|v|×(|v|+|e|)),采用递归方法实现了对任务图的有效分解和子图重构,生成任务群,完成任务调度,并且初步实现了对处理机的优化.通过实例分析以及与其他启发式调度算法的性能比较,证明该算法是一种快速、有效、可