多维QoS约束的云计算工作流调度算法

为有效解决云计算异构系统中工作流调度问题,提出一种多维QoS约束下的改进遗传算法(QoS-IGA)。建立工作流任务调度模型、多维QoS约束模型和考虑任务完成时间、完成费用及虚拟资源可靠性和负载均衡度的多目标优化函数;提出种群初始化原则,以及不破坏任务间依赖关系的交叉与变异算子,引入模拟退火算法的Metropolis准则避免遗传算法的早熟收敛问题。实验结果表明,QoS-IGA算法有效可行,其收敛速度快,调度效率高。

一种改进樽海鞘群算法及其多目标云工作流调度应用

为了优化云工作流应用的调度效率与代价,提出基于改进樽海鞘群算法的工作流调度策略。建立截止时间与预算约束的多目标优化模型,利用樽海鞘觅食的位置变化对工作流调度进行编解码,设计融合执行跨度与执行代价的权重适应度函数。为了增强樽海鞘群的寻优性能,引入基于疯狂算子的领导者更新模式,通过疯狂变量,减少领导者更新的停滞早熟现象;引入遗传算子的追随者更新模式,利用个体交叉和变异使樽海鞘群具有更均衡的搜索全局性和个体多样性,避免陷入局部最优。结果证明,改进樽海鞘群算法可以有效提升计算精度和收敛速度;应用于工作流调度求解后,其调度解收敛性更好,调度解集空间分布更加一致。

云中使用竞价实例的截止时间约束的工作流调度优化算法

近年来,由于按需资源供应和即付即用付费模式具有的明显优势,在云环境中执行大规模工作流应用程序越来越流行。云服务提供商以不同的价格提供不同性能的资源。为了提高资源的利用率,许多云服务商提供的瞬时资源的价格远低于正常资源的价格,Amazon EC2提供的竞价实例,可以大大降低工作流的执行成本。云中工作流调度的主要问题之一是在满足用户给定的截止时间约束的前提下,找到一种更廉价的调度方法。为解决这个问题,提出了一种使用竞价实例的截止时间约束工作流调度优化算法(Spot-ProLis)。该算法考虑了同一虚拟机上数据传输时长为零的情况,使用概率向上排序的方法对任务进行排序。在资源配置阶段,增加了竞价实例作为候选资源,有效降低了执行成本。实验结果表明,相比经典算法ProLis,所提算法在降低执行成本上具有显著优势。

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

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

最后期限动态分配的三步云工作流调度算法

现如今,云环境中的工作流调度问题依然很有挑战性.它的一个重要任务是找到一种能够满足最后期限约束且执行成本最优的调度方案.三步的列表调度算法可以有效地解决这一问题.该算法首先将最后期限分配到每个任务,形成任务子期限;之后再利用两步列表调度策略为每个任务分配资源.然而现有的最后期限分配策略均只能形成静态的子期限,因此还可以进行进一步的优化.本文采用三步列表调度算法进行云工作流调度,并提出一种基于粒子群的动态最后期限分配方法(DY-DD).实验结果表明,相比于其它经典调度算法,本文提出的算法在成功率和执行成本上均具有优势.

多vCPU环境中基于容器的科学工作流调度策略

现有科学工作流调度研究较少考虑计算资源的多道程序设计,难以同时实现有效的容器共享并优化任务并行度与资源利用率。为了解决以上难点,文章提出了一种分布式多vCPU环境中基于容器技术的分段式工作流调度策略。该策略通过分段调度方法,降低启发式算法的解空间大小,使用带遗传算子的自适应离散粒子群优化算法(ADPSOGA),在设备使用成本的约束下优化各个工作流的完成时间,并制定一种容器与设备间的动态伸缩方案,实现容器的复用并解决单个设备中任务并行时的资源争用问题。结果表明:ADPSOGA的性能优于其他同类启发式算法,并且分段调度方法与容器伸缩方案在工作流调度方面表现出良好的性能,能很好地适应因任务并行度增加所带来的影响。

网格工作流调度研究综述

阐述了工作流调度的基本概念和调度的相关知识,分析了目前流行的网格工作流的调度算法的优缺点,并对当前的网格系统和项目所采用的调度机制,从不同侧面对其进行了比较分析。随着服务网格的日益流行,提出了面向服务网格环境下的服务工作流调度,分析了调度中的关键问题,并给出了解决问题的方法和思路。

