作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2008, Vol. 34 ›› Issue (11): 191-193. doi: 10.3969/j.issn.1000-3428.2008.11.069

• 人工智能及识别技术 • 上一篇    下一篇

基于动态遗传算法的网格计算任务调度

赵 政1,薛桂香1,宋建材2,孟 和1   

  1. (1. 天津大学计算机科学与技术学院,天津 300072;2. 天津航海仪器研究所,天津 300131)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-06-05 发布日期:2008-06-05

Task Scheduling for Grid Computing Based on Dynamic Genetic Algorithm

ZHAO Zheng1, XUE Gui-xiang1, SONG Jian-cai2, MENG He1   

  1. (1. School of Computer Science and Technology, Tianjin University, Tianjin 300072; 2. Tianjin Navigation Instrument Research Institution, Tianjin 300131)
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-06-05 Published:2008-06-05

摘要: 针对网格任务调度的动态特性,提出一种改进的遗传算法——动态遗传算法(DGA),设计了新的编码机制和适应度函数,以及相应的选择、交叉和变异算子。根据网格系统各服务节点的计算能力、负载及网络状态进行动态调度,不仅使总的完成时间最短,尽量使主机的空闲时间最短,同时满足每个任务的截止时间的要求。在OPNET环境中构建了一个局部网格仿真模型,对所提出的动态遗传算法进行了仿真实验,并与其他常见网格任务调度算法进行了对比,结果表明动态遗传算法具有很好的优化能力,提供了较好的服务质量。

关键词: 网格计算, 任务调度, 动态遗传算法, 建模, 仿真

Abstract: The paper presents a scheduling strategy which uses a Dynamic Genetic Algorithm(DGA) to schedule heterogeneous tasks onto heterogeneous hosts dynamically considering for the dynamic characteristic of grid in task scheduling. DGA develops a new coding system and fitness function for local grid computing, and a new operators of selection, crossover and mutation is designed. The DGA schedules tasks dynamically based on computer ability, traffic load of each server node and the state of the network at that time, which not only shortens the makespan and the idle time of the nodes, but also satisfies the deadline of each task. A local grid simulation model is constructed by OPNET. DGA algorithm is realized, and is compared with other grid task scheduling algorithms. The simulation results show that the DGA scheduling algorithm has good ability of optimization, and provides good quality of service.

Key words: grid computing, task scheduling, dynamic genetic algorithm, modeling, simulation

中图分类号: