基于任务复制的进化调度算法

Task Duplication Based Evolutionary Scheduling Algorithm

并行程序任务调度是NP完全问题.已有的进化调度算法不能很好利用任务复制这一重要手段.为此,利用染色体直接编码和间接编码的优点,并结合任务图的知识,使进化调度算法的搜索能力得到增强,同时染色体的解码过程也得到简化.通过与同类算法的性能比较,表明了本算法在调度问题中的有效性.

The problem of scheduling parallel program tasks on network of workstation is known to be NP-complete. It is difficult for the existing GA-based scheduling algorithms to handle task duplications. To overcome the weakness, a new evolutionary scheduling algorithm was proposed, which makes use of the merits of both direct chromosome encoding and indirect chromosome encoding, as well as the knowledge of task digraph. As a result, the searching ability of the algorithm is enhanced and the decoding process of chromosomes is simplified. The algorithm was compared with the same kind of scheduling algorithm in terms of makespan and running-time. The experimental results show the effectiveness of the algorithm to the scheduling problem.