时间约束云工作流调度的粒子群搜索方法

为了快速找到较优的调度方案,针对时间约束工作流调度问题,即能在满足用户的截止时间约束的条件下最小化调度费用,提出基于粒子群算法的最优调度方案搜索方法。利用关键路径进行粒子初始化和搜索阶段的筛选处理,不但能够显著提高搜索结果的精度,而且减少了搜索的计算时间。将改进算法和传统粒子群优化算法进行了实验评估对比,实验数据证明,使用该方法使粒子搜索的时间少于传统粒子群算法,并且结果也优于传统方法。

基于混沌遗传算法的网格工作流调度应用

动态网格环境中,多QoS(服务质量)约束下的工作流调度问题是决定其任务执行成功与否及效率高低的关键。现有的网格工作流调度算法难以满足实际应用中的不同需求,同时算法欠优化,难以提供多种策略,由此提出了一种基于期限与预算两个QoS约束的改进型混沌遗传算法。首先,为避免算法出现收敛停滞将混沌机制引入遗传算法并对变异概率进行自适应处理。其次,提出时间和预算的线性结合概念,将目标函数转换为适应值函数。最终基于工作流调度中的平衡结构和非平衡结构测试了算法的有效性。

考虑信息安全因素的多目标云工作流调度

为了满足云工作流调度需求的多样性,构建了考虑信息安全因素和多实例工作流执行时长的云工作流调度模型。该模型主要考虑了保密性、完整性与真实性3种信息安全因素的时间开销,以及无决策偏好情况下的信息安全风险概率度量。为了提升调度优化效果,提出工作流实例中任务调度的优先级确定规则和考虑信息安全因素的虚拟机分配规则,并将这两个启发式规则与NSGA-Ⅱ算法相融合,对上述模型进行了优化求解。实验结果表明,所提算法可以较好地实现工作流执行结束时间与信息安全风险概率两个目标的平衡,亦可提高优化结果的质量。

基于混合粒度冲突检测的事务工作流调度算法

事务工作流由若干个平面事务组成,其执行满足松弛原子性.由于组成事务工作流的平面事务具有不同的完成特性,为了防止不可串行化的执行,现有的调度算法通常只允许一个活动工作流执行不可补偿事务,这大大限制了并发度.定义了基于事务类型和事务实例两种粒度的冲突关系,并提出了一种基于这两种粒度冲突检测的调度算法,保证了并发事务工作流的可串行化和可恢复执行.该算法从两个方面提高了并发度:一方面通过事务实例之间(细粒度)的冲突检测减少了工作流冲突的概率;另一方面通过事务类型之间(粗粒度)的冲突预测,允许多个将来不冲突的工作流执行不可补偿事务.

QoS约束下基于双向分层的网格工作流调度算法

为使网格工作流的执行满足用户QoS要求,应用有向无环图描述工作流,并分析其中的关键活动,把用户对工作流的整体QoS约束分割为对单个任务的QoS约束。以此为基础,提出了一种基于双向分层的网格工作流调度算法Q-TWS。该算法通过对工作流正向分层和逆向分层,可以方便并准确找到任务之间的并行关系。Q-TWS可最大程度放松对任务执行时间的约束,在增加调度灵活性的同时又满足用户的QoS要求。实验表明,Q-TWS算法与TL算法相比,在同样的截止时间约束下,工作流执行时间较短,且工作流执行费用较小。

移动边缘计算环境下面向安全和能耗感知的服务工作流调度方法

在移动边缘计算(MEC)环境中,用户将应用任务迁移至MEC端执行可以有效降低延时并减少能耗。然而,MEC环境面临潜在的恶意攻击,这些攻击可能导致隐私数据的丢失或泄露。基于此,提出了面向安全和能耗感知的服务工作流调度方法(SEA),该算法能在满足移动应用的风险率和截止时间限制条件下,最小化移动设备的能耗。SEA是基于粒子群优化算法,在编码中考虑了任务的调度位置、机密性服务和完整性服务。此外,还构建了新的安全模型,分别包括数据量、多核CPU、计算频率与安全开销之间的关系。最后,通过仿真实验证明了所提算法的可行性与有效性。

