学位论文 > 优秀研究生学位论文题录展示

截止期约束的网格工作流费用优化算法研究

作　者: 邓定兰
导　师: 于炯
学　校: 新疆大学
专　业: 计算机软件与理论
关键词: 网格工作流任务调度贪心策略
分类号: TP393.02
类　型: 硕士论文
年　份: 2010年
下　载: 64次
引　用: 0次
阅　读: 论文下载

内容摘要

网格工作流任务调度算法本质是资源选择策略,是用于为工作流中具有前后约束关系的任务从功能比较相似、性能有些差异的网格资源中选择适当的资源,以满足不同调度目标的策略。DAG图(即有向无环图,Directed Acrylic Graph)描述的网格工作流时间-费用优化问题是计算网格中一个基本的且NP-hard的问题,目前已有许多关于最小化完工时间的优化算法。但随着网格应用向商业化方向发展,网格资源变为有偿服务,这使得工作流调度不仅要优化完工时间,还要优化费用。本文简要介绍了网格及网格工作流的相关概念及关键技术,综述了网格工作流优化问题的相关算法。另外,针对截止期约束的网格工作流费用优化问题,本文提出了三个调度算法:基于贪心策略的网格工作流调度算法GSA-GW (Greedy Scheduling Algorithm for Grid Workflow)、改进贪心算法IGSA-GW (Improved GSA-GW)和分层贪心结合算法BLGA-GW(Bottom Level and Greedy Algorithm for Grid Workflow)。文章首先按照用户提交的截止时间建立数学模型,然后利用上述三个算法求得近似最优解,最后通过模拟实验,证明了这三个算法能较好地满足用户的时间费用要求。

全文目录

摘要  3-4
Abstract  4-7
第一章绪论  7-17
  1.1 研究背景  7-13
    1.1.1 网格的内涵  7-9
    1.1.2 网格需要解决的问题  9-10
    1.1.3 网格应用需要网格工作流  10
    1.1.4 网格工作流的内涵  10-11
    1.1.5 网格工作流执行模型及系统分类  11-13
  1.2 研究现状  13-15
  1.3 课题来源及意义  15
  1.4 本文的主要工作  15-16
  1.5 本文的组织结构  16-17
第二章网格工作流任务调度研究  17-27
  2.1 网格工作流的调度模型  17-19
  2.2 网格工作流调度的目标参数  19-20
  2.3 相关算法研究  20-27
    2.3.1 遗传算法  21-22
    2.3.2 蚁群算法  22
    2.3.3 微粒群算法  22-23
    2.3.4 模拟退火算法  23-25
    2.3.5 分层算法  25
    2.3.6 相关算法的优点和不足  25-27
第三章基于贪心策略的网格工作流费用优化算法及改进  27-39
  3.1 问题描述及建模  27-29
    3.1.1 问题描述  27-28
    3.1.2 相关定义及数学建模  28-29
  3.2 贪心算法GSA-GW  29-33
    3.2.1 相关定义  29-30
    3.2.2 算法描述  30-32
    3.2.3 算法时间复杂度分析  32-33
    3.2.4 算法流程图  33
  3.3 改进贪心算法IGSA-GW  33-36
    3.3.1 相关定义  33-34
    3.3.2 算法描述  34-36
    3.3.3 算法时间复杂度分析  36
  3.4 算法实例化  36-39
第四章算法GSA-GW 及IGSA-GW 的实验仿真及结果分析  39-44
  4.1 仿真环境及参数设置  39
  4.2 实验结果及性能分析  39-44
    4.2.1 算法费用优化性能分析  39-40
    4.2.2 算法时间性能分析  40-41
    4.2.3 Deadline 与测试结果间的关系  41-44
第五章第三个算法（BLGA-GW）的提出及测评  44-46
  5.1 算法描述  44
  5.2 算法测评  44-46
第六章总结及展望  46-48
  6.1 全文总结及结论  46-47
  6.2 进一步的工作  47-48
参考文献  48-52
在读期间发表的论文清单  52-53
致谢  53

截止期约束的网格工作流费用优化算法研究

内容摘要

全文目录

相似论文