基于遗传算法的网格任务调度方法研究

Research of Grid Task Scheduling Strategy Based on Genetic Algorithm

网格任务调度是典型的NP完全问题,因此如何快速地找到全局最优解是网格任务调度的难点所在。而遗传算法在解优化问题上具有快速性和健壮性,因而遗传算法是解决复杂的非线性问题,特别是复杂环境下的资源调度的有效方法。文中先对网格任务调度进行建模,把资源分配抽象成染色体上的等位基因,然后采用遗传算法对生成的染色体进行杂交、变异进化模拟,并且利用相对适应度以及精英选择来提高算法的收敛性。仿真结果表明,该改进算法能更有效地解决网格任务调度问题。

Grid task scheduling strategy is a typical NP complete problem,so the difficulty of grid task scheduling strategy is how to find the optimal solution in overall situation.While genetic algorithm has the speediness and robust trait on the optimum problem,therefore genetic algorithm is an effective method on solving the complex nonlinear problem,particularly on resource scheduling in complex environment.In this paper,firstly create the grid task scheduling model,Abstract distribution of the resource to allele on the chromosome,and then use genetic algorithm to simulate hybridization and mutation evolution of the generated chromosome,utilize comparative fitness and elite selection to improve degree of convergence of the algorithm.The simulation results show that this improved algorithm can solve the problem of grid task scheduling more effectively.