满足帕累托最优的多目标云工作流调度算法

为了同步考虑用户的任务QoS需求和云资源提供方的收益,提出一种云环境中满足帕累托最优的多目标最优化DAG(Directed Acyclic Graph)粒子群算法MODPSO(Multi-objective DAG Particle Swarm Optimization)。综合考虑任务执行跨度、执行代价与执行能耗的三目标同步最优化,设计基于DVFS的离散PSO调度优化方法。重新定义PSO的种群粒子进化过程和更新规则,进而得到多目标优化工作流调度解。通过人工合成工作流和现实科学工作流进行仿真测试,并对算法性能进行分析。结果表明,该算法可以通过非支配集的方式实现冲突多目标的调度优化求解。在满足用户QoS的同时,得到最优解的Pareto边界集,实现调度性能与系统能耗的均衡。     

不确定性云环境工作流调度多目标优化

云计算弹性的资源提供和虚拟机性能的不稳定性使得工作流的执行面临诸多不确定性.针对此问题,考虑执行时间具有不确定性,基于执行时间和代价的同步优化,提出同步满足健壮性的三目标优化工作流调度算法.以满足帕累托最优的均衡最优解集的形式进行建模,以启发式方式对模型求解.为衡量均衡解的质量,设计基于超体积的评估机制,得到冲突目标的均衡调度解,比原始双目标优化对执行时间的波动具有更小敏感性.实验结果表明,比较未考虑不确定性的双目标优化,该算法求解质量更高,均衡度更好,更符合不确定性实时云工作流调度.     

云环境中基于混合多目标粒子群的科学工作流调度算法

为了更高效地实现科学工作流任务的调度,研究了云环境中的工作流调度多目标优化问题,提出了一种基于非占优排序的混合多目标粒子群优化的工作流调度算法HPSO。首先,建立了截止时间与预算约束下工作流调度的多目标优化模型,模型引入三目标最优化,包括工作流执行跨度、执行代价及执行能耗;其次,设计了一种混合粒子群算法对相互冲突的三目标最优化进行求解,算法通过非占优排序的形式可以得到满足Pareto最优的工作流调度解集合;最后,通过3种科学工作流案例的仿真实验,与同类多目标调度算法NSGA-II,MOPSO和ε-Fuzzy进行了性能比较。实验结果表明,HPSO得到的调度解不仅收敛性更好,而且调度解的空间分布更加一致,更符合云环境中的工作流调度优化。     

融合遗传和粒子群算法的云工作流调度算法

针对云工作流调度问题,提出一种融合遗传算法和粒子群优化算法的工作流调度负载均衡算法.充分利用多元启发式方法融合的优势,避免遗传算法的收敛过慢和粒子群算法易于陷入局部最优的缺陷,有效将工作流任务映射至虚拟机资源,实现全局工作流执行跨度最小化和虚拟机分配的负载均衡.以算例详细说明算法实现思路,在现实科学工作流条件下进行仿真测试,验证算法性能.与几种单一元启发式调度方法相比,验证该算法拥有更高执行效率和负载均衡度.     

基于均衡适应度的云工作流调度算法

针对工作流任务调度优化问题,提出一种云工作流任务调度遗传算法。为了寻找工作流执行时间与执行代价的同步最优解,建立了遗传调度模型。在个体编码方面,采用了一种二维排列编码方法,可以更好地展现工作流任务间的执行次序;综合考虑任务执行代价与最早完成时间两个因素,设计了一种均衡适应度函数;为了丰富种群个体多样性,引入三种遗传交叉操作和两种遗传变异操作,以产生新的个体,增加了最优解的求解概率。通过数值仿真实验,在多个性能指标上对算法进行分析。结果表明,该调度算法能更好地平衡执行代价与调度效率,性能优于同类算法。     

多目标最优化云工作流调度进化遗传算法

为了实现云环境中科学工作流调度的执行跨度和执行代价的同步优化,提出了一种多目标最优化进化遗传调度算法MOEGA。该算法以进化遗传为基础,定义了任务与虚拟机映射、虚拟机与主机部署间的编码机制,设计了满足多目标优化的适应度函数。同时,为了满足种群的多样性,在调度方案中引入了交叉与变异操作,并使用启发式方法进行种群初始化。通过4种现实科学工作流的仿真实验,将其与同类型算法进行了性能比较。结果表明,MOEGA算法不仅可以满足工作流截止时间约束,而且在降低任务执行跨度与执行代价的综合性能方面也优于其他算法。     

云环境中基于分解的多目标工作流调度算法

云服务提供商在给用户提供海量虚拟资源的同时,也面临着一个现实的问题,即怎样调度这些资源,以最小的代价(完工时间、执行费用、资源利用率等)完成工作流的执行。针对IaaS环境下的工作流调度问题,以完工时间和执行费用作为目标,提出了一种基于分解的多目标工作流调度算法。该算法结合了基于列表的启发式算法和多目标进化算法的选择过程,采用一种分解方法,将多目标优化问题分解为一组单目标优化子问题,然后同时求解这些单目标子问题,使得调度过程更为简单有效。算法利用天马项目发布的现实世界中的工作流进行实验,结果表明,和MOHEFT算法以及NSGA-II*算法相比较,所提出的算法能得到更优的Pareto解集,同时具有更低的时间复杂度。     

DAG分割模型下的云工作流调度策略

为了优化云工作流调度的经济代价和执行效率,提出一种基于有向无循环图（DAG）分割的工作流调度算法PBWS。以工作流调度效率与代价同步优化为目标,算法将调度求解过程划分为三个阶段进行：工作流DAG结构分割、分割结构调整及资源分配。工作流DAG结构分割阶段在确保任务间执行顺序依赖的同时求解初始的任务分割图;分割结构调整阶段以降低执行跨度为目标,在不同分割间对任务进行重分配;资源分配阶段旨在选择代价最高效的任务与资源映射关系,确保资源的总空闲时间最小。利用五种科学工作流DAG模型对算法进行了仿真实验。结果表明。PBWS算法仅以较小的执行跨度为开销,极大降低了工作流执行代价,实现了调度效率与调度代价的同步优化,其综合性能是优于同类型算法的。     

QoS约束云环境下的工作流能效调度算法

云环境可以为大规模工作流的执行提供高效、可靠的运行环境,但工作流执行时带来的高能耗不仅会增加云资源提供方的经济成本,还会影响云系统的可靠性,并对环境产生不利影响。为了在满足用户截止时间QoS需求的同时降低云环境中工作流调度的执行能耗,提出一种工作流能效调度算法QCWES。该算法将工作流的能效调度方案求解划分为3个阶段:截止时间重分配、任务调度选择排序以及基于DVFS的最佳资源选择。截止时间重分配阶段旨在将用户定义的全局工作流截止时间在各个任务间进行重分配,任务调度选择排序阶段旨在通过自顶向下的任务分级方式得到任务调度序列;基于DVFS的最佳资源选择阶段旨在为每个任务选择带有合适电压/频率等级的最优目标资源,在满足任务的子截止时间的前提下使总体能耗达到最小。通过随机工作流和基于高斯消元法的现实工作流结构,对算法的性能进行仿真实验分析。结果表明,所提算法可以在满足截止时间约束下降低工作流的执行能耗,实现用户方的QoS需求与资源方的能耗间的均衡。     

一种可靠性驱动的云工作流调度遗传算法

为了解决云环境中工作流调度的可靠性问题,提出了一种基于可靠性驱动信誉度模型的工作流调度遗传算法RDR-GA。算法以工作流执行跨度makespan与可靠性最优化为目标,设计了一种基于时间依赖的可靠性驱动信誉度模型,通过该模型可以有效评估资源可靠性。同时,为了寻找遗传最优解,算法设计了新的遗传进化和评估机制,包括：1)以进化算子对调度解中的任务-资源映射进行遗传进化;2)以两阶段MAX-MIN策略评估并决定调度解的任务执行序列。仿真实验结果表明,满足可靠性驱动的信誉度算法不仅能够以更精确的信誉度改善工作流应用执行可靠性,而且能够以比同类遗传算法更快的收敛速度得到进化更优解。     

基于云科学工作流调度的代价与能效优化算法

为了降低云环境中科学工作流调度的执行代价与数据中心能耗,提出了一种基于能效感知的工作流调度代价最优化算法CWCO-EA。算法在满足截止时间约束下,以最小化工作流执行代价与降低能耗为目标,将工作流的任务调度划分为四步执行。首先,通过代价效用的概念设计虚拟机选择策略,实现了子makespan约束下的任务与最优虚拟机间的映射;其次,通过串行与并行任务合并策略,同步降低了工作流的执行代价与能耗;然后,通过空闲虚拟机重用机制,改善了租用虚拟机的利用率,进一步提高了能效;最后,通过任务松驰策略实现了租用虚拟机的能力回收,节省了能耗。通过四种科学工作流的仿真实验,结果表明,CWCO-EA算法比较同类型算法,在满足截止时间的同时,可以同步降低工作流的执行代价与执行能耗。     

基于自适应惩罚函数的云工作流调度协同进化遗传算法

云计算为大规模科学工作流应用的执行提供了更高效的运行环境。为了解决云环境中科学工作流调度的代价优化问题,提出了一种基于协同进化的工作流调度遗传算法CGAA。该算法将自适应惩罚函数引入严格约束的遗传算法中,通过协同进化的方法,自适应地调整种群个体的交叉与变异概率,以加速算法收敛并防止种群早熟。通过4种科学工作流的仿真实验结果表明,CGAA算法得到的调度方案在满足工作流调度截止时间约束与降低任务执行代价的综合性能方面优于同类型算法。     

一种多重约束下确保成功率的云工作流调度方法

为提高多重约束下的调度成功率,提出一种满足期限和预算双重约束的云工作流调度算法。将可行工作流调度方案求解分解为工作流结构分层、预算分配、期限分配、任务选择和实例选择。工作流结构分层将所有工作流任务划分层次形成包任务,以提高并行执行程度;预算分配对整体预算在层次间进行分割;期限分配将全局期限在不同层次间分割;任务选择基于任务最早开始时间确定优先级,得到任务调度次序;实例选择根据时间和代价均衡因子,获取任务执行最佳实例。仿真结果证明,该算法在调度成功率、同步优化工作流执行时间与执行代价上相较对比算法更好。     

A hybrid instance-intensive workflow scheduling method in private cloud environment

Aiming to solve the problem of instance-intensive workflow scheduling in private cloud environment, this paper first formulates a scheduling optimization model considering the communication time between tasks. The objective of this model is to minimize the execution time of all workflow instances. Then, a hybrid scheduling method based on the batch strategy and an improved genetic algorithm termed fragmentation based genetic algorithm is proposed according to the characters of instance-intensive cloud workflow, where task priority dispatching rules are also taken into account. Simulations are conducted to compare the proposed method with the canonical genetic algorithm and two heuristic algorithms. Our simulation results demonstrate that the proposed method can considerably enhance the search efficiency of the genetic algorithm and is able to considerably outperform the compared algorithms, in particular when the number of workflow instances is high and the computational resource available for optimization is limited.

     

移动云计算中基于延时传输的多目标工作流调度

云计算和移动互联网的不断融合,促进了移动云计算的产生与发展.在移动云计算环境下,用户可将工作流的任务迁移到云端执行,这样不但能够提升移动设备的计算能力,而且可以减少电池能源消耗.但是不合理的任务迁移会引起大量的数据传输,这不仅损害工作流的服务质量,而且会增加移动设备的能耗.基于此,本文提出了基于延时传输机制的多目标工作流调度算法MOWS-DTM.该算法基于遗传算法,结合工作流的调度过程,在编码策略中考虑了工作流任务的调度位置和执行排序.由于用户在不断移动的过程中,移动设备的无线网络信号也在不断变化.当传输一定大小的数据时,网络信号越强则需要的时间越少,从而移动设备的能耗也越少.而且工作流结构中存在许多非关键任务,延长非关键任务的执行时间并不会对工作流的完工时间造成影响.因此,本文在工作流调度过程中融入了延时传输机制DTM,该机制能够同时有效地优化移动设备的能耗和工作流的完工时间.仿真结果表明,相比MOHEFT算法和RANDOM算法,MOWS-DTM算法在多目标性能上更优.     

Cost-Time Efficient Scheduling Plan for Executing Workflows in the Cloud

The emergence of Cloud Computing as a model of service provisioning in distributed systems instigated researchers to explore its pros and cons on executing different large scale scientific applications, i.e., Workflows. One of the most challenging problems in clouds is to execute workflows while minimizing the execution time as well as cost incurred by using a set of heterogeneous resources over the cloud simultaneously. In this paper, we present, Budget and Deadline Constrained Heuristic based upon Heterogeneous Earliest Finish Time (HEFT) to schedule workflow tasks over the available cloud resources. The proposed heuristic presents a beneficial trade-off between execution time and execution cost under given constraints. The proposed heuristic is evaluated for different synthetic workflow applications by a simulation process and comparison is done with state-of-art algorithm i.e. BHEFT. The simulation results show that our proposed scheduling heuristic can significantly decrease the execution cost while producing makespan as good as the best known scheduling heuristic under the same deadline and budget constraints.     

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

针对具有截止期的云工作流完成时间与执行成本冲突的问题,提出一种混合自适应粒子群工作流调度优化算法（HAPSO）。首先,基于截止期建立有向无环图（DAG）云工作流调度模型;然后,通过范数理想点与自适应权重的结合,将DAG调度模型转化为权衡DAG完成时间和执行成本的多目标优化问题;最后,在粒子群优化（PSO）算法的基础上引入自适应惯性权重、自适应学习因子、花朵授粉算法的概率切换机制、萤火虫算法（FA）和粒子越界处理方法,从而平衡粒子群的全局搜索与局部搜索能力,进而求解DAG完成时间与执行成本的目标优化问题。实验中对比分析了PSO、惯性权重粒子群算法（WPSO）、蚁群算法（ACO）和HAPSO的优化结果。实验结果表明,HAPSO在权衡工作流（30～300任务数）完成时间与执行成本的多目标函数值上降低了40.9%～81.1%,HAPSO在工作流截止期约束下有效权衡了完成时间与执行成本。此外,HAPSO在减少完成时间或降低执行成本的单目标上也有较好的效果,验证了HAPSO的普适性。     

基于代价优化的云工作流调度改进PSO算法

云计算可以通过即付即用的方式向用户工作流提供资源。为了解决资源服务代价异构环境下的云工作流任务调度代价问题,提出一种基于改进粒子群算法的云工作流任务调度算法WSA-IPSO。通过综合考虑任务的执行代价和依赖任务间发生数据传输时的通信代价,算法将总代价优化问题形式化为有向无环图DAG中的任务调度模型,并提出基于改进粒子群算法的优化模型对其进行求解。通过改进传统粒子群算法的粒子速度更新策略和惯性权重更新策略,算法可以以更快的收敛速度得到代价最小化的调度方案。通过仿真实验,与MCT算法及标准粒子群算法进行性能比较。实验结果表明,WSA-IPSO算法在降低总代价、任务分布的负载均衡以及算法收敛性方面比较同类算法均表现出更好的性能。