计算机工程 ›› 2008, Vol. 34 ›› Issue (4): 73-74.doi: 10.3969/j.issn.1000-3428.2008.04.025

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

基于排列树剪枝的经济网格任务调度模型

黄飞雪1,姜新娜2,李志洁3,侯铁珊1

  

  1. (1. 大连理工大学经济系,大连 116024;2. 大连理工大学软件学院,大连 116024;3. 大连理工大学计算机科学与工程系,大连 116024)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-02-20 发布日期:2008-02-20

Task Scheduling Model Based on Pruning of Permutation TreeEconomics Grid

HUANG Fei-xue1, JIANG Xin-na2, LI Zhi-jie3, HOU Tie-shan1   

  1. (1. Department of Economics, Dalian University of Technology, Dalian 116024; 2. School of Software, Dalian University of Technology, Dalian 116024; 3. Department of Computer Science and Engineering, Dalian University of Technology, Dalian 116024)
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-02-20 Published:2008-02-20

摘要: 针对如何在网格环境下快速进行独立任务调度的问题,提出了基于排列树剪枝的经济网格任务调度模型。该模型综合考虑了任务时间和费用,将网格中兼顾时间和费用的任务调度问题形式化为一个n层m叉排列树,将调度方案的选择转化为树的遍历,利用剪枝方法避免无效路径的搜索。通过实验评估了将解空间定义成排列树的算法性能,并与解空间定义成子集树的算法进行了比较。实验结果表明,该策略按照用户对时间截止期和费用约束的需求将任务指派到合适的计算机上运行,减少了搜索路径,在问题规模变大的情况下,该算法与子集树算法相比也具有较高的效率。

关键词: 任务调度决策, 网格计算, 排列树, 剪枝, 子集树

Abstract: In order to solve the issue of independent task scheduling in grid environment, a model of task scheduling based on permutation tree pruning is proposed. The method of model synthetically considers two factors: execution cost and execution time of independent tasks. The issue of task scheduling is formulated as an n-level m-ary permutation tree. Through traversing the permutation tree, a scheduling scheme is generated, and invalid path searching is avoided by using pruning method. The performance of the proposed algorithm and the subset tree algorithm are compared. Experimental results show that the permutation tree algorithm can allocate application tasks to appropriate CPU resources based on users’ requirements of headline and budget constraint. It outperforms subset tree algorithm in terms of scheduling efficiency in large scale. The conclusion indicates that model can provide a candidate of independent task scheduling in grid environment.

Key words: decision of task scheduling, grid computing, permutation tree, pruning, subset tree

中图分类号: