异构系统中DAG任务调度的双螺旋结构遗传算法

摘要：

　　任务调度问题是一个NP完全问题,基于启发式的方法通常被用来求解次优解,其性能在很大程度上依赖启发的成效,在复杂问题时可能会产生不理想的结果.鉴此,根据DNA 双螺旋结构模型,提出了一种异构计算系统中DAG 任务调度的双螺旋结构遗传算法(DHSGA),DHSGA 算法将GA 算法和启发式方法有机的结合,首先针对DAG 任务图的数据依赖关系,采用启发式方法,控制GA算法的交叉与变异操作合理改变一个染色体主链结构,以产生较佳的任务调度优先队列；然后模仿碱基互补配对原则,利用启发式HEFT 算法实现从一个染色体主链(任务集)到另一个染色体主链(异构处理机集)的映射,以提高算法的有效性和收敛速度.随机DAG 任务图和真实问题DAG 任务图的仿真实验表明,所提出的DHSGA 算法在makespan 性能上明显优于启发式HEFT 算法,makespan平均减少10.1％.

关键词： 异构计算系统 任务调度 遗传算法 加权有向无环图

作者: XU Yu-Ming 徐雨明 LI Lang 李浪 OYANG Ai-Jia 欧阳艾嘉 WU Fan 吴帆

作者单位: College of Information Science and Engineering,Hunan University,Changsha,410082,China;Department of 湖南大学 信息科学与工程学院,长沙 410082 College of Information Science and Engineering,Hunan University,Changsha,410082,China

会议类型: 国内会议

会议名称: 2012全国高性能计算学术年会

会议地点: 张家界

会议语种:中文

页码: 1-10

在线出版日期: 2012-10-29（万方平台首次上网日期，不代表论文的发表时间）