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

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

基于截止时间满意度的网格工作流调度算法

动态网格环境中用户截止时间保障是工作流调度问题的一个挑战.利用随机服务模型来描述网格资源的动态处理能力及其动态负载压力,提出了截止时间满意度的概念和工作流截止时间满意度的计算方法.将以DAG图形式表示的任务执行关系转换为以数值表示的任务执行优先级,并根据最大截止时间满意度优先的思想,确定执行工作流子任务的候选资源;将工作流全局截止时间划分问题描述为一个约束下的非线性规划问题并通过已有方法求解该问题,提出了一种截止时间满意度增强的工作流调度算法(DSESAW).仿真实验采用实际网格应用和系统数据来验证所提出算法的性能表现,实验结果表明新算法在网格环境的自适应性和用户截止时间保障方面优于其他两种实际网格系统中的调度算法.     

基于动态粒子群算法的工作流服务主体优选方法

在研究工作流服务时间一费用双重优化问题的基础上,提出一种基于动态粒子群算法的工作流服务主体优选 方法。通过区域划分,在每个粒子所在区域内,当适应值小于最佳适应值时,对区域重新进行初始化,从而使算法具有 更强的全局收敛性和动态的自适应性;同时引入随机扰动、回退等算子,将搜索范围扩大到整个解空间以大大提高获 得最优解的概率。结合动态粒子群算法建立工作流调度问题的目标模型,并从跨时间粒度、跨时区、跨工作时间3个 方面对工作流服务主体优选方法进行了讨论分析。实验结果表明,该方法比其他应用工作流调度的算法具有更短的 执行时间和费用,具有更高的效率、更好的优越性。     

基于离散粒子群和禁忌搜索的网格资源调度算法

提出一种基于智能的网格资源分配和任务调度算法,由于网格资源调度是个离散问题,所以采用基于惯性权重的离散粒子群算法,针对离散粒子群算法在后期容易陷入局部最优的缺陷,将其与禁忌搜索算法相结合,在算法的前期采用离散粒子群算法进行搜索,在后期采用禁忌搜索算法进行局部搜索。并利用网格模拟工具Gridsim Toolkit开发一个网格模拟系统进行实验。实验结果表明,该算法具有较高的寻优能力。     

基于微粒群算法的网格工作流优化调度问题的研究

网格工作流中的调度问题是一个复杂且具有挑战性的问题,它影响着网格工作流执行成功与否及效率的高低.针对具有时序和因果约束关系的网格工作流优化调度问题进行了研究,建立了网格工作流的任务调度模型和调度问题的目标模型,并应用微粒群算法来优化网格工作流中任务的调度.实验结果证明该算法优于传统的调度算法.     

云环境中面向可靠性约束的工作流调度策略研究

随着越来越多的计算密集型依赖应用被卸载到云环境中执行，工作流调度问题受到了广泛的关注。针对云环境多目标优化的工作流调度问题，考虑到任务执行过程中服务器可能会发生性能波动和宕机等问题，基于模糊理论，使用三角模糊数表示任务执行时间和数据传输时间，提出了一种基于遗传算法的自适应粒子群优化算法(Adaptive Particle Swarm Optimization based GA,APSOGA),目的是在工作流的可靠性约束下，综合优化工作流的完成时间和执行代价。该算法为了避免传统粒子群优化算法存在的过早收敛问题，引入了遗传算法的随机两点交叉操作和单点变异操作，有效地提升了算法的搜索性能。实验结果表明，与其他策略相比，基于APSOGA的调度策略能够有效地降低云环境中面向可靠性约束的科学工作流的模糊总代价。     

基于粒子群优化和禁忌搜索的混合调度算法

提出了用于解决作业车间调度问题的离散版粒子群优化算法。该算法采用基于先后表编码方案和新的位移更新模型,使具有连续本质的粒子群优化算法直接适用于车间调度问题。同时,利用粒子群优化算法的全局搜索能力和禁忌搜索算法的自适应优点,将粒子群优化算法和禁忌搜索结合起来,设计了广义粒子群优化算法和粒子群—禁忌搜索交替算法两种混合调度算法。实验结果表明,两种混合调度算法能够有效地、高质量地解决作业车间调度问题。     

