基于改进PSO算法的网格任务调度算法

论文摘要

网格是当今分布式计算研究领域最为活跃的部分,它以虚拟组织VO(Virtual Organization)的形式灵活、有效地将不同管理域的异构资源组织起来,协同完成大型计算任务。任务调度是网格的重要组成部分,直接影响网格的性能。针对任务的个性化需求,如何有效地将任务合理地分配到计算资源上去,这是任务调度的主要内容。同时网格具有的动态性、异构性和分布性等特征,使得网格环境下的任务调度问题变得尤为复杂,已成为当前网格研究的热点,也被证明是个NP完全问题。因此,找到一个好的任务调度策略,尽可能缩短任务的总执行时间、有效均衡系统资源负载,具有非常重要的意义。近年来,兴起将启发式算法应用于任务调度,取得了较好的研究成果。作为一种比较新颖的启发式方法,粒子群优化算法PSO搜索速度快、操作简单、效率高,能有效求解NP完全问题,被广泛应用于任务调度中。有仿真结果表明：在任务调度中,PSO算法与其他启发式算法相比更具优越性。但是PSO算法固有的一些缺陷,使得算法在问题求解时易陷入局部极值、搜索精度不高。针对PSO算法的不足,本文对时间QoS约束下独立任务的调度问题进行研究,提出了一种基于改进PSO算法的网格任务调度算法MCPSO (An improved PSO of grid scheduling algorithm under the meta task)。该算法的主要思想是：首先采用混沌序列初始化大量粒子,并在产生的粒子中择优选出初始种群；然后在粒子更新时,引入混沌搜索,随机产生若干混沌序列并把最优混沌序列得到的位置和当前粒子最优位置比较。如果优于当前粒子,则更新当前粒子的最优位置,引导当前粒子跳出局部最优点,快速寻找最优解。实验表明,该算法改善了PSO算法易陷入局部最优问题,同时兼顾更好的时间跨度makespan和负载均衡,有效提高网格的性能。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究现状
• 1.2.1 网格任务调度的研究现状
• 1.2.2 粒子群优化算法及其在网格任务调度中的研究现状
• 1.2.3 研究意义
• 1.3 研究内容
• 1.4 论文结构
• 第二章 网格任务调度概述
• 2.1 网格任务调度
• 2.1.1 网格任务调度过程
• 2.1.2 网格任务调度目标
• 2.2 网格任务调度算法
• 2.2.1 常见启发式调度算法
• 2.2.2 常用启发式算法性能比较
• 2.3 网格任务调度模型
• 2.3.1 调度模型
• 2.3.2 算法度量指标
• 2.4 本章小结
• 第三章 PSO算法及混沌优化
• 3.1 最优化问题
• 3.2 PSO算法
• 3.2.1 基本原理
• 3.2.2 算法流程
• 3.2.3 标准粒子群优化算法
• 3.2.4 算法参数
• 3.2.5 PSO算法的优点与缺陷
• 3.3 PSO算法的改进策略和设计步骤
• 3.3.1 PSO算法的改进策略
• 3.3.2 PSO算法的设计步骤
• 3.4 混沌优化简介
• 3.4.1 基本原理
• 3.4.2 主要特征
• 3.5 本章小结
• 第四章 基于改进PSO算法的网格任务调度算法
• 4.1 任务调度问题定义
• 4.2 PSO算法改进及关键技术
• 4.2.1 粒子编码和解码
• 4.2.2 适应度函数
• 4.2.3 种群初始化
• 4.2.4 混沌优化搜索
• 4.2.5 边界处理
• 4.3 基于改进PSO算法的网格任务调度算法
• 4.4 本章小结
• 第五章 实验及性能分析
• 5.1 网格仿真工具
• 5.1.1 常用仿真工具
• 5.1.2 GridSim简介
• 5.2 实验及结果分析
• 5.2.1 实验方法
• 5.2.2 实验参数
• 5.2.3 实验结果分析
• 5.3 本章小结
• 第六章 结束语
• 6.1 工作总结
• 6.2 研究展望
• 参考文献
• 致谢
• 攻读学位期间主要的研究成果