摘要：在云计算架构下，工作流的分布式处理方式使得任务调度成为一项重点研究内容。本课题以云计算环境下的任务调度策略作为为研究对象。首先，本课题采用有向无环图的数据结构表征以云计算应用程序的工作流特性。然后以任务的总执行时间为优化目标，建立云计算工作流的任务调度模型。最后，本课题设计并实现相应的粒子群算法求解任务和处理器之间的最优映射关系。所设计的任务调度算法在根据真实应用程序提取得到的工作流图上进行评估。实验结果表明，本课题所实现的任务调度算法能够快速有效地获得工作流任务在处理器上的最佳调度。本课题方法在不同类型的工作流上均得以验证所获得的调度性能。

关键词  云计算  任务调度  粒子群算法  有向无环图

毕业设计说明书外文摘要

Title  Research on the Implementation of Particle Swarm Optimization   Based Scheduling Strategy in Cloud Computing Environments

Abstract：In cloud computing structures, the distributed prcessing of workflow tasks makes the task scheduling problem become an important research topic. The research task of this project is accordingly the task scheduling strategy in cloud computing structures. This project first uses directed acyclic graph to represent workflow characteristics. Then this project considers the total execution time of workflow as the optimization objective to construct the scheduling model. Furthermore, this work designs and implements a task scheduling algorithm based on particle swarm optimization to determine the optimal mapping relations between tasks and processing elements. The implemented scheduling algorithm was evaluated on various directed acyclic graphs profiled from realistic application workflows. Experimental results show that the particle swarm optimization based scheduling strategy is able to determine the optimal schedule of workflow tasks efficiently and effectively. The implemented algorithm was verified on various workflow applications to demonstrate the quality of its obtained schedule.

Keywords  Cloud Computing  Task Scheduling  Particle Swarm Optimization  Directed Acyclic Graph

目   录

1  引言 1

1.1  研究背景与意义 1

1.2  研究现状 1

1.3  总体技术方案及其社会影响 2

1.4  技术方案的经济因素分析 2

1.5  本文主要工作 2

1.6  本文结构 3

2  相关预备知识 4

2.1  工作流的DAG表示 4

2.2  云计算中的任务调度 4

2.3  粒子群优化算法 6

3  算法设计与实现 9

3.1  设计目标 9

3.2  总体设计框架 9

3.3  PSO算法的具体实现 11

3.4  云计算任务调度的具体实现 15

4  实验结果 21

4.1  实验工具与实验平台 21

4.2  实验数据 21

4.3  实验结果及分析 22

结  论 29

参 考 文 献 30

图1.1  云计算任务调度算法 1

图2.1  云环境中工作流的DAG表示 4

图2.2  PSO算法的搜索模型 6

图2.3  PSO算法的基本流程 7

图3.1  本文调度算法的总体流程图 9

图3.2  PSO算法实现的详细流程图 12

图3.3  对应图2.2所示的工作流的一个简单粒子 20

图4.1  前端界面设计图 22

图4.2  调节惯性权重w的结果图 23

图4.3  调节学习因子C1和C2的结果图 24

图4.4  调节种群规模N的结果图 24

图4.5  调节迭代次数Iternum的结果图 25

表3.1  前端设计结构表 10

表3.2  后端设计结构表 10

表3.3  数据交互设计结构表 11

表3.4  PSO算法主要变量定义表 12

表3.5  PSO算法主要函数定义表 13