基于遗传算法的网格服务工作流调度的研究

网格服务的提出为网格工作流的研究提供了新的契机与挑战，由网格服务组成的工作流（GSF）的调度问题是一个典型的NP问题。利用遗传算法所具有的并行性和全局解空间搜索的特点，针对网格服务调度问题，提出基于遗传算法的网格服务工作流调度算法GSFGA，并改进了遗传算法的收敛特性，通过分析实验结果证明该算法优于传统的调度算法。     

网格环境中的资源任务调度模型研究

为了解决动态异构网格环境下任务调度多目标问题,提出了基于满意度概念的任务调度模型.该模型最优化目标是保证任务执行总费用最低,执行时间最短和负载平衡,结合满意度目标函数,实现了免疫粒子群(immuneparticle swarlnoptimization,IPSO)启发式调度算法.实验结果表明,随着进化过程的推进,与PSO算法相比,IPSO算法在全局寻优能力、搜索速度和避免早熟方面都有显著提高.     

基于MPSO算法的云计算资源调度策略

针对云计算服务集群资源调度和负载平衡的优化问题,提出一种基于改进的粒子群优化算法的云计算资源调度策略。将动态多群体协作和变异粒子逆向飞行思想引入到粒子群优化算法中,从而控制全局搜索和局部搜索,尽量避免陷入局部最优。在CloudSim 平台进行模拟测试,结果表明,该调度策略有效且执行效率较高。     

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

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

基于混合GA算法的工作流作业调度队列优化

工作流作业的调度效率是评价工作流管理系统整体表现的重要指标。众所周知,工作流作业的调度问题是一个NP-hard问题,而异构的计算环境使得问题更加棘手。分层基因算法LGA将启发式算法与GA算法相结合,利用GA算法来优化经过正向分层之后的工作流作业调度队列,显著地减少了工作流作业的执行时间。该算法根据作业的分层优先级来产生作业队列,把队列中的同层作业从整体上看作是一位基因来处理,有效地对算法的进化方向进行规划,并通过对杂交和变异流程的改进,增强算法的搜索深度和广度。实验表明,相比于其他混合GA算法,经LGA算法优化之后的工作流作业调度队列,所需的执行时间更少。     

基于JBPM的服务动态编排及迁移方案

为了适应复杂环境下动态多变的业务需求,对以服务为核心的流程动态编排和再造提供支持,提出了基于JBPM工作流的流程动态编排与迁移方案,该方案分析了目前工作流在流程编排方面的局限性;结合柔性工作流的特点,给出了流程动态编排的模型,并对流程变更所产生的4类操作做了形式化的描述,通过对流程变更引发的流程进行迁移继而实现接续执行这一问题的研究,提出一种流程迁移算法。最后通过实例和性能测试工具验证了算法的可行性和高效性。     

A hybrid heuristic workflow scheduling algorithm for cloud computing environments

Cloud computing is a relatively new concept in the distributed systems and is widely accepted as a new solution for high performance and distributed computing. Its dynamisms in providing virtual resources for organisations and laboratories and its pay-per-use policy make it very popular. A workflow models a process consisting of a series of steps that shape an application. Workflow scheduling is the method for assigning each workflow task to a processing resource in a way that specific workflow rules are satisfied. Some scheduling algorithms for workflows may assume some quality of service parameter such as cost and deadline. Some efforts have been done on workflow scheduling on cloud computing environments with different service level agreements. But most of them suffer from low speed. Here, we introduce a new hybrid heuristic algorithm based on particle swarm optimisation (PSO) and gravitation search algorithms. The proposed algorithm, in addition to processing cost and transfer cost, takes deadline limitations into account. The proposed workflow scheduling approach can be used by both end-users and utility providers. The CloudSim toolkit is used as a cloud environment simulator and the Amazon EC2 pricing is the reference pricing used. Our experimental result shows about 70% cost reduction, in comparison to non-heuristic implementations, 30% cost reduction in comparison to PSO, 30% cost reduction in comparison to gravitational search algorithm and 50% cost reduction in comparison to hybrid genetic-gravitational algorithm.     

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.

     

