网格任务调度方法研究

Research on method of scheduling tasks in grid computing environment

网格计算中的关键问题之一是计算任务在各个资源之间的调度。提出了基于量子遗传算法(QGA)的网格任务调度算法,以减少调度时间为主要目标,增加资源利用率为次要目标。该算法采用量子比特间接编码的方式,通过有向无环图(DAG)来描述子任务间的依赖关系,根据深度值来给子任务的执行顺序进行排序。仿真结果显示,无论是任务完成时间还是资源利用率,此方法都明显优于基于遗传算法(GA)的网格调度算法。

One of the most important problems in grid computing is task scheduling between resources.This paper presents a scheduling algorithm based on quantum genetic algorithm,whose primary aim is to get the shortest makespan,and the secondary aim to improve the resources use factor.Indirect quantum bit coding method is adopted in this algorithm.It uses the DAG to define the relationship between subtasks,and ranks the subtasks according to the depth-value.Simulation demonstrates that the shortest makespan and resources use factor of this algorithm are better than those of scheduling algorithm based on simple genetic algorithm.