对等网络环境下多目标约束的并行任务调度策略研究

Parallel task scheduling strategy with multi-objective constraints in P2P

对等网络环境的特点决定了其任务调度性能是受多个因素制约的。鉴于任务执行时间、节点间的通信时间和任务调度费用等因素,提出了多目标约束的并行任务调度策略。首先给出了多目标任务调度的数学模型,利用任务需求与节点性能之间的关系来定义各目标的需求关系矩阵;然后利用隶属度函数将各个关系矩阵转化为模糊矩阵,并根据每个目标对最终目标的不同影响来确定各目标在最终决策中所占的比率,从而将多目标转化为单目标任务调度模型,在此基础上利用匈牙利算法对n个任务m个节点的最优分配问题进行求解。实验结果表明,基于多目标约束的任务调度模型较传统的方法更能优化任务调度的性能。

Task scheduling performance of the Peer to Peer （P2P） network was influenced by many factors. Consid- ering execution time, communication time among nodes and task scheduling costs, a parallel task scheduling algorithm with multi-objective constraints was presented. Mathematical model of multi-objective task scheduling was firstly proposed which determined the requirement relationship matrix for each objective by using the relationship between the task requirement and the nodes performance. Then all the relationship matrices were transformed into fuzzy matrix by membership functions. Proportions determined by the different effect on the final decision for each objective were applied to convert multi-objective task scheduling problem to single-objective problem. Meanwhile Hungary algorithm was adopted to solve best distribution on n tasks and rn nodes. Experimental results demonstrated that the task scheduling algorithm with multi--objective constraints had better performances than the traditional methods.