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

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