混合自适应粒子群工作流调度优化算法

马学森，许雪梅，蒋功辉，乔 焰，周天保

（1.合肥工业大学 计算机与信息学院，合肥 230601；
2.安全关键工业测控技术教育部工程研究中心（合肥工业大学），合肥 230009）

近年来，随着互联网和5G 快速发展，云服务模式不断成熟，云计算在学术界、工业界和政府部门等场合得到了广泛应用，用户应用程序普遍从集群和网格大规模迁移到基础设施及服务（Infrastructure as a Service，IaaS）云，云提供资源并向用户定价收费［1］。应用程序主要由一组数据相互依赖的任务组成，在云端形成有向无环图（Directed Acyclic Graph，DAG）工作流［2］。具有截止期的工作流要求应用程序都必须在有限的时间内完成［3］。因此，如何在具有截止期约束的条件下进行工作流调度成为近年来研究的热点之一。此外，云工作流调度的性能一方面影响用户的响应时间，另一方面关乎云提供商资源成本投入。用户希望在截止期内尽快完成应用程序工作流，而云提供商希望以较低成本满足用户需求以获得更高利润。因此，研究如何合理调度DAG 工作流，保证工作流在截止期内完成前提下，在用户与供应商之间权衡工作流完成时间和执行成本有重要意义。

云计算中的任务调度已经被证明是非确定性多项式（Non-deterministic Polynomial，NP）难问题［4］，尤其将工作流模型应用于云任务调度中，使问题更加复杂。近年来，众多学者提出了不同的工作流调度目标模型和算法：李启锐等［5］根据变化的用户数量及资源采用不同的调度策略需求，建立了云作业调度系统模型，以此解决一种由传输时间、等待时间和执行时间三部分构成的多目标优化问题，所提算法有效降低作业的整体完工时间；
Han 等［6］提出一种启发式算法通过同时最小化工作流的完成时间和执行成本来解决工作流调度问题；
Alkayal 等［7］构建了工作流完成时间、执行成本以及系统吞吐量的多目标模型，基于新的排序策略提出改进的多目标粒子群算法，具有较好的效果；
童钊等［8］提出一种基于强化学习的工作流调度算法，采用Q-learning 算法及线性加权法，优化工作流的完成时间及执行成本。上述研究主要以工作流完成时间、执行成本等目标优化为主，具有较好的优化效果，但是针对在满足所有工作流截止期约束下，以优化其完成时间及执行成本为目标的研究相对较少。

文献［9-12］中考虑了工作流的截止期，建立了不同的工作流调度模型，提出了不同算法解决具有截止期工作流的调度问题，具有较好的效果；
但上述文献均以最小化工作流执行成本为优化目标，解决的是在工作流完成时间的前提下，以最小化工作流执行成本为目标的单目标问题。针对具有截止期的工作流，权衡工作流的完成时间与执行成本的多目标优化问题亟须进一步研究。

此外，采用线性加权法求解多目标优化问题时，目标的权重系数对优化效果产生很大的影响，因此，大量研究者在权重系数的选择上进行了研究。孙长亚等［13］将任务完成时间、执行成本及负载均衡根据任务需求人为确定一组权重系数；
方伯芃等［14］将工作流服务费用及执行成本的权重系数人为确定三组依次做实验。上述实验权重系数的确定都具有一定的主观性。虽然上述基于强化学习的工作流调度算法通过大量实验可以得到一组多目标的权重系数，具有一定的客观性，但是其复杂度高，并且权重系数是个静态值，无法动态调整优化。因此，如何在工作流调度过程中，根据工作流的变化自适应确定各个目标的权重系数，将多目标的值权衡最小化亟须进一步研究。

