异构计算系统任务调度的遗传算法及改进

提出一种新的染色体编码方法——逆排序消出结点法RSEEN,确保染色体对应的任务分配调度为合理调度,不必在遗传操作过程中不断地验证和调整基因以保证染色体的有效性,简化了遗传操作,使优良基因更易保全并传递给后代,种群的进化过程更接近自然的进化法则。另外,还采用了启发式变异方法,加速了算法的收敛性。同时,构造本算法是以异构计算系统模型为基础的,充分考虑了任务间数据交换的开销和处理机间的差异,算法的应用更有普遍意义。

Genetic Algorithm of Task Scheduling in HCS and Improvement

A novel chromosome encode method--Reverse Sequence Exclude Exit Node was put forward, RSEEN encode method can make the corresponding task assignment and scheduling of chromosome reasonable which can avoid repeated verification and adjustment of gene to guarantee validity of chromosome in genetic operation while the predigest genetic operation processes and keeps the excellent gene passing to offspring to a large degree. Therefore the population evolution process is close to nature evolution law, At the same time, aheuristic mutation method was adopted to speed up algorithm convergence, In addition, the foundation of the improved genetic algorithm is heterogeneous computing system model and takes data transmission overhead among the tasks and speed diversity of different processor into the careful consideration that expands application spectrum of the algorithm generally.