论文总字数：24282字

摘 要

随着云计算技术的迅速发展，人们越来越关注云计算任务的资源分配与调度效率。本课题的主要任务是实现基于混合元启发方法在云环境下的工作流任务调度，同于解决在时间限制内最小化成本的问题。其中混合元启发方法将采用粒子群算法与遗传算法的结合，用遗传算法中的交叉与变异的概念将粒子群算法的面向问题离散化，同时将减缓标准粒子群算法的局部收敛问题，通过交叉、变异操作来扩大解的搜索范围，从而防止粒子群算法收敛过快而产生局部最优解的现象。本篇文章将主要描述一下几方面的内容。

首先是对工作流的建模。由于现实需求的复杂性，绝大部分应用无法分解为独立任务，而只能划分为相对独立但在数据传输以及资源分配上相互依赖的子任务，这使得任务之间需要按照一定的逻辑顺序来完成。本文将使用DAG图来表示子任务之间的完成顺序。同时我们需要建立数学模型来模拟工作流的调度环境，并确定目标函数。我们希望实现在截止期限制下最小化云中工作流的执行成本。

其次我们将分别介绍几种常见的启发式方法，以及一些常见的启发式算法的混合方式。并详细介绍改进粒子群算法。我们希望通过对启发式算法的混合达到“取其精华，弃其糟粕”的目的。可以在保留原有算法一定完整性的同时加入其他启发式算法的元素，以达到扩大前期搜索范围，精确后期局部搜索的效果。

最后我们将实现标准粒子群算法和改进粒子群算法，并通过最快和最廉价两种评价标准来对比标准粒子群算法和改进粒子群算法的性能。

关键词：云计算，工作流，启发式，粒子群算法，遗传算法

Abstract

With the rapid development of cloud computing technology, people pay more and more attention to the resource allocation and scheduling efficiency of cloud computing tasks. The main task of this paper is to realize the workflow task scheduling based on hybrid meta-heuristic in the cloud environment. Mixed finite element to inspire method will use the combination of particle swarm algorithm and genetic algorithm, using the concept of crossover and mutation in genetic algorithm will face the problem of particle swarm optimization discretization, at the same time will slow the local convergence problem of standard particle swarm optimization, via an adaptive mutation function to enlarge the search range of solutions, so as to prevent the convergence of particle swarm optimization too fast and produce the phenomenon of local optimal solution. This article will mainly describe several aspects of the content.

The first is to model the workflow. Due to the complexity of practical requirements, most applications cannot be decomposed into independent tasks, but can only be divided into relatively independent but interdependent sub-tasks in data transmission and resource allocation, which requires tasks to be completed in a certain logical order. This article uses a DAG diagram to represent the order of completion between subtasks. At the same time we need to establish a mathematical model to simulate the workflow scheduling environment and determine the objective function. We want to minimize the execution cost of workflows in the cloud with deadline constraints.

Secondly, we will introduce several common heuristic methods and some common hybrid methods of heuristic algorithm. The advanced particle swarm optimization algorithm is introduced in detail. We hope to achieve the goal of "taking the essence and discarding the dross" through the mixture of heuristic algorithm. We can keep some integrity of the original algorithm and at the same time add other heuristic algorithm elements, in order to expand the early search scope, accurate late local search effect.

Finally, we will implement standard particle swarm optimization and genetic-particle swarm optimization, and compare the performance of standard particle swarm optimization and genetic-particle swarm optimization through the fastest and cheapest evaluation criteria.

KEY WORDS: cloud computing, workflow, meta-heuristic method, particle swarm algorithm, genetic algorithm

目 录

摘要 I

Abstract II

第一章 云计算环境下任务调度问题 1

1.1 云计算技术 1

1.1.1 云计算背景 1

1.1.2 云计算体系结构 2

1.1.3 云计算特点 3

1.2 云工作流管理系统 4

1.3 云工作流任务调度目标 5