目前，云工作流调度算法主要分为非启发式算法与启发式算法两种。Max-Min 算法［15］等经典的非启发式算法属于尽力服务类调度算法，目的是在更短时间内找到工作流调度方案，而不是以工作流完成时间为优化目标。最早完成时间（Heterogeneous Earliest Finish Time，HEFT）算法［16］等传统的启发式算法主要以工作流完成时间最少为优化目标，未同时考虑资源代价问题，难以解决同时满足用户及云提供商需求的问题；
且传统启发式算法效率低，而智能启发式算法效率高，可在短时间内找到问题的解决方案，而且还可以应用于带有约束条件的更为复杂的调度问题。最经典的智能启发式算法包括蚁群算法（Ant Colony Optimization，ACO）［17］、遗传算法（Genetic Algorithm，GA）［18］和粒子群优化（Particle Swarm Optimization，PSO）算法［19］等，其中：ACO 计算开销较大，一般用来解决在图上搜索路径的问题。GA 通过选择、交叉和变异保证问题解的多样性进而获得问题的最优解。PSO 算法相较于ACO、GA 等全局优化算法，其优点是需要调整的参数较少、实现简单、计算复杂度与问题规模呈多项式关系等，且可通过迭代寻找最优解，在求解云工作流调度问题上具有天然的优势；
但PSO 与其他智能启发式算法相似，具有易陷入局部最优、早熟收敛的缺点。因此，一些研究针对PSO 的缺点进行改进。张晓丽［20］引入混沌搜索对PSO 进行改进，提出了一种基于粒子群优化的云工作流调度算法，实验结果表明，比改进后的ACO 及改进后的GA 寻优效果更好；
李学俊等［21］提出了改进粒子群优化算法（简记为惯性权重粒子群算法（Weight Particle Swarm Optimization，WPSO）精准调整粒子速度的自适应权重，求解满足时间约束时能耗最优的调度问题，考虑了粒子易陷入局部最优的问题，但忽略了对种群初始化方式进行改进可以提高收敛速度的问题。因此，对如何应用PSO 实现工作流调度问题需要做进一步研究。

为解决以上问题，本文在考虑DAG 云工作流的截止期约束下，在用户与供应商之间权衡工作流的完成时间与执行成本，提出一种混合自适应粒子群工作流调度优化算法（Hybrid Adaptive Particle Swarm Optimization algorithm for workflow scheduling，HAPSO）。首先，从用户及云提供商角度构建了DAG 云工作流调度模型；
其次，针对工作流完成时间与执行成本的冲突问题，引入范数理想点方法，同时与自适应权重结合，将DAG 调度模型转化为权衡工作流完成时间与执行成本优化目标的数学问题；
最后，通过改进PSO，平衡粒子群的局部搜索与全局搜索能力，进而对DAG 完成时间与执行成本的目标优化问题进行求解。通过实验验证了HAPSO 调度云工作流具有较好的优越性。

1.1 模型描述

本文提出的DAG 云工作流调度模型如图1 所示。DAG云工作流调度模型主要由用户提交的工作流应用程序、设计算法生成调度方案和云提供商提供资源完成工作流调度三部分组成。在该模型中，用户提交应用程序工作流，用DAG图表示。工作流到达后，首先确定工作流调度的优化目标，本文调度目标是在满足工作流截止期的同时，权衡用户与云提供商之间的需求最小化；
然后通过本文设计的HAPSO 对用户提交的工作流进行处理，找到目标最优的调度方案；
最后云提供商根据调度方案将工作流中的任务分配到相应的虚拟资源节点上，实现工作流的调度。

图1 DAG云工作流调度模型的架构Fig.1 Architecture of DAG cloud workflow scheduling model

本文提出的DAG 云工作流调度模型中的工作流用DAG表示。DAG 可以符号表示为G(T，E)，其中T为DAG 中的任务集合，T={t1，t2，…，tn}，ti(1 ≤i≤n)为DAG 的一个顶点，表示第i个任务。E为DAG 中任务之间的约束关系集合，E={(ti，tj)|ti，tj∈T}，其中任意一个有向边eij（DAG 中的边）代表依赖任务ti到tj之间的数据传输量。一般假设DAG 只有一个入口节点（无父节点）和一个出口节点（无子节点）。云提供商负责提供资源，主机p个，虚拟机m个，虚拟节点资源（虚拟机）表示为VM={v0，v1，…，vm-1}，其中vj(0 ≤j≤m-1)表示序号为j的虚拟机。每个任务分配到一个虚拟机运行，任务与虚拟机的分配映射关系用矩阵Z=(zij)表示。zij=0 表示任务ti不分配到虚拟机vj；
zij=1表示任务ti分配到虚拟机vj。

