面向多核任务调度的混合遗传算法

Modified hybrid genetic algorithm for parallel task scheduling of multiprocessors

多核处理器的并行任务调度一直是研究的热点话题,属于NP-hard问题。针对此问题,本文提出了一种集启发式算法、禁忌搜索算法、模拟退火算法于一体的改进混合遗传算法(modified hybrid genetic algorithm,MHGA)。MHGA改进如下:首先,采用启发式的分层调度来初始化种群,提高初始种群质量;其次,提出基于禁忌搜索(tabu search,TS)的随机编号交叉算子,提高种群的多样性;最后,采用基于模拟退火(simulated annealing,SA)的变异,提高个体质量。实验结果表明,与其他遗传算法(genetic algorithm,GA)相比,MHGA可以得到更小的任务调度时间和更快的最优解搜索能力。

Parallel task scheduling of multiprocessors is a hot research topic, and also is a well known NP- hard problem. Focusing on this problem, a modified hybrid genetic algorithm （MHGA） is proposed, in which the heuristic algorithm, tabu search （TS） algorithm and simulated annealing （SA） algorithm are integrated. The modifications of the MHGA include： using the hierarchical scheduling based heuristic method to initialize the population so as to improve the quality of initial population~ employing the TS based random number cross over to enhance the diversity of the population; adopting the SA based mutation to improve the quality of the in dividual. Experimental results show that the MHGA can obtain smaller task scheduling time and have ability to fast search better solution in comparison with other GAs.