基于有向无环图网格独立任务调度算法  

Independent tasks scheduling algorithm of grid computing platforms on direct acyclic graph

作　　者：乔付[1,2] 张国印[1] 刘忠艳[2] 

机构地区：[1]哈尔滨工程大学计算机科学与技术学院,哈尔滨150001 [2]黑龙江科技学院计算机与信息工程学院,哈尔滨150027

出　　处：《计算机应用研究》2009年第6期2187-2189,2194,共4页Application Research of Computers

基　　金：黑龙江省自然科学基金资助项目(F2004-06)

摘　　要：提出了基于有向无环图多约束网格环境下独立任务的调度模型,为其建立多约束线性规划模型,通过求解模型节点的优先级,获得网格各计算节点最优任务调度数;然后基于多约束最优任务调度方案,提出多约束带宽优先启发式算法(MCOPBHATS)和多约束计算速度优先启发式算法(MCOPCHATS)。实验结果表明,在多约束异构的网格环境下实现大量独立任务调度时,MCOPBHATS和MCOPCHATS算法的性能优于基于多约束最优任务调度方案的M in-M in算法。This paper discussed the model of scheduling independent tasks on multi constraints based direct acyclic graph grid computing platforms. Presented Multi constraints linear programming model. Using the model, obtained priority of each computing node, then obtained the optimal number of tasks scheduled each computing node. With the multi constraints optimal scheduling scheme, proposed multi constraints optimization-based priority-bandwidth heuristic algorithm for task scheduling （MCOPBHATS） and multi constraints optimization-based priority-computation heuristic algorithm for task scheduling （ MCOPCHATS ）. The experimental results show that the proposed algorithms for the scheduling problem obtain better performance than Min-Min algorithms based on the multi constraints optimal scheduling scheme.

关 键 词：网格计算 任务调度 有向无环图 线性规划 启发式算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]