DAG 云工作流调度模型解决的问题是：在保证工作流在截止期内完成前提下，找到权衡工作流完成时间与工作流执行成本最小化的DAG 云工作流调度方案，完成工作流调度。

1.2 调度目标

本文提出的DAG 云工作流调度模型解决的问题是在工作流的截止期约束下，权衡工作流的完成时间Makespan和执行成本Cost。在本节中，对调度优化目标进行相关定义。

定义1工作流完成时间Makespan。

DAG 工作流的完成时间Makespan为DAG 中的任务最大完成时间：

其中：任务ti完成时间FT(ti)包括响应时间ST(ti)、执行时间ET（ti）和传输时间TT(ti，ts)，满足关系

其中：succ（ti）表示任务ti的所有直接后继任务集合，任务ts为任务ti的直接后继任务之一。

通过式（3）计算得到ST(ti)：

式（3）中：pred（ti）为任务ti的所有直接前驱任务，avai[vmti]表示虚拟机准备执行任务ti的最早时间。入口任务tentry可以立刻获得资源，其响应时间为0；
非入口任务响应时间取决于该任务所在虚拟机的开始执行时间和该任务的所有前驱任务都完成的时间。

任务ti的执行时间

其中：Tlengthi为任务ti的长度，vj为虚拟机j的CPU 速度，pej为虚拟机j的CPU 数目。

任务ti到其直接后继任务ts的数据传输时间为：

其中：若任务ti与其直接后继任务ts在不同虚拟机上执行，则存在传输时间；
否则，传输时间为0。vi是任务ti分配的虚拟机，vs是将要执行任务ts的虚拟机，bw为虚拟机vi和vs的传输带宽。本文假设虚拟机带宽相同。

定义2工作流执行成本Cost。

云工作流调度中，虚拟机按单位时间收费，Tunit表示IaaS云的单位时间。工作流执行成本Cost为：

式（6）中，总执行时间为：

总传输时间为：

其中：vm_costj表示虚拟机j单位时间执行成本，bw_cost表示虚拟机单位时间传输成本。

定义3工作流的约束条件。

本文考虑工作流调度的三种约束：资源约束、任务间依赖约束以及截止期约束。

1）资源约束。

每个任务只能由一个虚拟机处理：

表示在分配矩阵Z的每一列中，只有一个元素的值为1，以保证每个任务只能分配到某一个虚拟机上执行。n为任务的数目，m为虚拟机数目。

2）任务间依赖约束。

任务的执行和传输的起始时间及结束时间满足的条件为：

其中：Ts1、Ts2分别为任务的执行起始时间和传输起始时间，Te1、Te2分别为任务的执行结束时间和传输结束时间。

其中：1 ≤i≤n，1 ≤k≤n，0 ≤j≤m-1，i≠k。约束（12）表示，对于每个任务ti进行传输之前必须完成执行；
约束（13）和（14）保证被分配到同一虚拟机的任务顺利执行和传输。例如，两个任务ti、tk被分配到同一虚拟机vi，任务tk在ti之后执行。约束（13）表示任务ti执行的结束时间在任务tk执行时间之前；
约束（14）表示任务ti传输的结束时间在任务tk执行时间之前。

3）截止期约束。

为保证DAG 工作流在截止期内完成，需满足：

其中：工作流的截止期［22］由工作流最快调度完成时间与截止期因子γ共同决定。由最早完成时间算法HEFT 得到的值作为，γ用来控制工作流截止期的紧急程度。

在工作流调度过程中，针对可能出现某些任务在队列中等待时间过长导致工作流不能在截止期内完成的情况，定义任务ti的最迟开始时间为：

其中：succ（ti）表示任务ti的所有直接后继任务集合，任务ts为任务ti的直接后继任务之一。没有直接后继任务的任务ti的最迟开始执行时间为工作流的截止期与ti的最小执行时间之差，有直接后继任务ts的任务ti的最迟开始执行时间为任务ts的最迟开始时间减去两者的最小传输时间得到的值与任务ti的最小执行时间之差。

定义4调度目标优化问题。

将DAG 云工作流调度模型转化为目标优化数学问题，如式（18）所示，即本文需要解决的问题是找到最小值f。通过范数理想点将Makespan与Cost设置为同一量级，η1+η2=1，fT代表工作流完成时间，由HEFT 得到的值作为最快调度完成时间，fC代表工作流执行成本，由贪心算法以执行成本Cost为目标调度得到的值作为最小工作流执行成本，η1、η2分别为工作流完成时间与执行成本部分的权重。

因此，本文DAG 工作流优化目标形式化定义为式（19）。Minf表示对Makespan和Cost的两个冲突目标在工作流截止期约束条件下进行协调折中处理，同时得到目标函数最小值f。

定理1对于任意DAG 工作流，总存在一组系数使得f最小，即∀DAG，∃（η1，η2）使得f最小。

由定理证明可知，存在一组权重系数（η1，η2）使得f最小，且η1、η2值随着fT、fC值自适应改变，由证明过程可推导出：

混合自适应粒子群工作流调度优化算法的调度目标为最小化f，通过求出全局最优解获得满足工作流截止期同时，权衡工作流完成时间与执行成本最小值的工作流调度方案，实现工作流的最佳调度。

云工作流调度属于离散优化问题，将粒子群优化（PSO）算法的解进行离散化编码可以很好地解决云工作流调度问题；
但是PSO 存在易陷入局部收敛的问题。针对此问题，本文提出混合自适应粒子群工作流调度优化算法HAPSO，对PSO 进行4 个方面改进：1）引入萤火虫算法（Firefly Algorithm，FA）［23］得到的调度方案来初始化HAPSO 粒子的初始位置，避免粒子初期由于搜索范围大导致搜索时间长的问题；
2）采用非线性递减方法对惯性权重进行自适应动态调整，结合伽马随机函数动态变化学习因子大小，跳出局部收敛状态；
3）引入花朵授粉算法的概率切换机制，自适应调整局部搜索与全局搜索策略；
4）对越界情况处理提出改进策略。

2.1 离散化编码

HAPSO 采用最小位置原则（Smallest Position Value，SPV）［24］编码方式将粒子位置映射到虚拟机资源上，每个粒子的位置代表一种调度策略，粒子的坐标代表调度策略的映射方式，粒子的适应度值代表调度策略的目标值。所有可行的调度策略构成了整个算法的解空间，每个粒子都在解空间中寻找最优解。第i次迭代中每个粒子的位置构成一个向量Xi（Xi=｛xi1，xi2，…，xin｝），n为构成DAG 工作流的任务总数，xin∈Xi表示一个粒子在第i次迭代后每个任务被分配到虚拟机的编号。对向量Xi进行处理：

将第t次迭代后粒子位置按SPV 方式处理再进行求余，得到任务ti所对应的虚拟机编号，实现任务到虚拟机资源的映射。m为虚拟机数目指的是第i次迭代的任务序号为d的位置。

假设调度一个由6 个任务构成的DAG 工作流，虚拟机的个数为4。6 个任务分配到4 个虚拟机，虚拟机编号为｛0，1，2，3｝，若HAPSO 得到最优解为｛2.4，7.1，5.3，6.7，3.5，4.2｝，经编码处理得到任务映射到虚拟机的结果如表1所示。

表1 粒子编码Tab.1 Particle coding

由解可知，任务6 分配到虚拟机0，任务3 分配到虚拟机1，任务1 和4 分配到虚拟机2，任务2 和5 分配到虚拟机3。被分配到同一虚拟机上的任务则按照依赖顺序先后执行，被分配到不同虚拟机上的任务但具有依赖顺序关系的则父任务执行完之后再进行数据传输，子任务才能执行。

2.2 种群初始化

萤火虫算法具有参数少、易实现等优点，采用多个位置并行的全局随机搜索策略，在求解本文优化目标问题时，能够同时获得每个任务被分配的虚拟机资源。因此，为了改进粒子群初始种群的质量，将萤火虫算法得到的工作流调度方案X=｛x1，x2，…，xn｝作为HAPSO 粒子i第一次迭代时的个体最优值与全局最优值初 始值。n为 构成DAG 工作流的任务数。HAPSO 中每个粒子先随机初始化速度，再根据个体最优值以及全局最优值更新自身的速度以及位置。图2 展示了HAPSO 中粒子更新位置的具体过程。

图2 粒子位置更新示意图Fig.2 Schematic diagram of updating particle position

式（22）计算粒子i第t+1 次迭代时的速度：

其中：w为惯性权重，c1和c2为学习因子，r1和r2是［0，1］内随机数分别为第t次迭代时个体最优解和全局最优解为第t次迭代时粒子i飞行的速度为第t次迭代时粒子i的位置。

式（23）计算第t+1 次迭代时粒子i的位置

在初始化HAPSO 时，FA 得到的最优工作流调度方案X=｛x1，x2，…，xn｝映射到HAPSO 各粒子位置X1=｛x11，x12，…，x1n｝作为第一次迭代时的个体最优值以及全局最优值。在后续粒子迭代过程中，每个粒子根据HAPSO 的位置更新公式不断调整该初始值，在解空间寻找最优的调度策略，直到找到最优解或者达到迭代次数。种群初始化算法表述如算法1。

算法1 种群初始化算法。

输入 任务列表Cloudlets，虚拟机列表Vms；

输出 初始化种群Swarm。

2.3 自适应动态优化参数

由图2 可知，惯性权重w代表当前迭代粒子速度对下一次迭代时粒子速度的影响程度。学习因子c1、c2分别代表当前迭代个体最优值与全局最优值对下一次迭代粒子速度的影响程度，r1和r2是［0，1］内随机数。因此，针对粒子在对虚拟机资源分配给任务时易陷入局部最优的问题，对惯性因子、学习因子进行改进，根据粒子迭代次数自适应动态改变参数值，提高粒子的搜索效率。

1）惯性权重自适应。

由式（22）可知：w>1 时，粒子速度会越来越大，最终粒子处于发散状态。w∈(0，1]时，w越大，对下一次迭代速度影响越大，增大种群多样性，有利于算法前期探索搜索空间；
w越小，对下一次迭代速度影响越小，有利于算法后期局部开发能力。胡堂清等［25］采用非线性递减函数对惯性权重w处理，实验证明采用非线性处理得到的收敛效果优于线性处理。因此，本文采用非线性递减方式对惯性权重处理，如式（24）所示：

其中：wmax=0.9，wmin=0.4［25］，t为当前迭代次数，T0为算法的总迭代次数。惯性权重w随着粒子迭代非线性减小，实现自适应的动态改变。

2）学习因子自适应。

由式（22）可知，学习因子较大代表个体最优值及全局最优值对下一次迭代速度的影响程度越大。针对工作流调度中寻找目标最优值的问题，HAPSO 前期注重自我学习，c1较大，c2较小；
HAPSO 后期注重向群内学习，c1较小，c2较大。针对算法中学习因子一般取值2.0［26］，造成易陷入局部最优的问题，本文结合伽马随机函数，动态改变学习因子，跳出局部收敛局面。本文对学习因子的改进，具体描述如式（25）（26）所示：

其中：cmax=2.5，cmin=0.5［27］，λ=0.1［28］，t为当前迭代次数，T0为算法的总迭代次数。

2.4 获取个体最优值与全局最优值

2.5 位置更新

由于PSO 不能很好地平衡局部搜索与全局搜索能力，HAPSO 引入花朵授粉算法的概率切换机制，对粒子迭代过程中全局搜索与局部搜索进行处理。设计随机切换概率p值，p∈[0，1]。实验［29］证明：p值过大，算法注重于全局授粉，收敛速度慢；
p值过小，算法注重于局部授粉，易陷入局部最优解；
当p=0.8 时，算法性能最好。因此，将p值设定在0.8附近波动，如式（29）所示，实现自适应切换局部搜索与全局搜索。若随机生成［0，1］值rand≤p，则粒子进行局部搜索，位置按式（23）更新；
若rand>p，则粒子进行全局搜索，位置按式（30）更新。

式中：vpbest表示个体最优速度，vgbest表示全局最优速度，表示粒子i在第t+1 次迭代时的速度分别为粒子i在第t次及第t+1 次迭代时的位置，L(λ)是花朵授粉算法的Levy 飞行函数；
rand、ε是［0，1］的随机数。

2.6 越界处理

针对粒子容易出现越界情况，一般以边界作为粒子位置［29］，这样处理方式简单，但由于绝大多数边界值并不是全局最优解，导致算法收敛效果不好。因此，HAPSO 采用beta分布函数对边界问题进行处理，将越界粒子均匀分布到具有可行解的搜索范围内，对粒子越过上界及下界按式（31）处理，重新初始化越界粒子的位置，a=b=0.8［28］，效果较好。

2.7 算法流程

设计混合自适应粒子群工作流调度优化算法HAPSO 的伪代码如算法2 所示。

若任务数为n，HAPSO 中粒子种群规模为m1，迭代次数为t1。FA 中萤火虫数量为m2，迭代次数为t2，则算法FA 时间复杂度为O(m22×t2)，由于初期使用FA 对HAPSO 各粒子位置初始化，本文设置t2远小于t1，m2较小，本文分别对惯性因子、学习因子，以及局部搜索与全局搜索的切换，边界问题处理都是简单的操作，可以在每次迭代中完成，复杂度O(1)，因此，总的算法时间复杂度为O(n×m1×t1)。

算法2 HAPSO 算法。

输入 DAG 工作流，最大迭代次数T0；

输出Makespan与Cost权衡最小值f。

3.1 仿真环境

将CloudSim［30］作为本文工作流调度实验的仿真器，通过在Datacenter Broker 类中添加调度算法HAPSO 完成仿真。为了模拟真实的随机复杂环境，本文随机生成DAG 工作流，通过任务的数量不同来改变DAG 的规模。设置云仿真参数如表2 所示。

表2 云仿真器参数设置Tab.2 Parameter setting of cloud simulator

将HAPSO 与PSO［19］、WPSO［21］、ACO［17］进行对比，其中，WPSO 是基于PSO 改进的算法，ACO 是与PSO 完全不同的算法。通过这些对比算法来验证本文提出的HAPSO 在工作流调度方面的性能。设置四种算法的各参数如表3 所示，其中，种群大小设置为30，迭代次数为500。将每次随机生成的DAG 工作流保存为文件，四种算法从同一文件中读取DAG 进行工作流调度实验。

表3 算法参数设置Tab.3 Parameter setting of algorithms

3.2 算法收敛性分析

为验证本文HAPSO 具有较好的收敛性，将PSO［19］、WPSO［21］和ACO［17］在解决求同一函数最小值问题方面进行比较，分别计算出四种算法对同一函数求最小值的收敛性结果，如表4 所示。

表4 算法收敛性对比Tab.4 Comparison of convergence among algorithms

图3 展示了四种算法在迭代过程中的适应度值的具体变化。

图3 四种算法的迭代效果对比Fig.3 Comparison of iterative effects of four algorithms

算法的收敛性指标为收敛速度与收敛精度。本实验中，收敛速度通过收敛迭代次数衡量，收敛精度通过寻优结果最小值衡量。由表4 可知，ACO 比PSO 收敛速度快，收敛精度高。WPSO 提高了收敛速度，但是收敛精度低于ACO。本文提出的HAPSO 极大地提升收敛速度的同时，也提高了收敛精度，HAPSO 的收敛性优于ACO。

从图3 可直观看出，首先，算法开始迭代时，HAPSO 初始解优于其他三种对比算法，说明引入FA 初始化HAPSO 具有很好的效果。HAPSO 在后期迭代时每个粒子根据FA 得到的最优值进行位置更新，粒子的搜索范围大幅度减小，有效避免随机初始化粒子位置导致生成的初始值可能不落在可行域的问题，这极大地提高了种群搜索最优值的速度，减少了迭代次数，从而提高了收敛速度。

然后，通过对惯性权重w，学习因子c1、c2的改进，使它们随着迭代次数增加而自适应变化，以实现种群从收敛较快的全局搜索到收敛较慢的局部搜索。同时引入花朵授粉算法的概率切换机制，平衡局部搜索与全局搜索的能力，防止种群因陷入局部搜索导致收敛结果较差。采用beta 分布函数对越界粒子重新设置初始位置，将越界粒子位置重新初始化到具有可行解的搜索范围内，大幅提高了粒子的搜索效率，从而提高HAPSO 的收敛精度。

3.3 DAG调度实验分析

本文DAG 工作流调度实验分为三个部分：工作流完成时间与执行成本权衡最小化对比实验、完成时间对比实验和执行成本对比实验。在完成时间与执行成本权衡最小化对比实验中，实现本文1.5 节提出的优化目标函数f，验证本文提出的HAPSO 性能。同时，为了验证HAPSO 的普适性，分别对工作流的完成时间和执行成本进行实验。

3.3.1 完成时间与执行成本权衡最小化对比实验

本实验在具有10 个虚拟机资源下，对具有不同数量的任务（30，60，100，200，300）构成的具有截止期的DAG 工作流，以工作流的完成时间与执行成本权衡最小化为目标进行调度。针对本文1.4 节提出的工作流截止期约束条件，本实验截止期因子取0.2 以表示DAG 工作流的紧急程度。实验得到的目标值f如图4 所示。

图4 四种算法的权衡最小值f对比Fig.4 Comparison of trade-off minimum values f of four algorithms

图4 的实验表明，相对于WPSO、PSO 和ACO 三种对比算法，HAPSO 实现的工作流调度方案得到的目标值f最小。说明HAPSO 在权衡工作流的完成时间与执行成本最小化方面具有较好的优越性。

同时，为了进一步证明本文所提算法HAPSO 在完成工作流调度时，工作流的完成时间是否满足截止期的要求，本文将本实验得到的工作流完成时间与该工作流的截止期进行对比。将不同DAG 工作流的完成时间以相应截止期为基线1 进行数据标准化，实验结果如图5 所示。

从图5 可以看出，对比四种算法在调度不同的DAG 工作流时，HAPSO 对应的工作流完成时间Makespan小于1，说明HAPSO 实现的工作流调度满足工作流截止期约束条件。

图5 四种算法在不同工作流上的完成时间和截止期对比Fig.5 Comparison of makespans and deadlines for different workflows of four algorithms

本文HAPSO 在实现工作流调度时，根据自适应权重系数权衡工作流的完成时间和执行成本两个冲突目标，有效协调折中了用户与云提供商的需求。通过f可知，HAPSO 在工作流完成时间与执行成本的多目标优化结果上，比PSO 降低了50.4%～81.1%，比WPSO 降低了40.9%～67.5%，比ACO 降低了45.3%～77.1%。PSO 性能低于ACO，但本文对PSO 进行改进，实验表明，改进后的HAPSO 比ACO 性能提高77.1%（以调度由300 个任务构成的DAG 云工作流为例），由此可说明本文所提的HAPSO 很大程度提高了PSO 性能。

在对粒子群改进过程中，采用FA 得到最初的调度方案，粒子根据最初调度方案按照惯性权重及学习因子的自适应动态变化进行迭代，调整DAG 工作流调度方案。同时利用花朵授粉的切换概率机制平衡粒子在寻找最优调度方案时的局部搜索与全局搜索能力，防止粒子在寻找虚拟机资源时易陷入局部最优状态，当粒子位置处于边界时，对其按式（31）进行处理，将粒子转移到可行解当中，避免任务因等待时间太长导致工作流超过截止期的问题。在保证工作流在截止期内完成前提下，确定自适应工作流完成时间与执行成本的权重系数，找到最小值f，实现DAG 工作流调度，将任务分配到合适的虚拟资源节点。

3.3.2 完成时间对比实验

实验中以工作流完成时间为目标，对由不同数量任务构成的DAG 工作流进行调度，得到了不同DAG 工作流完成时间。首先，对10～90 个任务构成的DAG 工作流在5 个虚拟机资源下调度得到的完成时间如图6 所示。接着增加构成DAG 工作流的任务个数至210～290，增加虚拟机的个数至15，得到工作流的完成时间如图7 所示。

图6 DAG完成时间对比（10～90任务数）Fig.6 Comparison of DAG makespan（10～90 tasks）

图7 DAG完成时间对比（210～290任务数）Fig.7 Comparison of DAG makespan（210～290 tasks）

由图6 和图7 的实验结果可看出，随着DAG 工作流的任务数增加，DAG 工作流的完成时间也相应增加。对相同DAG 工作流在相同的虚拟机资源下，HAPSO 的完成时间优化结果均优于其他三种算法，比PSO 减少了15.6%～69.4%，比WPSO 减少了2.5%～48.5%，比ACO 减少了0.8%～53.3%。在虚拟机资源不变的情况下，在任务数较少时，四种算法得到的时间值相差不大。这是由于在相同的DAG 工作流模型下，虚拟机数量与任务数相差不大，HAPSO 的优越性没有得到很好的体现。随着任务数增多，大量的任务根据四种算法得到的调度方案分配到固定数量的虚拟机资源，结果表明，HAPSO 性能优于其他三种算法。由此可知，HAPSO 也能很好地解决以工作流最小化完成时间Makespan为目标的问题。

3.3.3 执行成本对比实验

实验中以工作流执行成本为目标，对由不同数量任务构成的DAG 工作流进行调度，得到了不同DAG 工作流的执行成本。首先，对于10～90 个任务构成的DAG 工作流在5 个虚拟机资源下调度得到的执行成本如图8 所示。

图8 DAG执行成本对比（10～90任务数）Fig.8 Comparison of DAG execution cost（10～90 tasks）

接着增加构成DAG 工作流的任务数至210～290，增加虚拟机的个数至15，得到工作流执行成本如图9 所示。

由图8 和图9 的实验结果可看出，随着DAG 工作流的任务数增加，完成工作流所需的执行成本相应增加，四种算法对相同工作流在具有相同虚拟机资源下进行调度，HAPSO完成的执行成本最小，比PSO 降低了14.9%～48.0%，比WPSO 降低了2.5%～23.8%，比ACO 降低了11.7%～33.3%。在任务数较少时，四种算法的调度策略完成工作流的执行成本并没有明显差距，与工作流的完成时间对比实验结果类似，由于任务数较少，调度策略的结果很难显示出较大差距。随着任务数增多，可选择的调度策略增多，HAPSO 通过FA初始化来提高收敛速度，通过平衡全局搜索与局部搜索能力，避免粒子陷入局部收敛的状态，提高HAPSO 的收敛精度，HAPSO 的寻优能力得到增强。因此，所提算法也能很好地适用于解决最小化工作流执行成本Cost的目标优化问题。

图9 DAG执行成本对比（210～290任务数）Fig.9 Comparison of DAG execution cost（210～290 tasks）

本文针对云工作流完成时间与执行成本的冲突问题，提出了一种混合自适应粒子群工作流调度优化算法HAPSO。该算法能够保证DAG 工作流在截止期内完成前提下，有效权衡云工作流完成时间与执行成本。同时，在优化云工作流完成时间或执行成本的单目标上，HAPSO 都优于WPSO、PSO 和ACO。因此，HAPSO 在优化云工作流调度目标上具有较好的普适性。但是本文用户需求仅考虑了云工作流的完成时间，云提供商的需求只考虑了云工作流的执行成本。因此，本文考虑的因素较少，在未来的研究工作中，将考虑工作流应用程序的可靠性、能耗和安全性等因素对DAG 云工作流调度的影响。

猜你喜欢粒子调度成本2021年最新酒驾成本清单河南电力(2021年5期)2021-05-29《调度集中系统(CTC)/列车调度指挥系统(TDCS)维护手册》正式出版铁道通信信号(2020年10期)2020-02-07基于强化学习的时间触发通信调度方法北京航空航天大学学报(2019年9期)2019-10-26一种基于负载均衡的Kubernetes调度改进算法成都信息工程大学学报(2019年3期)2019-09-25虚拟机实时迁移调度算法三门峡职业技术学院学报(2019年1期)2019-06-27温子仁，你还是适合拍小成本电影(2018年12期)2018-12-23基于粒子群优化的桥式起重机模糊PID控制测控技术(2018年10期)2018-11-25基于粒子群优化极点配置的空燃比输出反馈控制浙江工业大学学报(2017年5期)2018-01-22基于Matlab的α粒子的散射实验模拟物理与工程(2014年4期)2014-02-27基于两粒子纠缠态隐形传送四粒子GHZ态山西大同大学学报(自然科学版)(2014年3期)2014-01-23

推荐访问:工作流 粒子 调度