一种满足可靠性和能效的云工作流调度方法

为了同步解决云工作流调度时的失效和高能耗问题,提出一种基于可靠性和能效的工作流调度算法。算法为了在截止时间的QoS约束下最大化系统可靠性并最小化调度能耗,将工作流调度过程划分为四个阶段:计算任务优先级、工作流任务聚簇、截止时间子分配和任务调度。算法在满足执行次序的情况下对任务进行拓扑排序,并以通信代价最小为目标对任务进行聚簇;将截止时间在任务间进行子分割;以合适的频率/电压等级对聚簇后的任务进行调度,在确保可靠性的前提下最小化系统能耗。通过随机任务图和高斯消除任务图进行综合仿真测试,结果表明算法在降低总体能耗和提高工作流调度可靠性方面均优于对比算法。     

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

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

云科学工作流截止期限约束代价优化调度算法*

针对异构云环境下科学工作流调度的代价优化问题,提出一种基于约束关键路径的代价优化调度算法(CSACCP)。算法以满足截止期限约束同时最小化执行代价为目标,充分考虑云环境和科学工作流的独有特性,设定任务的向上权值,将工作流分解成约束关键路径(CCP)集合。结合首次适应插入算法以减少空闲时隙,改善费用优化效果,采用及时完成和最小费用增长代价的虚拟机选择策略形成备选资源集合。整体分配CCP到最便宜的虚拟机实例,压缩数据通信开销减少工作流的执行代价。通过四种著名的科学工作流仿真测试,结果表明与现有启发式算法相比,CSACCP不仅可以在满足截止期限的约束下得到更小的执行代价,还拥有更高的任务调度成功率。     

一种云工作流任务调度能效优化算法

工作流任务执行时带来的高能耗不仅会增加云资源提供方的经济成本,而且会降低云系统的可靠性。为了满足截止时间的同时,降低工作流执行能耗,提出一种工作流能效调度算法CWEES。算法将能效优化调度划分为三个阶段：初始任务映射、处理器资源合并和任务松驰。初始任务映射旨在通过任务自底向上分级排序得到任务调度初始序列,处理器资源合并旨在通过重用松驰时间合并相对低效率的处理器,降低资源使用数量,任务松驰旨在为每个任务重新选择带有合适电压/频率等级的最优目标资源,在不违背任务顺序和截止时间约束前提下降低工作流执行总能耗。通过随机工作任务模型对算法的性能进行了仿真实验分析。结果表明,CWEES算法不仅资源利用率更高,而且可以在满足截止时间约束下降低工作流执行能耗,实现执行效率与能耗的均衡。     

基于局部关键路径与截止期限分配的云工作流调度算法

为了解决云计算中截止期限约束下的工作流调度代价优化问题,提出一种基于局部关键路径和截止期限分配的工作流任务调度算法。为了满足期限约束,并最小化执行代价,算法将工作流任务的调度过程划分为两个阶段:期限分配阶段和调度资源选择阶段。期限分配阶段定义工作流的局部关键路径,并以递归的方式在局部关键路径上的任务间进行子期限分配;调度资源选择阶段在满足任务子期限的同时,为每个任务选择执行代价最低的资源进行任务调度,以实现调度代价优化。分析算法的时间复杂度,并通过一个算例对算法的实现思路进行了详细阐述。通过科学工作流结构的仿真实验,证明了算法不仅可以满足截止期限约束,而且可以降低工作流任务的执行代价。     

满足实时云任务需求的主动响应式工作流调度模型

为了改善云平台中多工作流调度时的执行代价和资源利用率,提出一种满足实时云任务需求的主动响应式工作流调度算法.该算法可以分别针对新工作流的到达、任务完成后的虚拟机资源提供、紧迫任务到达等做出主动的实时响应调度策略,从而充分利用虚拟机资源的空闲时槽和更大化的任务并行程度,以混合形式调度来自不同工作流的任务.在确保截止期限约束的同时,有效满足实时云任务的调度需求.大量实时工作流的仿真测试表明,与另外几种同类型算法相比,该算法不仅可以降低任务执行代价,而且可以得到更高的资源利用率,实现算法预期效果.     

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

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

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

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

云环境下基于预算分配的科学工作流调度研究

云环境下的科学工作流部署不同于传统的独立任务调度,需同步考虑调度代价与时间问题。为此,提出基于预算分配的科学工作流调度方法,将工作流任务与虚拟机资源间的映射求解分为预算分配和资源提供与调度2个阶段。为优化预算使用,设计基于快优先的预算分配算法(FFTD)和基于慢优先的预算分配算法,实现预算在各任务间的子分配。基于任务最早完成时间的降序排列进行任务选择,在虚拟机可重用的情况下根据单个任务的子预算进行资源分配,保证工作流任务的顺利调度。引入5种常规类型的科学工作流进行实验,测试算法在不同类型工作流结构和不同预算约束下的性能,结果表明,FFTD算法在72%、88%、84%的实验场景中相比BDT-AI算法具有更高的虚拟机资源利用率、预算约束满足率以及更短的调度时间,综合性能更优。     

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

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

云中截止时间动态分配的工作流调度成本优化算法

现如今,如何在满足截止时间约束的前提下降低工作流的执行成本,是云中工作流调度的主要问题之一。三步列表调度算法可以有效解决这一问题。但该算法在截止时间分配阶段只能形成静态的子截止时间。为方便用户部署工作流任务,云服务商为用户提供了的三种实例类型,其中竞价实例具有非常大的价格优势。为解决上述问题,提出了截止时间动态分配的工作流调度成本优化算法(S-DTDA)。该算法利用粒子群算法对截止时间进行动态分配,弥补了三步列表调度算法的缺陷。在虚拟机选择阶段,该算法在候选资源中增加了竞价实例,大大降低了执行成本。实验结果表明,相较于其他经典算法,该算法在实验成功率和执行成本上具有明显优势。综上所述,S-DTDA算法可以有效解决工作流调度中截止时间约束的成本优化问题。     

An Effective Cloud Workflow Scheduling Approach Combining PSO and Idle Time Slot-Aware Rules

Workflow scheduling is a key issue and remains a challenging problem in cloud computing.Faced with the large number of virtual machine(VM)types offered by cloud providers,cloud users need to choose the most appropriate VM type for each task.Multiple task scheduling sequences exist in a workflow application.Different task scheduling sequences have a significant impact on the scheduling performance.It is not easy to determine the most appropriate set of VM types for tasks and the best task scheduling sequence.Besides,the idle time slots on VM instances should be used fully to increase resources'utilization and save the execution cost of a workflow.This paper considers these three aspects simultaneously and proposes a cloud workflow scheduling approach which combines particle swarm optimization(PSO)and idle time slot-aware rules,to minimize the execution cost of a workflow application under a deadline constraint.A new particle encoding is devised to represent the VM type required by each task and the scheduling sequence of tasks.An idle time slot-aware decoding procedure is proposed to decode a particle into a scheduling solution.To handle tasks'invalid priorities caused by the randomness of PSO,a repair method is used to repair those priorities to produce valid task scheduling sequences.The proposed approach is compared with state-of-the-art cloud workflow scheduling algorithms.Experiments show that the proposed approach outperforms the comparative algorithms in terms of both of the execution cost and the success rate in meeting the deadline.     

Energy-efficient Tasks Scheduling Heuristics with Multi-constraints in Virtualized Clouds

Reducing energy consumption has become an important task in cloud datacenters. Many existing scheduling approaches in cloud datacenters try to consolidate virtual machines (VMs) to the minimum number of physical hosts and hence minimize the energy consumption. VM live migration technique is used to dynamically consolidate VMs to as few PMs as possible; however, it introduces high migration overhead. Furthermore, the cost factor is usually not taken into account by existing approaches, which will lead to high payment cost for cloud users. In this paper, we aim to achieve energy reduction for cloud providers and payment saving for cloud users, and at the same time, without introducing VM migration overhead and without compromising deadline guarantees for user tasks. Motivated by the fact that some of the tasks have relatively loose deadlines, we can further reduce energy consumption by proactively postponing the tasks without waking up new physical machines (PMs). A heuristic task scheduling algorithm called Energy and Deadline Aware with Non-Migration Scheduling (EDA-NMS) algorithm is proposed, which exploits the looseness of task deadlines and tries to postpone the execution of the tasks that have loose deadlines in order to avoid waking up new PMs. When determining the VM instant types, EDA-NMS selects the instant types that are just sufficient to guarantee task deadline to reduce user payment cost. The results of extensive experiments show that our algorithm performs better than other existing algorithms on achieving energy efficiency without introducing VM migration overhead and without compromising deadline guarantees.     

虚拟云下满足多重约束的时限敏感任务调度算法

目前以虚拟云服务平台作为强大计算平台的虚拟云环境下,许多现存调度方法致力于合并虚拟机以减少物理机数目,从而达到减少能源消耗的目的,但会引入高额虚拟机迁移成本;此外,现存方法也没有考虑导致用户高额支付成本的成本因子影响。以减少云服务提供者能源消耗和云服务终端用户支付成本为目标,同时保障用户任务的时限要求,提出一种能源与时限可感知的非迁移调度（EDA-NMS）算法。EDA-NMS利用任务时限的松弛度,延迟宽松时限任务的执行从而无需唤醒新的物理机,更无需引入虚拟机动态迁移成本,以达到减少能源消耗的目的。多重扩展实验结果表明,EDA-NMS采用成本和能耗有效的虚拟机实例类型组合方案,与主动及响应式调度（PRS）算法相比,在减少静态能耗的同时,能更有效地满足用户关键任务的敏感时限并确保用户支付成本最低。     

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

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

A multi-objective reinforcement learning algorithm for deadline constrained scientific workflow scheduling in clouds

Recently, a growing number of scientific applications have been migrated into the cloud. To deal with the problems brought by clouds, more and more researchers start to consider multiple optimization goals in workflow scheduling. However, the previous works ignore some details, which are challenging but essential. Most existing multi-objective workflow scheduling algorithms overlook weight selection, which may result in the quality degradation of solutions. Besides, we find that the famous partial critical path (PCP) strategy, which has been widely used to meet the deadline constraint, can not accurately reflect the situation of each time step. Workflow scheduling is an NP-hard problem, so self-optimizing algorithms are more suitable to solve it.In this paper, the aim is to solve a workflow scheduling problem with a deadline constraint. We design a deadline constrained scientific workflow scheduling algorithm based on multi-objective reinforcement learning (RL) called DCMORL. DCMORL uses the Chebyshev scalarization function to scalarize its Q-values. This method is good at choosing weights for objectives. We propose an improved version of the PCP strategy calledMPCP. The sub-deadlines in MPCP regularly update during the scheduling phase, so they can accurately reflect the situation of each time step. The optimization objectives in this paper include minimizing the execution cost and energy consumption within a given deadline. Finally, we use four scientific workflows to compare DCMORL and several representative scheduling algorithms. The results indicate that DCMORL outperforms the above algorithms. As far as we know, it is the first time to apply RL to a deadline constrained workflow scheduling problem.