基于资源状态可靠度的网格工作流调度算法

针对执行时间限制严格类型的DAG类型网格工作流提出一种新的基于资源状态可靠度的网格工作流调度算法。该算法根据用户提交的工作流执行时间要求,利用Chapman-Kolmogorov向后方程来计算出DAG图中关键路径上各资源在任务到达时刻均处于"闲状态"的概率大小,然后选择一组资源组合的状态可靠度大于用户要求的信任度置信水平且总费用较低的一组资源。最后通过实验验证了该算法的有效性。

基于期限约束与关键路径的云工作流调度

为优化云工作流任务的调度过程,提出基于期限约束与关键路径的工作流调度算法WS-DCCP。结合云资源的异质与弹性特征对任务进行逻辑分层,在此基础上,正比例重分配工作流期限,通过改进的任务升秩与降秩值之和赋予任务优先级,并根据任务优先级构造工作流的约束关键路径,将约束关键路径上的任务集调度至同一资源以降低通信代价。在满足约束关键路径子期限的条件下寻找执行代价最小化的资源,进而获得满足期限约束的代价最小调度解。仿真结果表明,与IC-PCP算法和JIT算法相比,WS-DCCP算法可以在满足期限约束的同时降低工作流调度代价,提高调度成功率。

云环境下一种多维QoS约束的工作流调度算法

云计算以用户为中心按需提供服务,云环境下必须关注用户的服务质量(QoS).云计算工作流调度的QoS目标约束条件,不仅有工作流完成时间,还包括调度预算、系统的可靠性以及安全性等,多维QoS约束的工作流调度算法的研究至关重要.为此,提出一种基于生物共生演算法(symbiotic organisms search,SOS)的多维QoS约束的工作流调度算法(QoS-SOS).首先为工作流中的每个任务分配适当的优先级,将非支配解的思想融入到生物共生演算法中,从而获得分布均匀的Pareto最优解集来解决多维QoS约束的工作流调度问题.实验结果表明,QoS-SOS不仅拥有较快的收敛速度,而且有很好的寻优能力,还能够根据用户的偏好选择侧重不同的优化方案,从而适应于大规模的云环境.

带准备时间和截止期约束的云服务工作流调度算法

带准备时间和截止期约束的云服务工作流费用优化是一个新的云计算资源优化分配问题。分析该NP-hard问题特征,建立相应的整数规划数学模型。构建有效的变量取值概率模型和更新机制,提出高质量初始群体的启发式生成方法;提出混合的分布估计算法(HEDA),引入个体向全局最优解学习的策略,提高算法的全局搜索和局部优化能力。模拟实验结果表明此提出的方法在合理的CPU时间内可有效减少工作流费用。

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

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

基于格分布方差的多目标云工作流调度算法

提出了基于格分布方差的多目标云工作流调度算法和差粒子自学习策略。首先,考虑任务调度的特性,进行粒子编码离散化。其次,利用Pareto最优工作流调度解集映射到自适应网格坐标系的策略,计算网格坐标系中每个Pareto最优解的格分布量。再次,采用格分布方差评估当前Pareto前端的多样性程度,并动态调整进化策略。最后,设计了差粒子自学习策略。仿真实验表明,通过该算法得到的工作流调度解集,在IGD和S性能指标上均优于MOPSO算法,在最优值方面优于ε-FDPSO和NSGA-Ⅱ算法。

基于并行分层的工作流调度优化算法

针对给定截止时间约束下用有向无环图描述的工作流时间费用优化问题,逆向分层算法未考虑工作流中各个任务在实际执行过程中的并行性而带来相对较多的时间碎片,提出一种基于并行分层的工作流调度算法——并发级别工作流调度算法。该算法将工作流在实际执行过程中的某个任务和其他一个(或具有依赖关系的相邻多个)并行执行的任务尽量划分到同一层,并根据各层的并行度分配冗余时间,对每层中存在具有依赖关系的多个相邻任务采用Markov决策过程算法进行时间费用优化。对平衡结构和非平衡结构的有向无环图所描述的工作流进行大量模拟实验,对比最小临界路径算法、逆向分层算法和期限顶级算法,实验结果表明所提算法具有较显著的优势。