论文部分内容阅读
网格计算自从上一世纪九十年代中期出现以来,逐渐被认为是支持广域并行和分布式计算的下一代主流计算平台,可以实现计算、信息、数据、存储、知识等资源的全面共享。网格工作流将工作流管理和网格计算结合起来,提供了一种分布式协作的工作流系统解决方案。目前情况来看,网格技术更注重于研究面向服务技术方面。在工作流执行过程中,服务质量(QoS)的应用,促使调度者根据服务质量来选择成员服务,这样网格中的资源可以更好地按照用户的需求来进行组织和分配。网格工作流调度侧重于研究广泛分布的资源及任务调度,直接影响着网格工作流执行的成功率及其效率,可以说是一个非常复杂且具有挑战性的问题。本文通过对网格工作流进行建模并改进其任务调度算法,来提高网格工作流的性能。诸如选择路由、并行路由等多种复杂情况存在于实际工作流中,基于DAG图简单直观的特点,本文选择DAG建模来表明网格工作流任务调度过程。网格工作流执行过程中的任务或者状态表示为DAG图的结点,任务之间的时序依赖关系表示为有向弧,而一些属性和参数则表示为弧上的权值。接下来为了解决网格工作流任务调度过程中多目标优化问题,本文提出了多QoS条件下网格工作流调度模型,定义了多维度的QoS参数标准体系结构,并对各个参数进行重新定义,重点分析了网格工作流环境下各种不同约束关系的结构中服务质量的计算方式。本文在基于遗传算法(GA)和粒子群算法(PSO)基础上,提出了遗传粒子群(GAPSO)混合算法,引用了特殊的适应度函数,在遗传算法部分设定了动态的交叉和变异概率,并提出了动态切换算法和终止算法的方法,同时也改进了粒子群算法中惯性权重的设置以及对粒子进行离散化。结合各自算法的优势,在算法运行初期利用遗传算法的全局搜索能力进行优化搜索,在后期利用粒子群算法快速收敛能力提高算法的运行速度。本文通过MATLAB工具进行仿真,共设计了三组实验。首先为了减少参数的取值对算法性能带来的误差,选取不同的混合算法切换系数S,根据它们在相同的初始种群数量范围内末代种群平均适应度值变化情况,来选择最优的S值;然后在一个具体的工作流实例中求解满足服务质量的最优解,证明通过改进的GAPSO混合调度算法求解的最优解满足该工作流实例中不同用户对服务质量的要求,符合计算网格工作流中的复杂环境;最后比较了应用于网格工作流任务优化调度的改进的GAPSO算法和其它调度算法在不同服务个数情况下,寻找到最优解时算法的执行时间,证明了混合算法的优越性。实验结果表明本文提出的改进的GAPSO混合算法在网格工作流调度方面具有更高的效率,能更有效地解决网格工作流调度问题。