中文摘要：

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

英文摘要：

The task scheduling problem is known to be an NP-complete problem and the heuristicbased optimization approaches have been proposed to obtain suboptimal solutions.But they are not likely to produce consistent results on a wide range of problems.In this paper,by the DNA doublehelix structure inspired,a double-helix structure genetic algorithm （DHSGA） for task scheduling on heterogeneous computing systems is proposed.Its basic idea is to exploit the advantages of heuristicbased algorithms while avoiding their drawbacks.According to the data dependencies of a DAG task graph,the heuristic approach is used to control the crossover and mutation operations of GA algorithm in order to change the main chain structure of a chromosome reasonably,thus the DHSGA generates a better task scheduling priority queue.Then imitating the complementary based on a pairing principle,the heuristic HEFT algorithm improves the effectiveness and convergent speed by mapping from the chromosomal chain （task set） to another chromosome chain （processor set）.The software simulation results show that the proposed DHSGA significantly improves the makespan on distributed heterogeneous computing systems,over a large set of randomly generated graphs as well as graphs for real-world problems with various characteristics,compared with the list scheduling algorithms.The average makespan reduction is about 10.1％.