【摘要】 针对如何在网格环境下快速进行独立任务调度的问题,提出了基于排列树剪枝的经济网格任务调度模型。该模型综合考虑了任务时间和费用,将网格中兼顾时间和费用的任务调度问题形式化为一个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.更多还原