基于量子粒子群优化的DAG并行任务调度研究  

Research on DAG parallel task scheduling problem based on quantum-behaved particle swarm optimization

作　　者：张聪[1] 沈惠璋[1] 

机构地区：[1]上海交通大学安泰经济与管理学院,上海200052

出　　处：《计算机应用研究》2010年第7期2458-2461,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(70671070);高等学校博士学科点专项科研基金资助项目(20070248054)

摘　　要：任务调度是网络并行计算系统的核心问题之一。在有向无环图(DAG)描述问题的基础上,提出了一种进行并行任务调度的量子粒子群优化算法。首先对DAG并行任务调度问题作出定义,并给出了优化问题的目标;然后分别讨论了问题的编码表示、解码方案、位置向量的计算方法、离散问题连续化、算法的总体流程等;最后给出算法的仿真实验情况及分析,实验结果表明,该算法有良好的全局寻优性能和快捷的收敛速度,调度效果优于遗传算法和粒子群优化算法。Task scheduling is one of the important problems in parallel computing system.This paper proposed a quantum-behaved particle swarm optimization algorithm for task scheduling based on directed acyclic graph.First redefined the parallel task scheduling problem and its aim.Then discussed the representation of the encoding,the procedure of the decoding,the computational method of position vector,the continuative of the discrete problem and the structure of the algorithm respectively.In the end,presented the algorithm simulation,experiment result analysis and the conclusions.The simulation results show that this algorithm has better global optimizing ability and more rapid convergence,and it is superior to genetic algorithm and particle swarm optimization algorithm.

关 键 词：任务调度 量子粒子群优化 有向无环图 

分 类 号：TP314[自动化与计算机技术—计算机软件与理论]