一个调度Out-Tree任务图的启发式算法

Heuristic algorithm for scheduling Out-Tree task graphs

任务调度问题是并行分布式计算中的挑战性问题之一。大多数实际的调度算法是启发式的因而常常具有改进的余地。针对Out-Tree任务图这一基本结构提出一个基于任务复制的启发式调度算法,该算法在确保最短调度长度的同时,注重处理器的负载平衡,以达到节约处理器的目的。比较性实验的结果表明,该算法确保了最短调度长度且使用的处理器最少。因而,该算法提高了系统的利用率,避免消耗过多的资源,实际应用性更好。

Task scheduling is one of the challenging problems in parallel and distributed computing systems. Most realistic scheduling algorithms are heuristic and heuristic algorithms often have room for improvement. This paper proposes a task dupli- cation based heuristic scheduling algorithm for Out-Tree task graphs, which guarantees the shortest schedule length and takes load balances into account to economize the used processors. From comparative experimental results, the proposed scheduling algorithm can produce better schedule which has the shortest schedule length and uses the least number of processors. It can improve the system utilization, avoid the redundant resource consumption, and then more applicable in real world.