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

摘要：

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

关键词：NP完全问题、遗传算法、双螺旋结构、DAG任务调度、调度长度

所属期刊栏目：51

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金重点项目61133005;国家自然科学基金项目61370095,90715029,61070057,60603053,61103047;国家科技支撑计划基金项目2012BAH09B02;湖南省杰出青年基金项目12JJ1011;湖南省科技厅计划项目2013GK3082;湖南省自然科学基金项目13JJ3047

在线出版日期：2014-08-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共13页

页码：1240-1252