1.4 云工作流任务调度数学模型 5

1.5 云工作流任务调度目标函数 7

第二章 云工作流调度相关元启发式算法 8

2.1 启发式调度算法研究现状 8

2.2 元启发式算法 9

2.2.1 遗传算法 9

2.2.2 粒子群算法 10

2.2.3 蚁群算法 11

2.3 混合启发式算法 12

2.3.1 蚁群算法 爬山算法 12

2.3.2 蚁群算法 遗传算法 12

2.3.3 遗传算法 贪心算法 13

第三章 云工作流调度改进粒子群算法 14

3.1 粒子群算法 14

3.1.1 粒子群算法模型 14

3.1.2 粒子群算法的参数 15

3.1.3粒子群算法的优化 16

3.2 改进粒子群算法 17

3.2.1 改进粒子群算法的提出 17

3.2.2 改进粒子群算法模型 18

第四章 算法仿真实现与分析 20

4.1 算法仿真与实现 20

4.1.1 评价指标 20

4.1.2 参数设置 20

4.2 算法总体比较 21

第五章 结论与展望 25

5.1 工作总结 25

5.2 工作展望 25

参考文献 26

致 谢 27

云计算环境下任务调度问题

1.1云计算技术

1.1.1云计算背景

如今，随着科学技术和全球经济一体化的发展，无论科研界还是社会商业对于应用服务提出的要求都越来越高，处理的任务量都越来越大。人们越来越需要一种可以集中处理、存储、网络以及基础计算资源的解决方案，可以根据所需动态的获取任意资源。云计算的出现解决了科研和商业界所需要的大量计算资源的难题。在它基础设施即服务的调度模型中，云计算为需要对计算资源更强大控制的用户应用程序提供虚拟硬件。虚拟机是IaaS中主要的计算单元，几乎与桌面计算机完全相同。它的灵活性使得通过网络连接的虚拟机变为具有强大计算能力的工具。这些计算工具对科研产生了巨大的影响，包括科学工作流这种强烈依赖于计算工具的问题。随着云计算的出现和云基础架构的快速部署，越来越多的大规模工作流应用程序在被“云化”，用户可以动态地获取和发布云资源，并且支付基础费用。

云计算的产生背景是多元化的。从社会经济方面来说，全球经济一体化的发展，使得人们需要功能更加强大的应用来存储，分析并处理巨大的数据，这其中需要足够的资源来支持庞大的存储空间和复杂的计算能力，用户的需求是云计算发展的动力；从社会层面来说，数字时代的来临使得人们的消费行为产生了很大的改变，很多时候金钱对于人们来说只是手机上的一个数字，而频繁的电子交易无疑使得数据的计算处理能力受到了极大的挑战；从社会发展角度看，我们的社会将出口型向内需型社会转变，如何满足人民大众日益增长并不断个性化的需要是一项严峻的挑战，同时我们的制造业不断向服务型、创新型转变，这其中计算机和互联网都将起到巨大的作用，无数的工业数据与资源需要得到处理；最后也是最重要的，计算机技术的长足发展为我们实现云计算提供了坚实的技术支持，企业信息技术的成熟与发展也对云计算的到来提供了更成熟的、更适用于商业的体系结构。以上从社会经济、民族发展以及技术支持等方面讲述了云计算的产生背景。下面就让我们来了解一下云计算的体系结构。

1.1.2云计算体系结构

由于云计算的商业产生背景，所以到目前为止，云计算并没有统一的规范和标准，各大公司都有自己的云计算理念和应用。在他基础设施即服务的调度模型中，云计算为需要对计算资源更强大控制的用户应用程序提供虚拟硬件。虚拟机是IaaS中主要的计算单元，几乎与桌面计算机完全相同。它的灵活性使得通过网络连接的虚拟机变为具有强大计算能力的工具。图1是云计算的体系结构的通用表示。

剩余内容已隐藏，请支付后下载全文，论文总字数：24282字