计算机工程 ›› 2010, Vol. 36 ›› Issue (3): 31-33.doi: 10.3969/j.issn.1000-3428.2010.03.011

• 软件技术与数据库 • 上一篇    下一篇

网格工作流的动态贪心调度算法

邓定兰1,于 炯1,2,谭亚丽 ,吕良干   

  1. (1. 新疆大学信息科学与工程学院,乌鲁木齐 830046;2. 北京理工大学计算机学院,北京 100081)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-02-05 发布日期:2010-02-05

Dynamic-Greedy Schedule Algorithm for Grid Workflow

DENG Ding-lan , YU Jiong1,2, TAN Ya-li , LV Liang-gan   

  1. (1. School of Information Science and Engineering, Xinjiang University, Urumqi 830046;
    2. School of Computer Science and Technology, Beijing Institute of Technology, Beijing 100081)
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-02-05 Published:2010-02-05

摘要: 有向无环图描述的工作流时间费用优化问题是计算网格中的基本难题之一。针对该问题提出一种网格工作流的动态贪心调度算法(DGS-GW)。按用户提交的截止时间和偏好因子建立数学模型,利用DGS-GW求解该模型的次优解。实验结果证明了该算法的有效性。

关键词: 网格工作流, 任务调度, 偏好因子

Abstract: Optimization problem of workflow time-cost described by Directed Acyclic Graph(DAG) is a fundamental intractable problem in computational grid. Aiming at this problem, this paper proposes a Dynamic-Greedy Schedule algorithm for Grid Workflow(DGS-GW). According to the deadline and preference factor submitted by users, it establishes a mathematical model and uses DGS-GW to solve it. Experimental results show that the algorithm is effective.

Key words: grid workflow, task schedule, preference factor

中图分类号: