第一章 绪论
1.1研究背景
云计算是一种信息技术服务模式，该模式通过对可配置虚拟资源（如网络、服务器、存储、应用软件和服务）的分享，实现了通过网络随时随地，快捷高效的对虚拟资源的访问、配置和管理。相比较传统的本地数据中心部署的模式而言，云计算能够在满足企业不同客制化服务需求的同时为企业大大降低了运维成本使企业更专注于业务。相比较传统的分布式计算、网络计算等模式，云计算具有如下 5 种特点[1]：
（1） 按需自助服务：用户能够在无需与云计算提供商联络的情况下，根据自己的实际需求使用云计算资源。通过这一服务，用户可以对具体的使用情况进行规划，例如需要多少计算和存储资源，以及如何管理和部署这些服务等。这种服务方式能够提高计算效率并为用户降低成本。
（2） 宽带网络连接：用户能够通过高带宽通信链路连接到云服务。这种通过低成本的高带宽网络连接到高利用率的大型 IT 资源池的服务方式，是云计算在经济上可行的一个重要因素。
（3） 资源池：云计算供应商的计算资源在多租户模式下能够为多个消费者服务，根据消费者的需求分配不同的物理资源和虚拟资源。
（4） 资源弹性配置：云具有对可配置资源弹性配置和释放的能力，按客户的需求可以快速地对资源进行分配和释放。
（5） 可被测量的服务：由于云计算面向服务的特性，用户所使用的云计算资源能够被自动的分配和监控，用户只需为其租用的云计算资源支付使用费用。
.......................
1.2研究内容
本文研究的混合云环境下基于弹性资源的动态工作流调度问题旨在研究一种高效可行的调度方法，为动态到达的工作流任务分配合适的计算资源，以达到减少租赁成本的目的，该问题具有以下几点特点：
（1） 到达云平台的应用请求是计算敏感的且具有随机性，到达时间和处理时长在其未到达之前是未知的，并且在被建模成工作流任务之后，其处理时长和截止时间是确定的。
（2） 所需调度的工作流各个子任务之间具有 DAG 依赖关系，每个子任务的执行需要占用一定的虚拟机资源。
（3） 云平台的计算资源（虚拟机）是弹性可扩展的，在本地虚拟机不够用时，可以从公有云租赁虚拟机。
（4） 虚拟机资源按集群进行管理，一个集群只处理一类特定的任务。
现有的关于云环境下的工作流调度问题大部分都是 NP 难问题[9],本文所研究的混合云环境下基于弹性资源的工作流调度问题与传统的调度问题不同之处在于：
（1） 传统的调度问题通常假设资源数目是固定的[10]，而本文所研究的问题场景基于混合云平台，其上的资源是弹性可扩展的。
（2） 传统的调度问题因受限于有限的物理机资源，其进行调度的任务的截止时间通常不是固定的[11]-[13]，超期的任务会被扣除相应的罚金。但在实际应用中，相对于给予用户超期补偿，用户更青睐于得到及时的应用反馈信息，因此，为调度任务设置确切的截止时间能给用户带来更好的使用体验。混合云平台上资源可扩展的特性恰好为这类确定截止日期的调度任务提供了便利。当某个集群中所处理的任务达到其处理阈值时，可以及时从公有云租用机器来扩大其处理能力而不必使任务超期。因此，本文研究的具有确定截止时间的工作流调度问题对于现实来说更有意义。
..........................
第二章 国内外文献综述
2.1启发式算法
启发式算法又可分为列表调度算法、聚类算法和任务复制算法三大类。
2.1.1 列表调度算法
列表调度算法根据各个任务的优先级维护一个包含所有任务的列表。它通常有两个阶段：任务选择阶段：选择任务优先级最高的就绪任务；处理器选择阶段：选择最合适的机器来处理该任务，以最小化预定义的成本函数（例如最早开始时间）。列表调度算法因为易于理解且实现简单，被很多研究者用于解决调度问题，例如 Arabnejad 等[30]提出了一种针对异构系统基于列表的调度方法 PEFT；Suzuki 等[31]利用列表调度对 DAG 并行任务调度问题提出了一种基于异构松弛度的算法 HLBS；Liu 等[32]针对异构计算系统的调度问题，提出了一种迭代列表调度算法，利用前一轮迭代地结果以迭代地方式提高调度质量；Beaumont 等[33]针对异构资源上的独立任务提出了一种基于列表调度的算法 HeteroPrio。列表调度算法能够在较短的调度时间内获得调度结果，相比较其他算法具有更好的性能表现。
2.1.2 聚类算法
聚类算法将给定数目的任务安排到不限数量的集群中，在每一步调度中，为集群选择的任务可以是任何任务而不仅仅局限于就绪任务。聚类算法通过不断迭代来优化集群，每次迭代都通过合并一些集群来优化之前的集群。Deng 等[34]利用数据集和任务之间的依赖关系，基于 K 均值聚类策略提出了一种高效的数据和任务协同调度策略，以提高工作流调度性能减少跨数据中心的数据传输总量；Kanemitsu[35]等针对数据密集型应用程序提出了一种基于聚类的任务调度算法 CMWSL，用于在大量异构处理器中最小化最差调度时长；Tsai 等[36]针对并行多工作流任务，基于聚类算法提出了一种自适应性双准则工作流调度方法，该方法既考虑了任务的完成时间又考虑了潜在资源的利用率提高了并行工作流的整体执行性能；Yoosefi 等[37]针对并行任务提出了一种可重构主序列聚类算法 Re DSC，该算法能有效减少并行运行时间。
.........................
2.2元启发式算法
许多元启发式算法例如粒子群优化算法（PSO），遗传算法（GA），模拟退火算法（SA）和蚁群算法（ACO）均被应用于工作流调度问题。Tao 等[41]提出了针对多维度的复杂空间中的工作流可信调度问题提出了一种旋转混沌粒子群优化算法 RCPSO；Jena 等[42]针对云环境下的多目标任务调度问题提出了嵌套粒子群优化调度方法，以减少能源消耗和处理时长；Liu 等[43]改进了具有可变领域的基本粒子群算法，用于解决有安全限制和数据密集型的工作流调度问题；Cui 等[44]提出了一种基于遗传算法的数据副本放置策略，用来减少云中数据传输带宽的消耗和执行延迟；Ahmad 等[45]通过修改遗传算子并采用有效的启发式算法提出了混合遗传算法 HGA，该算法能有效的在调度执行过程中优化负载平衡，最大限度的利用资源；Eawna等[46]针对多层应用中的动态资源配置问题，将粒子群优化算法和模拟退火算法结合提出了PSO-SA 算法，该算法对于多层应用资源的配置比单一 PSO 或 SA 算法更快；Xiong 等[47]针对云数据中心的任务调度问题将 Johnson 规则与遗传算法相结合，提出了一种针对云数据中心多处理器调度特点的基于 Johnson 规则的遗传算法 JRGA。
元启发式算法通常需要大量的 CPU 计算时间和内存空间才能提供高质量的调度方案，而现实的云计算场景往往需要实时计算，这使得在实际的云计算场景中元启发式算法的应用并不广泛。
元启发式算法通常用于解决静态的任务调度问题，而对于任务负载通常是百万级的动态任务调度问题，快速启发式算法则更为适用。Ousterhout 等[48]针对百万级的并行任务调度问题，介绍了一种采用随机抽样方法的无状态分布式调度器 Sparrow，Sadooghi 等[49]针对大规模并行任务提出了一个紧凑、轻量、可扩展的分布式任务执行框架 CloudKon，Wang 等[50]-[51]提出了一种适用于多云环境下的自适应任务负载分配系统，该系统能优化云中的云延迟和本地与云端之间的数据传输延迟，提高对用户请求的响应能力。因为上述系统和算法的目标是每秒处理百万级任务量的任务，所以它们采用了简单而快速的方法进行独立任务的调度和资源分配。因此，它们对于具有依赖关系的工作流任务调度问题并不有效，由于任务之间的依赖关系导致的优先级限制，计算可行解的时间反而大大增加了。Topcuoglu 等[52]提出的 HEFT算法是解决此类问题最常用的基于列表调度的启发式方法，该算法首先根据优先级排序具有依赖关系的任务，然后将它们分配给适当的资源以获得性能上的优化。
............................
第三章 混合云环境下动态工作流调度问题描述 ...............................10
3.1问题场景 ...........................................10
3.2应用请求工作流和资源模型 ........................................... 11
第四章 混合云环境下动态工作流调度方法 ............................17
4.1动态工作流调度方法总体框架 .................................17
4.1.1 动态工作流调度方法 ..........................................18
4.2任务调度方法 .........................................19
第五章 模拟实验 ........................................................38
5.1方法组件组合和测试实例 .....................................38
5.1.1 各方法组件组合 ................................39
5.1.2 测试实例 ..................................39
第五章 模拟实验
5.1方法组件组合和测试实例
5.1.1各方法组件组合
在任务调度阶段我们提出了 2 种任务调度方法 STS 和 GTS，在未开始任务收集阶段我们提出了 JSC 收集方法，在重调度阶段我们提出了 MINS 和 MILS 两种重调度方法。上述方法除了任务调度阶段的方法是不可或缺的以外未开始任务收集阶段和重调度阶段的方法都不是不可或缺的，因此，本文提到的动态工作流任务调度方法总共2 × 2 × 3 = 12种变种，如表 5.1所示。我们将通过测试实例对这些方法变种进行实验并评估挑选出其中调度效果最好的组合。
...........................
第六章 总结与展望
6.1总结
经过了近十年的发展，云计算技术已经深入应用到了企业、游戏、医疗、金融等生产生活中的各个领域，有效解决了传统 IT 技术面临的投资成本过高、运维工作量大、办公不灵活、数据安全无法保证等问题。近些年我国的云计算发展进入了快车道，在政策支持和产业推动下，越来越多的企业开始使用云计算这一信息技术服务模式。云计算的几种部署模式中，混合云因其高安全性和多计算资源的特点日益受到企业用户的青睐，混合云环境下的资源调度问题也成为了学术界和工业界研究的重点问题。
本文研究的混合云环境下的动态工作流调度问题针对的是混合云环境下的子任务间依赖关系可用 DAG 表示的工作流动态调度问题，提出了一种能够有效减少租用虚拟机成本的调度方法。该方法由任务调度阶段的基于单个任务的调度方法、未开始任务收集阶段的收集方法和重调度阶段的以单台虚拟机上总任务安排时长尽可能大为优先的重调度方法组成。并通过实验验证了在大部分任务负载的情况下该方法相较于经典的 HEFT 方法均能有效减少租用虚拟机的成本。
参考文献（略）