基于动态任务优先级的网格任务调度算法研究

摘要

Task scheduling is a NP-complete problem in the grid environment.To ensure that the task most significantly affects the makespan can be scheduled in each scheduling step,the task scheduling algorithm by using dynamic task priority is proposed.The critical path of directed acyclic graph（DAG） is dynamically determined and the idle time slots of nodes are effectively utilized to replicate task for reducing the communication overhead and shortening the overall execution time.Extensive experiments are carried out and the research results show that the proposed algorithm outperforms the HEFT algorithm and the DDS algorithm in execution time.%网格环境下的任务调度是一个NP完全问题.为了确保每一步都能优先调度影响调度长度最大的就绪任务,提出一种采用动态任务优先级策略的任务调度算法.在进行任务调度的过程中,通过动态计算任务图DAG的关键路径并有效地利用处理器的空闲时间段来复制任务,使任务节点之间的通信开销尽可能降低,进而缩短整个任务图的完成时间.大量的模拟实验结果表明,所提的算法在任务完成时间上明显优于HEFT算法和DDS算法.