基于改进遗传算法的网格任务调度

On grid task scheduling based on modified genetic algorithm

为在网格环境下完成任务调度,使服务运行时间和费用2个指标达到最优化,将这2个指标作为网格任务调度模型的衡量指标,将计算经济模型引入网格资源管理,改进了遗传算法。算法中的染色体编码采用间接编码方式,对每个任务占用的资源编码,即实数编码方法。生成初始种群时采用随机生成种群和根据某些先验知识生成种群这2种方法相结合,变异操作时根据原来染色体的适应值和适应度函数进行有目的的随机变异。通过网格仿真平台GridSim对该算法进行模拟验证,并将其与简单遗传算法及GridSim中经济模型下时间最优算法DBC_Time比较,试验结果证明,其能较好完成网格环境下任务的调度,实现时间和费用双目标优化。

To obtain the optimization in cost and time together in task scheduling on Grid environment,the cost and time factors were taken into account as measurement index in grid task scheduling model,and the computational economy model was introduced into grid resource management.Then a modified genetic algorithm was proposed.In the algorithm,chromosome coding was optimized with indirect coding that resource of each task was initialized through real number coding.Original population was generated via stochastic method together with priori knowledge,and purposeful mutation operation was implemented according to fitness value of old chromosome and fitness function.Finally,the algorithm was compared with simple genetic algorithm and DBC（Deadline and Budget Constrained） time optimization scheduling algorithm by simulating in GridSim,a grid simulation platform.It is proved that the modified genetic algorithm can complete the task scheduling in grid environment effectively,achieving the objective of optimizing scheduling time and running cost.