Abstract: Task scheduling is one of the most important issues to achieve high performance for multiprocessor systems.With the extensive studies of this issue，many new methods including Genetic Algorithms（GAs） have been introduced in this field.However，traditional GAs has two serious demerits，premature convergence and evolutional stagnation.To overcome those weaknesses，a novel GA，namely Multi-Population and Level Set based task scheduling algorithm（MPLS），had been developed for multiprocessor systems.MPLS employed the idea of multi-population coevolution to ensure the population diversity and introduced the concept of level set into task scheduling to speed up the iterative convergence.Based on the third-party benchmark，MPLS’ performance had been compared with other three GAs，including GTMS，MSGS and NGS.The comparative results show that MPLS can obtain much better schedule lengths than GTMS and MSGS，and slightly better than NGS.MPLS keeps the population diversity with the highest level of all the four GAs.Consequently，MPLS outperforms the others GAs in terms of schedule length and population diversity.

Key words: multi-population, level set, population diversity, Genetic Algorithm（GA）, task scheduling

摘要： 随着任务调度问题的广泛研究，包括遗传算法在内的许多新方法被引入到任务调度领域。然而，传统的遗传算法存在早熟收敛和后期进化停滞两个严重不足。为了克服这些不足，提出了算法MPLS。MPLS算法采用多种群共同进化的思想来维持种群多样性。同时，MPLS算法将水平集概念引入到任务调度研究中，以改进迭代收敛速度。基于第三方测试数据集，将MPLS的性能和GTMS、MSGS和NGS算法进行了对比。比较结果表明，MPLS算法获得的调度长度远好于GTMS、MSGS算法，略好于NGS算法。MPLS算法能将种群多样性维持在一个很高的水平。MPLS算法在调度长度和种群多样性方面要优于其它算法。

关键词: 多种群, 水平集, 种群多样性, 遗传算法, 任务调度