东北大学学报（自然科学版）

东北大学学报(自然科学版) ›› 2007, Vol. 28 ›› Issue (7): 973-977.DOI: -

• 论著 • 上一篇    下一篇

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

马学彬;温涛;郭权;王刚;   

  1. 东北大学软件中心;东北大学软件中心;东软信息学院计算机科学技术系;东北大学软件中心 辽宁沈阳110004;辽宁沈阳110004;辽宁大连116023;辽宁沈阳110004
  • 收稿日期:2013-06-24 修回日期:2013-06-24 出版日期:2007-07-15 发布日期:2013-06-24
  • 通讯作者: Ma, X.-B.
  • 作者简介:-
  • 基金资助:
    国家高技术研究发展计划项目(2002AA113020)

GA-based algorithm for task scheduling on computational grid

Ma, Xue-Bin (1); Wen, Tao (1); Guo, Quan (2); Wang, Gang (1)   

  1. (1) Software Center, Northeastern University, Shenyang 110004, China; (2) Department of Computer Science and Technology, Neusoft Institute of Information, Dalian 116023, China
  • Received:2013-06-24 Revised:2013-06-24 Online:2007-07-15 Published:2013-06-24
  • Contact: Ma, X.-B.
  • About author:-
  • Supported by:
    -

RichHTML

1

PDF (PC)

1012

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

关键词: 资源调度, 网格计算, 遗传算法, DAG图, NP问题

Abstract: 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. A comparison test showed that the genetic algorithm proposed is better than conventional HEFT and DLS algorithms during task scheduling on computational grid.

中图分类号: