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

摘要： 工作流作业的调度效率是评价工作流管理系统整体表现的重要指标。众所周知，工作流作业的调度问题是一个NP-hard问题，而异构的计算环境使得问题更加棘手。分层基因算法LGA将启发式算法与GA算法相结合，利用GA算法来优化经过正向分层之后的工作流作业调度队列，显著地减少了工作流作业的执行时间。该算法根据作业的分层优先级来产生作业队列，把队列中的同层作业从整体上看作是一位基因来处理，有效地对算法的进化方向进行规划，并通过对杂交和变异流程的改进，增强算法的搜索深度和广度。实验表明，相比于其他混合GA算法，经LGA算法优化之后的工作流作业调度队列，所需的执行时间更少。

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