基于遗传算法的网格资源调度算法

Scheduling in Grid Computing Environment Based on Genetic Algorithm

网格将多种资源组织在一个统一的框架下 ,为各种复杂的计算任务提供资源 因此计算任务在各种资源之间的调度成为了一个关键的问题 简述了在异构资源之间调度任务的重要性 ,提出了一种基于遗传算法的任务调度算法 该算法采用资源 -任务的间接编码方式 ,通过DAG图获取子任务的层次关系 ,并将子任务按照层次深度排序 ,解决了种群中的非法问题 在单一资源上采用短任务优先和父节点优先两个原则来安排子任务的执行次序 。

Grid computing is a new computing-framework to meet the growing computational demands.Computational grids provide mechanisms for sharing and accessing large and heterogeneous collections of remote resources.However, how to schedule the subtasks in these heterogeneous resources is a critical problem.In this paper, a scheduling-algorithm based on genetic algorithm (GA) is addressed.The chromosome coding method and the operator of genetic algorithm are discussed in detail.The relationship between subtasks can be obtained through the DAG, and then the subtasks are ranked according to their depth-value, which can avoid the emergence of invalidate chromosomes.In the single resource, two principles are adopted to determine the sequence of the subtasks: one is the short-subtask prior; the other is parent-subtask prior.