适用于实例密集型云工作流的调度算法

工作流调度算法仅适用于单个复杂工作流实例,而不适用于实例密集型云工作流实例,为此,提出了基于实例密集型的云工作流调度算法(MCUD)。MCUD算法先对待处理的一组工作流实例进行分类,再对分类后的同类工作流实例采用一种新的分配方法将用户指定的总最后期限分配到各任务;同时,在调度的过程中动态地调整后续任务的子最后期限。MCUD算法对同类工作流实例中的任务分配不同子最后期限,减小了资源竞争,提高了资源的利用率。仿真实验表明,MCUD相比于其他算法,在满足总的最后期限的前提下更进一步地降低了执行成本和执行时间。     

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

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

多QoS约束的双目标最优的网格工作流调度研究*

针对当前网格工作流调度算法中大多只考虑DAG结构的网格工作流,涉及QoS参数较少或将多QoS参数聚合成一个单目标函数进行优化调度,提出了一种多QoS约束的双目标最优的网格工作流调度算法。该算法是基于AGWL网格工作流模型和改进的MOPSO算法,其目标是在满足可靠性、可利用性和声誉这三维QoS参数约束下,同时最小化两个冲突目标,即响应时间和服务费用。通过与原MOPSO所设计的网格工作流调度算法比较,该算法能获得更优的优化解。     

Bi-level fuzzy based advanced reservation of Cloud workflow applications on distributed Grid resources

The increasing demand on execution of large-scale Cloud workflow applications which need a robust and elastic computing infrastructure usually lead to the use of high-performance Grid computing clusters. As the owners of Cloud applications expect to fulfill the requested Quality of Services (QoS) by the Grid environment, an adaptive scheduling mechanism is needed which enables to distribute a large number of related tasks with different computational and communication demands on multi-cluster Grid computing environments. Addressing the problem of scheduling large-scale Cloud workflow applications onto multi-cluster Grid environment regarding the QoS constraints declared by application’s owner is the main contribution of this paper. Heterogeneity of resource types (service type) is one of the most important issues which significantly affect workflow scheduling in Grid environment. On the other hand, a Cloud application workflow is usually consisting of different tasks with the need for different resource types to complete which we call it heterogeneity in workflow. The main idea which forms the soul of all the algorithms and techniques introduced in this paper is to match the heterogeneity in Cloud application’s workflow to the heterogeneity in Grid clusters. To obtain this objective a new bi-level advanced reservation strategy is introduced, which is based upon the idea of first performing global scheduling and then conducting local scheduling. Global-scheduling is responsible to dynamically partition the received DAG into multiple sub-workflows that is realized by two collaborating algorithms: (1) The Critical Path Extraction algorithm (CPE) which proposes a new dynamic task overall critically value strategy based on DAG’s specification and requested resource type QoS status to determine the criticality of each task; and (2) The DAG Partitioning algorithm (DAGP) which introduces a novel dynamic score-based approach to extract sub-workflows based on critical paths by using a new Fuzzy Qualitative Value Calculation System to evaluate the environment. Local-scheduling is responsible for scheduling tasks on suitable resources by utilizing a new Multi-Criteria Advance Reservation algorithm (MCAR) which simultaneously meets high reliability and QoS expectations for scheduling distributed Cloud-base applications. We used the simulation to evaluate the performance of the proposed mechanism in comparison with four well-known approaches. The results show that the proposed algorithm outperforms other approaches in different QoS related terms.     

基于目标函数变化率的混合蚁群遗传算法

根据蚁群算法和遗传算法收敛性互补的特点,提出了一种基于目标函数变化率的混合蚁群遗传算法。该算法的基本思想是：用蚁群算法的解作为遗传算法的初始种群,根据目标函数的变化率交叉地调用蚁群算法和遗传算法。每当种群进化接近停滞时,调用蚁群算法。这种方法可动态地控制蚁群算法和遗传算法的调用时机,再配合相应的信息素更新方法,以提高算法的收敛性。将新算法用于车间调度基准测试问题,仿真结果表明,与常规混合蚁群遗传算法相比,新算法的全局收敛性和局部收敛性有了明显的提高。