本文是一篇物流工程论文，本文提出的R_ACO算法在任务调度顺序和虚拟机分配都采用了整数编码，以确保搜索空间完备，并针对任务调度顺序和虚拟机分配建立了对应信息素模型，根据信息素进行状态转移构成个体解。
第1章 绪论
1.1研究背景及意义
近年来， 随着互联网蓬勃的发展和信息技术设备的普及，全球互联网用户在互联网平台产生的数据量呈现指数增长，这些数据存储以及处理对计算能力提出了高要求，为了存储以及处理海量数据，需要采用计算能力更强的计算范式进行处理数据，云计算应运而生。
云计算是在网格计算( Grid Computing)、并行计算 ( Parallel Computing)、效用计算( Utility Computing)以及分布式计算( Distributed Computing ) 等基础上发展起来的[1]。云计算作为大规模计算平台由云计算服务提供者和云计算用户组成，云计算服务需求方即用户，随时随地利用互联网按照需求向云计算提供商获取计算资源，而云计算服务提供商采用一种“即付即用”的收费方式，便捷地向用户提供软硬件资源[2]。这种服务方式深受大众喜爱，个人、企业以及组织对云计算认可度越来越高。在全球范围内，许多知名IT公司争先恐后地加入云计算竞争行业。国际知名的云计算平台主要有谷歌的GCP（Google Cloud Platform）、亚马逊的AWS（Amazon Web Service）、微软的Azure、IBM的Blue Cloud，而国内知名云计算平台有阿里云、华为云、腾讯云、百度云等。
云计算作为一个兴起的领域，企业和学术界目前较为认可美国国家标准与技术研究院（National Institute of Standards and Technology，NIST）对云计算的定义——云计算是一种用户按需付费的服务模式，它提供便利的、泛在的计算资源，如服务器、存储空间、软件应用程序、互联网服务，在共享资源池中的资源可按需配置，通过最小的管理工作即可快速获取和释放资源[3]。云计算具有以下几个特征，①按需自助服务 ②广泛的网络接入③共享资源池④资源弹性服务⑤可评测量化的服务，云计算用户可随时随地利用互联网获得计算资源与服务[3]。云计算按照不同服务类型可分为以下几种：⑴基础设施即服务（Infrastructure as a Service，IaaS）:基础设施即服务是指将基础设施以服务的方式提供给客户，基础设施包括网络、存储和一些基本的计算资源。
1.2国内外研究现状
云计算环境下工作流调度算法多数在异构环境中或同构环境对工作流进行调度的算法。国内外研究人员对云工作流调度展开了研究，也提出了很多有效的算法。这些算法可以分为三类：启发式算法、元启发式算法以及启发式和元启发式混合算法。
启发式算法依赖于特定问题，通常无法保证解是最优的，但可根据特定规则在规定时间内求出良好的解，其解是确定的[11]。Topcuouglu等[12]提出了两种异构计算环境下工作流任务调度优化算法，即异构最早完成时间（HEFT）算法和处理机上的关键路径（CPOP）算法，以同时满足高性能和最小化调度时间。其中，HEFT算法根据任务的向上排序值生成任务调度顺序，并将其分配给处理器，采用基于插入式的方法使得完成时间最小化。HEFT是最为经典和流行的启发式算法。Zhang[13]等在不考虑任务之间传输时间前提下，提出一种有效的优先级和相对距离算法，以最小化工作流的任务调度长度，该方法可有效提高虚拟机的利用率和调度性能。Zhou[14]等提出了一种基于模糊优势排序的异构最早完成时间（FDHEFT）算法，以研究IaaS云中工作流调度的成本和完工时间联合优化，该算法将模糊优势排序机制与列表调度启发式HEFT紧密结合。Faragardi[15]等提出了一种新的资源配置机制和工作流调度算法，称为贪婪资源配置和改进HEFT（GRP-HEFT），该算法基于小时成本模型在给定成本预算约束下最小化工作流完成时间。Deldari[16]等基于可用的多核处理资源提出了一种在用户定义最后期限下工作流成本优化算法，该算法采用集群化工作流方式租赁更多核数处理资源来减少时间，在截止时间后将其他集群的任务填补空白时间以降低成本。Arabnejad[17]等开发了一种预算截止日期感知调度（BDAS）算法，其满足预算和时间限制，同时引入一种异构实例的可调成本-时间权衡策略。Bala[18]等提出一种改进的HEFT算法，该算法可以减少多种影响因素引起的资源服务器之间等待时间，比如资源服务器之间带宽，存储因素等。Lin[19]等基于弹性计算资源提出了SHEFT算法并形式化云计算环境模型和针对该环境的科学工作流以最小化工作流完成时间。
第2章 相关理论及模型定义
2.1云工作流相关概述
云计算是基于分布式计算、大数据、共享资源的一种新型计算范式[53]。随着互联网发展迅速，以科学研究和商业领域为代表的行业对云计算的需求都与日俱增，物流和电子商务行业同样产生海量数据。随着大数据时代到来，数据除了需要储存空间，也需要更多的资源来处理。传统的工作流系统面对高速发展且数据量庞大的工作流需求显得力有不逮，而近些年发展迅速的云计算能很好的处理工作流问题。工作流是一种业务过程抽象成任务自动化完成的计算模型。常见的是以计算密集和数据密集为主的科学工作流和以实例密集为主的商业工作流[54]。
云工作流是工作流管理系统在云环境下的一种新型应用模式[55]。集成工作流系统与云计算，云工作流使得资源获取与释放、管理监控变得快捷方便。云工作流一般具有透明性、可伸缩性以及实时监控特点，透明性是指云工作流可提供运行时，任务调度、负载均衡以及自配置机制；可伸缩性是说明云工作流可根据用户需求实现资源自动配置，可避免资源不够以及资源浪费现象；实时监控说明可通过侦测功能，了解掌握运行情况，及时应对故障发生[56]。
云工作流的核心问题是任务调度问题，即工作流中的实例被拆分为许多有依赖关系的不可拆分任务，然后将这些任务分配给合理的资源上处理。云工作流调度的目的不是简单地提供给用户一个调度方案，仅仅保证工作流顺利完成[57]。云工作流调度考虑更多是QoS即服务质量，满足用户QoS需求。云计算服务是一种即付即用的模式，也就意味着用户按照使用时间付费，合理的调度能减少云资源使用时间以减少费用；同时也可以释放云资源，使得资源利用率提高。云工作流调度已被证明是一个NP-hard问题，通常不能在多项式时间内求出最优解。在环境异构以及资源复杂的情况下，云工作流调度过程十分复杂，常见的是用启发式算法和元启发式算法求解。启发式算法通常依赖特定工作流案例，其求解速度快，质量通常不高；元启发式算法通过迭代进化搜索更优解，其算法复杂度以及搜索空间影响搜索效率。常见的元启发式算法有：蚁群算法、遗传算法、粒子群算法、模拟退火算法等。
2.3云工作流任务执行时间计算模型
工作流通常以文件形式处理数据，传输这些文件的方式会影响调度算法性能，尤其是成本和最大完工时间。一种常见的方式是点对点模型（P2P），另一种方式是使用全局共享存储系统作为文件存储[61]。P2P模型设定文件直接从处理父任务的虚拟机传输到处理子任务的虚拟机，这意味任务是同步通信的，虚拟机必须保持一直运行，直到子任务都接收完所有数据。这种方式会导致虚拟机租赁成本偏高。此外，虚拟机假如发生故障，会导致数据丢失，并且整个系统宕机，需要重新任务才可保障调度完整。因此，本文采用共全局共享储存模式进行数据传输。全局共享存储模型中，任务被执行前首先在全局存储中读取文件信息，任务执行完成后将输出文件存储在共享数据中心。特别注意的是，当一个任务与其父任务在同一台虚拟机上执行时，不需要读取其父任务产生的输入文件。
第3章 基于改进蚁群算法的云工作流调度优化方法.................... 17
3.1蚁群算法................................... 17
3.1.1蚁群算法原理................................. 17
3.1.2蚁群算法在TSP问题中的应用 ................ 18
第4章 实验评价................................ 37
4.1实验设置.................................... 37
4.1.1案例选择......................................... 37
4.1.2虚拟机配置.................................. 39
第5章 总结与展望............................. 50
5.1总结................................ 50
5.2展望................................ 51
第4章 实验评价
4.1实验设置
4.1.1案例选择
为公平、客观地验证本文提出的R_ACO算法的有效性，实验所选用的所有案例都源自于第三方案例库，确保本文算法和对比算法采用相同模型、相同案例下进行对比分析。实验案例可在案例库中自由下载，https://confluence.pegasus.isi.edu/display/pegasus/Deprecated+Workflow+Generator 学者普遍认可这些案例，不同的工作流各具其特色，一定程度上满足研究需求。本文选用了三种不同案例类型的科学工作流模型，分别为Epigenomics、LIGO、Montage.这些工作流案例来自不同的领域，具有不同的结构
