关键词: 作业调度, 完成时间, 正向分层, 遗传算法

Abstract: Efficiency of workflow scheduling is an important evaluation index of the performance of workflow management system. Workflow scheduling problem is a well-known NP-hard problem and heterogeneous computing environment makes it more challenging. The Layered Genetic Algorithm（LGA） combines the heuristic algorithm with genetic algorithm, and uses genetic algorithm to optimize workflow scheduling queues after positive layering, which significantly reduces the makespan of workflow. The LGA generates the task queue according to hierarchical priority, and treats sub-tasks in the same layer as one gene in the course of evolution. Through the improvement of crossover and mutation process, the LGA plans a direction of the evolution and enhances the search depth and breadth of the algorithm. The experimental results show that compared with other hybrid genetic algorithms, workflow scheduling consumes less makespan after optimization of the LGA.

Key words: workflow scheduling, makespan, positive layering, Genetic Algorithm