第一章 绪论
1.1 研究背景与意义
随着网络规模的快速扩大，应用服务的用户数急剧上升，企业或用户对计算机的处理能力和网络资源等需求日益增加，然而传统单一的计算资源已经无法适用于复杂的应用场景。同时，随着硬件技术的飞速进步，计算资源具备了更强大的功能，其价格也越来越便宜。在此技术背景下，云计算作为一种新颖的计算模式得到了广泛应用，它提供了各类应用、数据存储以及 IT 服务。根据用户需求，云计算利用虚拟化技术提供可靠性高的动态可扩展资源。云服务提供商可分为两类，一类是管理云平台和租赁资源的基础设施提供商，另一类是从基础设施提供商处租赁资源然后提供给终端用户的中间商。
近年来，各大 IT 公司纷纷进入到云计算服务领域，依托自身原有技术及业务优势推出云计算系统，目前比较成熟的有 Amazon EC2, Google App Engine，阿里云等[3]。为了将数目庞大，分布分散和运算性能不同的物理计算节点组织成强大的计算资源平台[4]，这些系统通常采用 Hadoop[5]、Spark[6]等大数据分析工具。云计算按照服务类型可分为软件即服务 SaaS、平台即服务 PaaS 和基础设施即服务 Iaa S[7]。现今，全球云计算企业的不断集中是一个明显的趋势，亚马逊、微软以及阿里云合计占全球 Iaa S 市场的 66.5%，其市场份额依旧在快速增长。
云计算系统运行效率与任务调度算法直接相关[8]。任务调度主要是在特定约束条件下采用适当的策略将任务分配到资源节点上，以达到某种调度目标。从服务提供商的角度出发，必须最大限度地通过降低任务调度的耗时，降低云数据中心的能源消耗和提高资源使用的效率等方式获取较好的经济收益，同时需要为用户提供优质的服务；而从用户的角度出发，希望以较低的费用获得较好的任务调度效果，比如任务执行的可靠性高、用时短、安全性好等。因此，任务调度不仅要尽可能满足服务提供商的利益，还需要兼顾用户的服务质量（Quality of Service, QoS）请求[9]。
.........................
1.2 国内外研究现状
云计算环境下，一方面，庞大的服务器规模、异构的资源和用户的 QoS，使得任务调度复杂化；另一方面，云计算系统的性能表现与任务调度算法紧密关联。因此，任务调度问题吸引了众多学者进行深入研究[15]。
早期研究主要关注工作流的执行时间、费用等指标中的某一个，最为经典的列表启发式算法是异构最早完成时间算法（Heterogeneous Earlist Finish Time, HEFT）[16]，根据任务间的通信开销以及任务在虚拟机上的平均执行时间来计算每个任务的调度优先级，选取高优先级的任务到能最快完成该任务的虚拟机上，从而实现总调度时间最小化。文献[17]通过调整工作流中的路径长度，充分挖掘了费用优化空间，提出了基于路径平衡的费用优化算法。郭禾[18]等人采用分层思想，运用动态规划策略计算出任务在进行服务选择时所产生的零碎时间，从而费用的优化空间得以提升。文献[19]提出了预算约束的 HEFT 算法（BHEFT），根据整个工作流的剩余预算和当前任务的可用预算进行相应的调度。Liu 等人[20]提出协同进化的遗传算法，通过调整交叉和变异概率加速算法的收敛并防止早熟。Vinothina 等人[21]运用蚁群优化算法来优化调度策略以达到最小的完工时间。李学俊等人[22]提出一种新的自适应惯性权重的粒子群任务调度算法，通过调整粒子速度以平衡粒子局部和全局搜索，获得执行费用更优的调度方案。
然而，单目标的任务调度已难以满足日益增长的用户 QoS，需要兼顾多个目标进行优化。而多个目标间相互冲突且存在非线性关系，诸多国内外学者对传统的单目标问题进行改进并应用到多目标优化问题中，由此提出了多种群智能算法
..........................
第二章 云计算基本理论
2.1 云计算概述
2.1.1 云计算定义与特点
云计算的概念最初来自于戴尔数据中心解决方案以及 Google-IBM 分布式处理项目。云计算是在分布式计算、网格计算等技术上发展而成的一种新型的商业计算模型，其发展历程如图 2.1 所示。在严格约束条件下，分布式计算将任务切分成小任务，采用若干个存储或处理单元来处理这些小任务。随后，并行计算逐渐发展起来，它同时使用多个处理器处理大型且复杂的任务。随着商业和科学计算的复杂化，网格计算凭借其超强的数据处理能力，获得了研究者们的青睐。它强调共享资源，在动态变化且由多个机构组成的虚拟组织中协调资源和解决大型问题。为了降低服务交付和服务应用方式的成本，SaaS 作为软件布局模型，为用户搭建了软硬件平台并且提供了运维服务，具有易维护、轻量化和成本低等特点。
近年来，云计算凭借配置灵活、资源利用率高等优势，逐渐颠覆传统互联网行业的部署模式。在云计算模式下，服务提供商通过云数据中心为用户提供大量的基础设施和服务，用户通过 web 接口配置和控制云计算资源，无需担心基础设施的故障问题，从而将更多的时间和精力花在商业模式创新和软件开发上，释放了边际信息化建设成本[40]。目前，被大众普遍接受的云计算定义由美国国家标准与技术研究院制定[41]：云计算是通过互联网以便利的、随需应变的方式获取计算资源（例如，存储、网络、服务器、服务和应用等）同时提高资源利用率的计算模式，其中资源来自于可配置的计算资源共享池。而且用户在资源管理、与供应商交互方面的工作量很少，只需要快速配置和发布相关的计算资源即可。
.........................
2.2 云工作流
2.2.1 云工作流简介
云工作流是工作流程的概括描述，由一系列相互衔接和自动进行的任务构成。云工作流技术集合了云计算平台和工作流系统，从而降低云计算成本并且提高云服务质量[45]。目前，在云工作流调度研究领域，调度的对象主要包括了两种类型的工作流。
第一种是科学工作流的调度，它占据了绝大多数的研究。由于科学工作流需要对大量的数据进行分析，因此需要有超强的存储和计算能力作为支撑。通常来讲，科学工作流主要分为计算密集型和数据密集型两大类。前者花费大量时间在计算方面，处理该类型工作流的服务节点不仅要具备较高的计算能力，而且对计算负载管理的要求也高。后者需要将大部分时间用在 I/O 和数据处理上面，采用数据并行策略处理 TB、PB 级数据量。最为常见的科学工作流应用包括 Montage，CyberShake，LIGO 和 SIPHT[46]。目前，科学工作流的调度要求不断提高，在调度方案耗时短的情况下，其对应的费用和性能指标也需要满足用户的 QoS.
第二种是商业等系统中的实例密集型工作流的调度。该类工作流实例通常需要将任务间的通信时间考虑在内，每个任务并不复杂而且所需要的计算能力不高。一般来讲，存在数量较多而且同时运行的工作流实例。但是它们对服务响应时间和任务执行效率的要求较高。比较常见的应用场景包括证券交易，航空铁路售票系统和银行转账业务等。在处理这些工作流实例时，对于服务器性能的考验较高，因为服务器的崩溃将会导致各方利益受损。
第三章 多目标问题建模与方法 ............................... 12 3.1 多目标优化 ..................................... 12
3.1.1 多目标优化问题模型 ................................ 12
3.1.2 Pareto 相关定义 ............................. 12
第四章 基于格分布方差的多目标工作流调度算法 .................................... 20
4.1 GVDA-MOPSO 工作流调度算法设计 ..................... 20
4.1.1 粒子编码 ......................................... 20
4.1.2 改进的自适应网格坐标系 ........................ 20
第五章 基于任务聚类的 NSGA-II 算法的多目标任务调度算法 ................................. 34
5.1 TC-NSGA-II 任务调度算法设计 ............................. 34
5.1.1 染色体编码 ................................. 34
5.1.2 遗传算子设计 ....................................... 35
第五章 基于任务聚类的 NSGA-II 算法的多目标任务调度算法
5.1 TC-NSGA-II 任务调度算法设计
5.1.1 染色体编码
种群中的每个个体代表一种可能的任务分配策略，染色体编码就是将染色体结构与解空间之间建立一种关联，编码结构的设计是 NSGA-II 算法的关键步骤之一。对于本文的任务调度问题，工作流中的任务具有依赖关系并且有层次区分。因此，本文先对工作流中的任务进行分层，确定每个任务所在的层级，然后对根据任务层级对染色体进行编码设计。算法 5 展示了任务分层算法的伪代码。
............................
第六章 总结与展望
6.1 工作总结
用户通常注重云平台的 QoS 表现，侧重考虑任务调度时间、费用等，希望花费较少的费用获得最佳的服务处理；同时，服务提供商需要从经济利益角度，评估整个平台的资源使用情况和运营成本。随着云计算的深入发展，云数据中心被广泛地建立起来，因此能耗问题日益突出。任务调度作为云计算的关键环节之一，直接跟云平台的效率和任务执行的效率相关。因此，在云计算环境下，研究云数据中心能耗，用户所关心的任务调度时间和费用等目标，具有一定的价值。通过学习与研究，发现多目标优化算法在这方面应用具有一定的优势。
本文针对工作流任务调度中的时间、费用和能耗等这个多目标问题，分别选择 MOPSO算法和 NSGA-II 算法进行研究，针对算法中存在的不足，对其进行优化。本文的主要工作总结如下：
(1) 概述了云计算基本理论，对工作流和任务调度进行了阐述，对所要研究的任务调度时间、费用和能耗多目标问题进行建模，确立任务调度的目标。这些工作为研究本课题提供了理论依据。
(2) 提出了基于格分布方差的多目标工作流任务调度算法（GVDA-MOPSO）。针对多目标粒子群算法平衡开发与开采难的问题，改进了网格坐标系，提出了格分布方差来评估当前 Pareto 前端的多样性，并以此动态地调节搜索策略。设计了差粒子自学习策略以提高解的多样性，其中设计了精英粒子的选取策略。从调度解集的多样性和收敛性指标，调度时间、费用和能耗方面来评估算法的有效性.
(3) 提出了基于任务聚类的 NSGA-II 算法的多目标任务调度算法（TC-NSGA-II）。为了进一步改善调度时间，采取任务聚类算法节省任务间的通信开销，从而达到降低调度时间的目的。同时，针对 NSGA-II 获得的 Pareto 工作流调度解集分布性较差的问题，设计了交叉算子与变异算子，引入了动态拥挤距离，提高了解的多样性。并将 TC-NSGA-II算法与 GVDA-MOPSO、NSGA-II 算法进行对比实验，以分析和证明算法的优势。
参考文献（略）