一种基于遗传算法的网格任务调度算法

GA-Based Algorithm for Task Scheduling on Computational Grid

任务调度问题是一类NP问题,经典调度理论一般仅能获得问题的近似最优解.尽管已有用于任务调度的遗传算法的求解质量优于传统方法,但多数是考虑单任务或独立多任务调度的遗传算法.采用理论分析与仿真实验相结合的方法,提出了一种改进的遗传算法解决网格的任务调度问题.这种遗传算法所处理的任务不仅可以包含多个有前后约束关系的子任务,并且每个子任务可以需要多种资源.通过对比实验可以看到本文所提出的算法在网格任务调度方面要优于传统的HEFT和DLS算法.

Task scheduling plays an important role in grid system and has a notable impact on the overall performance. Scheduling problems, as a class of NP （non-deterministic polynomial ） problems can get a near optimal solution by classical scheduling approaches in most cases. Although the existing methods of task scheduling based on GA（genetic algorithms） can give better solutions to task scheduling than classical approaches, most of them are used for single task or multiple tasks which are independent on each other. An improved GA is thus proposed for task scheduling on computational grid by combining theoretical analysis with simulation results. What tasks the genetic algorithm deal with may involve many subtasks with contextual constraints and every subtask may require several kinds of resources. algorithm proposed is better than conventional HEFT A comparison test showed that the genetic and DLS algorithms during task scheduling on computational grid.