基于pso算法的网格任务调度策略

《基于pso算法的网格任务调度策略》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据第29卷第2期辽宁工程技术大学学报(自然科学版)2010年4月v01．29No．2JournalofLiaoningTechnicalUniversity(NaturalScience)Apr．2010文章编号：1008—0562(2010)02．0274．04基于PSO算法的网格任务调度策略迟玉红L2，白鹏2，于俊发2，喻春明2(1．清华大学计算机科学与技术系，北京100084：2．中国人民解放军65053部队，辽宁大连l16113)摘要：为了合理地协调和分配网格资源，降低网格任务完成时间，有效保持网格资源负载平衡，通过分析网格任务调度的关键问题和PSO

2、算法的优化原理，建立了网格任务调度的元任务模型和性能指标的数学模型，确定了粒子编码和解码方式，提出了一种基于局部模型PSO算法的网格任务调度策略，并在PSO算法处理粒子边界问题时，采用了“圆桌运动”的新方法。仿真实验结果表明，算法可行有效，并且改善了PSO算法易陷入局部最优的问题。关键词：网格；任务调度；元任务；PSO算法；局部模型中图分类号TPl8；TP393文献标识码：ATaskschedulingingridbasedonPSOalgorithmCHIYuhon91。，BAIPeng‘，YUJunf．a‘·YUChunmingZ(1．Departmentof

3、ComputerScienceandTechnology，TsinghuaUniversity，Beijing100084,Chinas2．Unit65053，PLA，Dalian116113,China)Abstract：Itisachallengetofindtheoptimalsolutionwhichcanrationallycoordinateandallocatetheresourcesingridsystem，greatlyreducethecompletiontime，efficientlybalanceworkloadandimprovegrid

4、performance．ThispaperinvestigatesthekeyissuesoftaskschedulingandtheprincipleofPSOalgorithm，developsthemodelofmetataskin鲥dsystemandthemodelofperformancemetricsoftaskscheduling．Alsothepaperhasdevelopedanewmethodforcodingandencodingofparticles，andproposedataskschedulingschemebasedOilPSOa

5、lgorithmusinglocalbestmodel．Togivetheboundaryconditions，thepaperproposesanewmethodcalled‘'round-tablemoving”．Theexperimentalresultsshowthattheproposedapproachconlributestooverallgrid10adbalancing，significantlyimprovesthe舒dapplicationexecutionperformanceandresourceutilization，andavoids

6、thePSO’S‘'premature”problem．Keywords：grid；taskscheduling；metatask；PSOalgorithm；localbestmodel引言由于网格环境的动态性、异构性等特点，以及网格资源在任务执行过程中的状态难以预测，从而使得网格任务调度问题异常复杂。近年来，已引起许多学者的关注，并取得一定的研究成剿卜4J。GA算法是解决网格任务调度问题常用且有效的启发式算法15】。但与PSO算法相比，前者开销较大，执行时间较长，而后者搜索速度快，运算简单，更加有效率【6】，且PSO算法的局部模型较全局模型有更好的收敛性和健壮性

7、171。基于以上问题研究，本文提出基于局部模型PSO算法网格任务调度策略，并在处理粒子越界问题时，采用“圆桌运动”方法，改善了PSO算法易陷入局部最优问题，有效提高网格任务调度的性能。1网格任务调度问题优化模型1．1任务模型的确定由于现有的网络环境对任务调度的整体影响是不能忽略的。因此，本文所调度的任务之间虽然彼此独立，但不排除任务内部存在依赖关系，即子任务(SubTask)tsl。由这样若干可一次调度，任务内部具有依赖关系，而彼此之间相互独立的任务组成的集合，本文将其称为元任务(MetaTask)。如图1，元任务MetaTask是由乃，乃，⋯，珀共日个相互独立的

8、任务组成。