A particle swarm optimization and min–max-based workflow scheduling algorithm with QoS satisfaction for service-oriented grids

In service-orientated grids (SOG) environments, grid workflow schedulers play a critical role in providing quality-of-service (QoS) satisfaction for various end users (EUs) with diverse QoS objectives and optimization requirements. The EU requirements are not only many and conflicting, but also involve constraints of various degrees—loose, moderate or tight. However, most of the existing scheduling approaches violate EU constraints in tight situations and suffer inferior QoS optimization results. In this paper, a constraints-aware multi-QoS workflow scheduling strategy is proposed based on particle swarm optimization (PSO) and a proposed look-ahead heuristic (LAPSO) to improve performance in such situations. The algorithm selects the best scheduling solutions based on the proposed constraint-handling strategy. It hybridises PSO with a novel look-ahead mechanism based on a min–max heuristic, which deterministically improves the quality of the best solutions. Extensive simulation experiments have been carried out to evaluate the performance of the proposed approach. The simulation results show that the LAPSO algorithm guarantees satisfaction (0% violation) of the EU constraints even in tight situations. It also outperforms the comparison algorithm, with about 30% increase, in terms of cumulative QoS satisfaction of optimization requirements. In addition, the new scheme significantly reduces the CPU time by about 75% compared to the benchmark algorithm.     

基于网格资源超图模型的可信任务调度

网格任务调度是当前重要的研究领域。网格环境具有动态性、异构性等特点,网格资源的处理性能和稳定性都是影响到任务调度顺利完成的重要因素。为了获得更小的任务完成时间,该文根据网格环境的特点,建立了网格资源超图模型,在该模型基础上对资源按性能进行聚类,并提出一种可信任务调度算法GRHTS。模拟实验结果表明,该基于网格资源超图模型的可信任务调度算法优于同类算法,是一种有效的网格任务调度算法。     

军事网格工作流调度算法研究

针对军事网格应用及工作流的特点,提出一种基于网格工作流分割的调度算法。采用基于有向无环图的工作流建模方法,对网格工作流的相关概念进行形式化定义。在确定基本工作流之间的复合关系后,对网格工作流中的任务实施调度。实例结果表明,该算法能减少网格工作流的任务执行时间,具有较好的调度性能。     

网格环境下工作流的费用-时间调度算法

开放网格服务架构（OGSA）和计算经济模型的提出，使得动态的、不同QoS的服务支持下的资源调度成为一个复杂且具有挑战性的问题。该文提出了网格环境下基于费用-时间的工作流调度算法，该算法采用动态资源选择策略适应网格计算环境下的动态性和自治性。在追求较小的工作流完成时间的同时，对费用进行了优化。模拟结果显示该调度算法符合计算网格的复杂环境，能够更好地满足不同用户的实际需要。     

混合计算环境中截止期约束下的科学工作流调度策略

整合云和网格基础设施,增强科研机构现有网格系统的计算能力并向应用提供截止时间保障的服务是科学研究领域的热点。在这种"网格-云"混合计算环境中,对何时租借云虚拟资源以及如何租借做出有效决策是一个难题。现有的一些调度策略主要在网格资源静态能力特征的基础上,以作业等待时间作为决策依据,缺乏对资源动态服务能力的有效评估,无法保证科学应用的截止时间需求。本文提出了一种混合环境下的科学工作流执行系统架构并对其核心组件进行了阐述。针对其中的工作流调度问题,利用随机服务模型建模已有网格系统中的资源的动态服务能力,以任务违约风险作为是否租借外部虚拟资源的判断指标,提出了一个科学工作流调度算法HCA_SASWD。实验结果表明,HCA_SASWD相对于其他算法,能有效保证用户的截止时间要求,为需要提供截止时间保障的系统架构提供了参考。     

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

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

一个网格服务工作流的动态调度算法*

针对服务网格环境中资源的动态性,提出了一种并行调度算法PGSWA（parallel grid service workflow scheduling）,该算法引入了性能预测模型和并行就绪队列来预测下一段时间资源的性能并使得成员服务能够并行执行。实验证明,该算法能较好地缩短工作流的执行时间,提高工作流的执行性能。     

一个市场驱动的QoS网格工作流任务调度算法

网格调度关系到整个网格任务运行的效率,因此在网格的研究过程中,已经提出了很多调度算法.但这些算法大部分是对元任务(Meta-task)进行调度,很少是针对关联任务的.在考虑用户QoS(Quality of Service)需求的情况下,提出了一个市场驱动的QoS网格工作流任务调度算法.仿真实验结果表明了该算法的合理性和有效性.     

基于D-Petri Net和动态调度的网格工作流

提出了网格工作流体系结构;给出了基于D-Petri Net的网格工作流建模语言和验证方法,利用该建模语言生成的过程模型适合网格资源动态性的特点;分析了根据网格性能动态产生并行任务和动态调度的算法;最后介绍了在Globus上实现的原型系统和在基因测序中的应用,该系统具有良好的效果。     

