基于微粒群算法的网格工作流优化调度问题的研究

论文摘要

网格环境使工作流流程需要跨组织执行,从而使传统的工作流技术在网格中应用面临着许多问题,尤其是网格工作流的调度问题,它影响着网格工作流执行成功与否及效率的高低。同时,很多工作流活动需要人的参与,而人不能一年365天,一天24小时不问断地工作（运行）。因此,在全球化协作环境下,网格工作流优化调度必须考虑这种跨组织、跨地域引起的跨时区,跨时间工作体制,跨时间粒度等多种与时间相关的因素,以进一步实现执行优化。针对上述问题,本文对具有时序和因果约束关系的网格工作流优化调度问题进行了研究。为网格工作流调度问题建立了目标模型,并分别从跨时间粒度,跨时区,跨时间工作体制方面对网格工作流调度模型进行了讨论分析。然后在满足目标模型表达式的基础上,使用微粒群算法为网格工作流的调度找到最优的执行路径（在本文中就是最佳站点组合）。其研究的内容主要包括:1)建立了具有时序和约束关系的网格工作流调度问题的目标模型,解决了网格工作流中由于任务调度流程的多样性和复杂性而在进行任务调度分析的过程中很难得出一个统一的模型表示形式的问题;2)分别从跨时区,跨时间工作体制,跨时间粒度,不同节假日设置等方面依次对目标模型进行了讨论分析,并对不同情况下的目标模型表达式进行了进一步的修改;3)根据目标模型,选择最新群体智能算法-微粒群算法进行网格工作流的优化调度。并根据问题的需要,对微粒群算法进行了一定的改进,在此基础上进行了基于改进微粒群算法的网格工作流优化调度的设计;4)针对不同的网格工作流实例,使用MATLAB 7.0进行了仿真实验和分析。验证了改进的微粒群算法应用于网格工作流中任务的优化调度比其他应用网格工作流调度的算法具有更短的执行时间,说明了基于微粒群算法的网格工作流调度具有更高的效率,更好的优越性。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 问题的提出
• 1.2 国内外研究现状分析
• 1.2.1 网格工作流研究现状
• 1.2.2 网格工作流调度的研究现状
• 1.3 本文的研究工作及意义
• 1.3.1 本文的主要工作
• 1.3.2 研究的意义
• 1.4 论文结构
• 第二章 相关文献综述
• 2.1 工作流技术
• 2.1.1 工作流定义
• 2.1.2 工作流相关概念
• 2.1.3 工作流模型的有向图表示
• 2.2 网格
• 2.2.1 网格概念
• 2.2.2 网格资源特点
• 2.2.3 网格任务调度策略
• 2.3 网格工作流概述
• 2.3.1 网格工作流与传统工作流的区别
• 2.3.2 网格工作流的执行过程
• 2.3.3 网格工作流研究的关键问题
• 2.4 微粒群算法
• 2.4.1 微粒群算法基本原理
• 2.4.2 算法流程
• 2.4.3 算法的伪代码
• 2.4.4 PSO算法参数分析
• 2.4.5 全局模式与临域模式
• 2.4.6 与其他进化算法的比较
• 2.5 本章小结
• 第三章 网格工作流调度模型
• 3.1 网格工作流调度问题
• 3.1.1 调度的衡量指标
• 3.1.2 网格工作流调度过程
• 3.2 调度模型存在的基本环境
• 3.3 网格工作流调度问题的目标模型
• 3.3.1 网格工作流调度中多时间粒度问题的解决
• 3.3.2 网格工作流调度中时区差异问题的解决
• 3.3.3 网格工作流调度中时间工作体制差异问题的解决
• 3.4 本章小结
• 第四章 基于PSO算法的网格工作流优化调度问题的设计
• 4.1 网格工作流调度问题中粒子位置向量的表示
• 4.2 适应度函数的确定
• 4.3 个罚函数法处理约束
• 4.4 应用于网格工作流调度问题的改进微粒群算法
• 4.5 算法描述
• 4.6 本章小结
• 第五章 仿真试验与结果分析
• 5.1 仿真环境
• 5.2 仿真实验及分析
• 5.3 本章小结
• 第六章 总结与展望
• 6.1 总结
• 6.2 展望
• 参考文献
• 致谢
• 附录A 攻读学位期间发表论文目录
• 附录B 攻读学位期间参与研究项目