面向DAG任务调度的改进CRO多目标优化算法研究

摘要

在过去几年里，云计算已成为新兴技术产业中最热门的领域之一，在云计算“按需使用、按量付费”的商业服务模式下，并行任务调度已成为云计算领域中极其重要的关键技术。任务调度问题是NP(Non-deterministic Polynomial)难优化问题。基于群智能的随机搜索技术具有较强的普适性，目前已被用来求解任务调度问题，并且取得了比传统算法更好的解。然而，现有云任务调度算法考虑因素大多比较单一，建立新的问题模型和设计新的调度算法将具有重要的实际意义。
　　本文研究化学反应算法(Chemical Reaction Optimization)CRO在多目标任务调度问题求解中的应用，CRO算法融合了遗传算法和模拟退火算法的思想，是一种基于化学反应过程中分子的相互作用及能量转换过程的群体智能算法。本文的主要研究内容和成果如下:
　　1.建立云环境下任务处理时间-执行费用的双目标DAG任务调度模型。基于节点和通信边均带有权值的DAG(Directed A-cyclic Graph)图的任务调度问题模型考虑了云环境的异构性、任务间通信关系及优先约束关系等特点，能够很好的反映调度环境和任务的实际特性。
　　2.针对多目标任务调度问题，提出多目标化学反应算法，重新设计化学反应算法中四类分子碰撞准则，以及在求解调度问题时分子反应的具体操作。对任务处理时间-执行费用的双目标调度模型进行求解，仿真实验证明算法具有很好的收敛性和普适性，取得了较好的效果。
　　3.提出用于解决云环境下多目标任务调度问题的参数自适应调整的粒子群化学反应混合算法HPSO-CRO(Hybrid Algorithm Basedon Particel Swarm and Chemical Reaction Optimization)。该算法综合两种算法的优势，能够很好的平衡算法全局搜索和局部搜索能力。仿真实验结果表明算法比粒子群算法和化学反应算法具有更短的任务处理时间和更少的任务执行费用。

目录

声明

摘要

插图索引

第1章 绪论

1．1 研究背景与意义

1．1．1 研究背景

1．1．2 研究意义

1．2 国内外研究现状

1．3 本文的主要工作

1．4 本文的结构

第2章 云计算及任务调度

2．1 云计算

2．1．1 云计算概念及服务类型

2．1．2 云计算主要特征

2．2 云环境任务调度问题概述

2．2．1 任务调度问题的概念

2．2．2 任务调度问题的分类

2．2．3 云环境下任务调度综述

2．2．4 DAG调度模型

2．3 任务调度算法

2．3．1 调度算法综述

2．3．2 常用调度算法

2．4 小结

第3章 多目标优化问题及优化算法

3．1 多目标优化问题

3．1．1 多目标优化问题的数学描述

3．1．2 多目标优化问题的相关概念

3．2 传统多目标优化算法及其不足

3．3 群智能优化算法

3．3．1 粒子群优化算法

3．3．2 离散粒子群算法

3．3．3 化学反应算法

3．4 小结

第4章 基于多目标化学反应算法的云任务调度

4．1 云环境下DAG调度双目标模型

4．1．1 任务模型

4．1．2 云目标系统模型

4．2 多目标化学反应算法

4．3 基于多目标化学反应算法的任务调度

4．3．1 算法描述及流程

4．4 实验仿真与分析

4．4．1 实验环境

4．4．2 随机应用程序DAG任务图

4．4．3 多目标优化性能评价指标

4．4．4 实验结果与分析

4．5 小结

第5章 基于HPSO-CRO算法的云任务调度

5．1 HPSO-CRO自适应混合多目标优化算法

5．2 HPSO-CRO多目标DAG调度算法描述

5．2．1 解的表示

5．2．2 种群初始化

5．2．3 PSO操作中的更新机制

5．2．4 CRO局部操作更新机制

5．2．5 基于HPSO-CRO算法的云环境DAG任务调度流程

5．3 仿真实验与分析

5．4 小结

结论

参考文献

附录A 攻读学位期间发表的学术论文与获得的成果

附录B 攻读学位期间参与项目目录

致谢