三层虚拟工作流模型的非线性制造工艺多目标优化算法研究EI北大核心CSCD

时间、生产质量和成本是加工制造中相互制约的重要参数,平衡此参数使制造工艺最优是一个NP(Non-deterministic polynomial)难题,对此出现了许多优秀的调度方法.然而这些方法的优化对象均为线性工艺,对于普遍存在的非线性工艺却无法调度优化.针对此不足,本文以非线性工艺为优化对象提出了三层虚拟工作流模型Three-VMG(Three-virtual model graph)及其优化算法Three-OVMG(Three-optimal virtual model graph).该模型和算法首先建立非线性工作流,采用虚拟技术寻找虚拟结点进行重构,将其改造为虚拟线性工作流;其次结合工艺特点对模型进行分段,采用逆向分层串归约来实现段内最优解,采用累积最优解来衔接各段间的值;最后根据优化结果自顶向下完成各层资源的优化调度.实验表明,该过程较传统时间最小化优化调度算法具有显著的优化效果,其性能及可操作性也能满足工程要求.     

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

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

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

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

A system-centric scheduling policy for optimizing objectives of application and resource in grid computing

In grid computing, grid users who submit applications and resources providers who provide resources have different motivations when they join the grid. Application-centric scheduling aims to optimize the performance of individual application. Resource-centric scheduling aims to optimize the resource utilization of resources provider. Due to autonomy both in grid users and resource providers, the objectives of application-centric and resource-centric scheduling often conflict. The paper proposes a system-centric scheduling that provides a solution of joint optimization of the objectives for both the grid resource and grid application. Utility functions are used to express the objectives of grid resource and application. The system-centric scheduling policy can be formulated as joint optimization of utilities of grid applications and grid resources, which combine both application centric and resource-centric scheduling benefits. Simulations are conducted to study the performance of the system-centric scheduling algorithm. The experiment results show that the system-centric scheduling algorithm yields significantly better performance than application-centric scheduling algorithm and resource-centric scheduling algorithm.     

基于路径平衡的工作流费用优化方法

针对效用网格下截止期约束的工作流费用优化问题,提出了路径平衡(path balance,简称 PB)算法,对工作流中各路径长度进行调整,并提出基于路径平衡的费用优化(path balance based cost optimization,简称PBCO)算法。 PBCO 基于 PB 的计算结果设置初始约束时间,充分利用了工作流的费用优化空间。同时,采用逆向分层策略对任务进行分层,并根据各层任务数按比例分配冗余时间,有效地增大了多数任务的费用优化空间,进一步改善了工作流的费用优化效果。实验结果表明,PBCO比另外几种著名算法(如DET,DBL等)改进了约35%。     

一种新颖的网格工作流调度算法

针对当前网格工作流调度算法中大多只考虑DAG结构的网格工作流、涉及QoS参数较少及将多QoS参数聚合成一个单目标函数进行优化调度的现状,提出了一种新颖的网格工作流调度算法。该算法基于表达结构丰富的AGWL语言建模网格工作流,且基于MOPSO算法所设计的带多QoS约束的多目标优化的网格工作流调度算法。通过与基于NSGA-Ⅱ算法的网格工作流调度算法比较,表明了该算法的有效性。     

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

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

基于PSODE的网格任务调度算法

针对网格计算中任务在各个资源之间的调度问题,提出了一种网格环境下PSODE的任务调度算法.该算法实现了计算资源、存储资源、带宽资源、数据资源的利用率最高化和代价最低化.对基本粒子群算法和差分进化算法进行了分析,通过构造算法函数、适应值函数和权重公式,建立了粒子群差分混合算法并对其进行优化,介绍了算法的实现过程.实验结果表明,该算法与其它调度算法比较,具有良好的性能.     

基于离散粒子群算法的工作流任务调度研究

工作流系统可以实现企业的业务过程的自动化,好的调度算法可以提高整个工作流系统的执行效率。对工作流任务调度的研究具有重要的意义。离散粒子群优化算法是一种收敛速度快、调整参数少、易实现及理解的优化算法。结合工作流特点,通过置换因子的概念,将离散粒子群算法与工作流任务调度相结合,给出了基于离散粒子群算法的工作流任务调度的定义。并结合保险理赔处理进行实验,得到了良好的效果,验证了应用的有效性和可行性。     

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

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

融合DE和NSGA-Ⅱ算法的网格工作流调度研究*

针对当前网格工作流调度算法中大多只考虑DAG结构的网格工作流、考虑QoS维数较少及将多QoS参数聚合成一个单目标函数进行优化调度的现状,基于AGWL网格工作流模型,提出了一种带QoS约束的多目标优化的网格工作流调度算法,该算法是将DE的变异和交叉算子替换NSGA-Ⅱ中的变异和交叉操作所设计的一种调度算法。通过与基于NSGA-Ⅱ的网格工作流调度算法比较,表明了该算法的有效性。