一种基于遗传算法的网格任务调度算法  

Grid Task Scheduling with an Improved Genetic Algorithm

作　　者：肖青[1] 杨长兴[1] 杨炼[1] 

机构地区：[1]中南大学信息科学与工程学院,湖南长沙410083

出　　处：《计算机技术与发展》2008年第8期32-34,38,共4页Computer Technology and Development

基　　金：湖南省自然科学基金项目(06JJ5131);湖南省教育厅科研资助项目(07C388)

摘　　要：任务调度算法是网格计算研究的一个重要方向,已被证明是一个NP完全问题。提出了一种新的网格任务调度算法。该算法基于遗传算法,为加快算法的收敛速度,在生成初始种群时优先分配关键路径上的任务;由于资源间存在着通信延迟,引入任务复制方法,并结合遗传操作控制任务复制的深度,可以减少任务之间的通信开销,缩短整个调度的完成时间;最后进行优化操作,减少冗余的任务复制。模拟实验结果表明,该算法在收敛速度和调度完成时间均优于普通遗传算法。Task scheduling is an important research aim in grid computing research area, and it has been proven to be NP-complete. Presents a new grid task scheduling algorithm. The scheduling algorithm based on genetic algorithm. For improving the convergence rate, preferentially assign tasks of the critical path to resources when generating initial populations. Because of the communication delays between resources, import task duplication method and incorporate new genetic operators to control the degree of replication of tasks, which can reduce task communication delays and shorten the length of schedules. At last, use optimal operator to reduce large task replication numbers. The algorithm was compared with common genetic scheduling algorithm in terms of convergence rate and complete time. The experimental results show the effectiveness of the proposed algorithm to the scheduling problem.

关 键 词：网格任务调度 遗传算法 关键路径 任务复制 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]