异构计算系统中独立任务调度的混合遗传算法

有效的任务调度是异构计算系统获取高性能的关键因素之一,由于任务调度问题是NP-困难的,为了获取尽可能好的解,文献中存在许多启发式调度算法.针对异构计算系统的独立任务调度问题,基于遗传算法和最小完成时间算法MCT(Minimum Completion Time),提出一种新的混合遗传算法,它采用遗传算法来进化任务调度的优先队列,然后再使用MCT算法把优先队列解码为一个有效的调度,与文献中其它算法进行比较表明,它不但能产生更好的调度结果,而且有很好的收敛速度. 

Hybrid genetic algorithm for independent tasks scheduling in heterogeneous computing systems

Efficient tasks scheduling is critical for achieving high performance in heterogeneous computing systems. The tasks scheduling problem is NP-hard in general. In order to obtain better solutions, many scheduling heuristics were presented in the literature. Based on genetic algorithm and MCT(minimum completion time) algorithm, a new hybrid genetic algorithm was presented for independent tasks scheduling in heterogeneous computing systems. Genetic algorithm was used to evolve a priority queue first, and then the priority queue was mapped to a schedule using MCT algorithm. The simulation results comparing with other scheduling algorithm show that it produces better results in terms of schedule length, and it has good convergent speed.