基于改进遗传算法的工作流调度研究

在资源受限工作流系统中,任务的执行顺序和资源分配对工作流执行时间有很大影响。文中就此问题提出了一种新的方法,把工作流调度分为计划和执行两个阶段,先运用改进的遗传算法对工作流系统中的任务执行顺序和资源分配做好全局优化,然后再按照计划执行,达到执行时间最短的目的。实验结果表明,与动态工作流调度方法以及标准遗传算法比较,在相同工作流中,当存在并发执行的任务时,基于改进后的遗传算法的调度方法能够做到全局资源分配最优,使得整个工作流系统在执行时间方面最短。     

基于改进遗传算法的工作流调度研究

在资源受限工作流系统中,任务的执行顺序和资源分配对工作流执行时间有很大影响.文中就此问题提出了一种新的方法,把工作流调度分为计划和执行两个阶段,先运用改进的遗传算法对工作流系统中的任务执行顺序和资源分配做好全局优化,然后再按照计划执行,达到执行时间最短的目的.实验结果表明,与动态工作流调度方法以及标准遗传算法比较,在相同工作流中,当存在并发执行的任务时,基于改进后的遗传算法的调度方法能够做到全局资源分配最优,使得整个工作流系统在执行时间方面最短.     

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

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

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

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

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

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

算力网络环境下基于势博弈的工作流任务卸载优化机制

边缘计算虽然部分解决了任务上云导致的时延过长的问题,但由于通常只考虑端边云间的垂直协同,不可避免出现了“算力孤岛”效用,因而仍然难以满足工作流任务的低延迟执行需求.为了高效协同利用广域网上的算力资源,降低工作流任务的执行时间,亟需对算力网络中的工作流任务卸载和资源分配问题进行研究.首先描述了算力网络环境下面向多用户的工作流任务执行场景,并对该场景下的网络环境、工作流任务及其执行流程进行建模.其次根据优化目标建立工作流执行时延模型,以构建面向算力网络环境的多用户工作流任务卸载与资源分配问题.最后根据工作流应用的特点,针对链式工作流提出了一种基于势博弈的分布式工作流卸载算法.针对复杂DAG工作流提出一种基于动态资源权重的启发式工作流卸载算法.仿真实验表明,与其他算法相比,所提算法均能够协同广域网上的算力与网络资源,降低工作流任务的平均完成时间,从而有效提高了算力网络环境中的工作流任务的执行效率.     

允许违反局部时间约束的科学工作流调度策略

提高科学工作流在云环境中的执行效率、降低执行费用受到广泛关注。用户期望的局部QoS约束与工作流的总体执行效率之间往往存在矛盾。针对该现象,在前期的研究基础上提出一种允许违反局部时间约束的科学工作流调度策略。通过对已聚簇的工作流任务集使用任务后向优先合并的方法,可实现任务间空闲时间片的合理利用,进而优化科学工作流的执行时间;另外,为充分利用任务的松弛时间,提高工作流的整体执行效率,允许部分任务的调度违反局部最晚完成时间的约束。实验结果表明,该策略能提前科学工作流的最早完成时间,提高处理机的利用率,并最终降低工作流的执行费用。     

云环境下基于聚簇的科学工作流执行优化策略

基于云环境下的科学工作流,以提高处理机利用率、降低费用为目标,提出了一种基于聚簇的执行优化策略。该策略首先基于合理的任务复制和分簇,以实现关键任务的尽早调度;在此基础上,对任务簇再次进行聚集,以充分利用任务簇中任务间可能的空闲时间。实验表明,该策略能够提高任务的并行度,提前工作流的最早完成时间,并且在提高处理机的利用率和降低科学工作流的执行费用方面有显著效果。     

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

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

基于工作流的分布式协同计划控制架构研究*

从协同的角度研究了制造业在分布式协同制造企业环境下所面临的相关技术问题,提出了基于工作流的分布式协同计划控制架构。该架构分为两层,在企业层对所有协同机构的生产任务进行动态的协同优化调度;在车间层对有限资源在需求约束下进行优化调度。应用扩展的工作流概念和功能去正确地管理活动序列,建立了资源管理、活动调度以及任务协同调度的优化模型。最后,提出了基于规则的更新处理组件用于提高系统自动化程度。     

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

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

云计算环境中面向DAG任务的多目标调度算法

为了实现任务执行效率与执行代价的同步优化,提出了一种云计算环境中的DAG任务多目标调度优化算法。算法将多目标最优化问题以满足Pareto最优的均衡最优解集合的形式进行建模,以启发式方式对模型进行求解;同时,为了衡量多目标均衡解的质量,设计了基于hypervolume方法的评估机制,从而可以得到相互冲突目标间的均衡调度解。通过配置云环境与三种人工合成工作流和两种现实科学工作流的仿真实验测试,结果表明,比较同类单目标算法和多目标启发式算法,算法不仅求解质量更高,而且解的均衡度更好,更加符合现实云的资源使用特征与工作流调度模式。     

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

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

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

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

Science in the Cloud: Allocation and Execution of Data-Intensive Scientific Workflows

An important challenge for the adoption of cloud computing in the scientific community remains the efficient allocation and execution of data-intensive scientific workflows to reduce execution time and the size of transferred data. The transferred data overhead is becoming significant with emerging scientific workflows that have input/output files and intermediate data products ranging in the hundreds of gigabytes. The allocation of scientific workflows on public clouds can be described through a variety of perspectives and parameters, and has been proved to be NP-complete. This paper proposes an evolutionary approach for task allocation on public clouds considering data transfer and execution time. In our framework, a solution is represented using an allocation chromosome that encodes the allocation of tasks to nodes, and an ordering chromosome that defines the execution order according to the scientific workflow representation. We propose a multi-objective optimization that relies on a cloud cost model and employs tailored evolution operators. Starting from a population of possible solutions, we employ crossover and mutation operators on both chromosomes aiming at optimizing the data transferred between nodes as well as the total workflow runtime. The crossover operators combine parts of solutions to reduce data overhead, whereas the mutation operators swamp between parts of the same chromosome according to pre-defined rules. Our experimental study compares between the proposed approach and current state-of-the art approaches using synthetic and real-life workflows. Our algorithm performs similarly to existing heuristics for small workflows and shows up to 80 % improvements for larger synthetic workflows. To further validate our approach we compare between the allocation and scheduling obtained by our approach with that obtained by popular scientific workflow managers, when real workflows with hundreds of tasks are executed on a public cloud. The results show a 10 % improvement in runtime over existing schedulers, caused by a 80 % reduction in transferred data and optimized allocation and ordering of tasks. This improved data locality has greater impact as it can be employed to improve and study data provenance and facilitate data persistence for scientific workflows.     

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

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

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

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

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

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