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

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

基于逆向分层的网格工作流调度算法

有向无环图DAG(Directed Acrylic Graph)描述的工作流时间费用优化问题是计算网格下一个基本的且难以求解的问题.通过分析DAG图中活动的并行和同步完成特征,采取由后向前方法将活动逆向分层(BottomLevel,BL),将工作流截止期转化为层截止时间,提出截止期约束的逆向分层费用优化算法DBL(Deadline BottomLevel).算法中同层活动的开始时间不同于DTL(Deadline Top Level)算法中设置相同的策略,而是分别由其前驱活动确定,时间浮差被平均分配到各分层,以尽量增大活动的费用优化区间.通过大量模拟实验将DBL和MCP(mini mumCritical Path)、DTL两算法比较,结果表明DTL将MCP的平均费用降低15.62%,而DBL将MCP的平均费用降低24.74%.最后讨论了截止期和分组参数对算法性能的影响.     

基于时序一致的工作流费用优化方法

针对效用网格下的工作流时间约束-费用优化问题,分层算法将工作流进行分层并逐层进行优化调度,取得了良好效果.然而,这类分层算法由于缺乏更有效的截止时间确定策略来保证时间约束而使得算法的适用性受限.在已有算法截止期约束的逆向分层算法(deadline bottom level,DBL)的基础上,研究工作流的时序特征,并基于任务的一致性状态对费用进行优化,提出了基于时序一致的截止期约束逆向分层算法(temporal consistency based deadline bottom level,TCDBL).TCDBL通过一致性时间点来保证时间约束,解决了DBL的适用性受限问题;同时基于各层并行度分配冗余时间,基于宽松时间约束策略进行费用优化,达到了进一步减少工作流执行费用的目标.实验结果表明TCDBL的费用优化效果比DBL改进了约14%.     

基于逆向分层的网格工作流调度改进算法

通过对逆向分层DBL(Deadline Bottom level BL)算法的分析与研究,发现当截止期(δn)大于BLmin的情况下,其对逆向分层浮差(Tws)分配上有不足之处。为此该文提出了一种改进算法DBL-LC(DeadlineBottomlevel-lowercost)。改进算法使得对逆向分层浮差(Tws)的使用更加充分,减少了流时间碎片。实验证明,在相同的截止期下DBL-LC执行费用比DBL算法平均降低了14.52%。     

网格工作流的动态贪心调度算法

有向无环图描述的工作流时间费用优化问题是计算网格中的基本难题之一。针对该问题提出一种网格工作流的动态贪心调度算法(DGS-GW)。按用户提交的截止时间和偏好因子建立数学模型,利用DGS-GW求解该模型的次优解。实验结果证明了该算法的有效性。     

带通信开销的DAG工作流费用优化模型与算法

通信开销在云环境中无法忽略,但现有DAG(directed acyclic graph)工作流费用优化模型大都未考虑任务之间的通信开销,难以在实际云环境中应用.为此,提出带通信开销的工作流费用优化模型CA-DAG (communication aware-DAG),并在分层算法的基础上提出针对CA-DAG模型的调度算法CACO(communication aware cost optimization).CACO使用前向一致规则(forward consistent,FC)求解工作流的最小完工时间;根据逆向分层策略将任务分层,使费用优化问题从全局转化到局部;采用动态规划方法收集任务在选择服务时产生的零散“时间碎片”,增加任务的费用优化空间,改善费用优化效果.仿真实验结果表明,在考虑通信开销时,CACO费用优化效果较DTL (deadline top level),DBL(deadline bottom level),TCDBL(temporal consistency deadline bottom level)都有显著提高.     

基于改进优先级规则的工作流费用优化方法

效用网格下的工作流时间约束-费用优化调度是一个NP难问题,基于时间耦合强度(time-dependent coupling strength,TCS)的最适规则(best fit time-dependent coupling strength,BFTCS)将作业的资源特征与工作流的结构特征作为优先级规则的两个重要方面应用于迭代算法的改进阶段,取得了良好效果,然而,BFTCS忽略了工作流的时序特征.在已有工作的基础上,定义任务的时间灵活度(temporal mobility,TM)并设计基于时间耦合强度和时间灵活度的最适规则(best fit based on time-dependent coupling strength and temporal mobility,BFTCSTM).该规则在BFTCS规则的基础上选择TM较大的任务优先迭代,有效减缓了迭代过程中工作流长度的增长过程,使其他任务能进一步优化费用的机会增大,改善了工作流的费用优化效果.实验结果证明了BFTCSTM的优越性.     

OSG环境中可靠性增强的工作流自适应调度

针对实际的网格环境-Open Science Grid (OSG),提出了一个多阶段网格工作流调度机制,主要包括站点发现、站点初始评估以及站点动态评估和选择.通过基于时间序列的性能预测值评估各资源站点的初始性能,提出了一个基于网格资源站点自适应评分机制的选择算法.为了提高工作流执行的可靠性并尽可能缩短执行时间,设计了一个增量式的任务副本策略,并采用各资源站点任务排队等待时间的经验累积分布函数图来优化任务副本的设置参数.在实际网格环境OSG中,基于网格工作流系统Swift完成的大量实验结果表明,所提出的算法和策略能够有效减小工作流调度长度和作业拒绝率,同时在OSG中能够成功完成的Swift工作流规模也明显增大.     

兼顾费用与公平的带通信开销的多有向无环图调度

针对云环境下多有向无环图(DAG)工作流的调度算法应考虑执行时间、费用开销、通信开销、公平性等多个指标的问题,在模型带通信开销的DAG(CA-DAG)的基础上结合公平性算法提出一种优化完成时间的后向求异(BD)原则与兼顾费用和公平的多DAG调度策略CAFS.CAFS调度策略分为两个阶段:预调度阶段利用带通信开销的工作流费用优化(CACO)算法在考虑通信开销的同时求解所有任务的最优服务并优化费用,采用fairness算法得到较公平的调度顺序;调度阶段采用BD原则,根据在预调度阶段得出的调度顺序进一步优化整体的完成时间并执行调度.实验结果表明,CAFS调度算法具有较好的公平性,在不提高费用的基础上时间减少19.82%.     

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

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

A model-driven workflow fragmentation framework for collaborative workflow architectures and systems

This paper focuses on a workflow distribution methodology for rationally deploying workflow models onto a distributed workflow system running on cloud computing environments, and we particularly lay a stress upon that those workflow systems operable on cloud computing environments are dubbed collaborative workflow systems, which are not only built upon the collaborative workflow architectures proposed in the paper, but pursuing the so-called collaborative computing paradigm characterized by focusing collaboration over cloud computing environments. The essential idea of the workflow distribution methodology is about how to fragment a workflow model and how to allocate its fragments to each of the architectural components configuring the underlying collaborative workflow architecture and system. As a reasonable solution to realize the essential idea, the paper proposes a model-driven workflow fragmentation framework, which provides a series of fragmentation algorithms that semantically fragmentate a workflow model by considering the semantic factors - performer, role, control-flow, data-flow, etc. - of the ICN-based workflow model as fragmentation criteria. The algorithms are classified into the vertical fragmentation approach, the horizontal fragmentation approach, and the hybrid approach of both. Conclusively, this paper conceives a possible set of collaborative workflow architectures embedding the collaborative computing paradigm, and describes the detailed formalism of the framework and about how the framework works on those collaborative workflow architectures and systems.     

服务质量感知的网格工作流调度

在网格工作流中引入服务质量,可以使网格中的资源更好地围绕用户的要求进行组织和分配,服务质量为工作流执行过程中选择成员服务提供了依据.工作流服务质量的估算和服务质量感知的工作流调度是实现服务质量感知的网格工作流的两个关键问题.基于一种网格工作流模型讨论了网格工作流的服务质量参数体系,提出了工作流服务质量的估算算法和网格工作流调度数学模型,并提出了基于遗传算法的调度方法.仿真实验表明,该调度算法具有较好的收敛性.     

Global transaction support for workflow management systems: from formal specification to practical implementation

In this paper, we present an approach to global transaction management in workflow environments. The transaction mechanism is based on the well-known notion of compensation, but extended to deal with both arbitrary process structures to allow cycles in processes and safepoints to allow partial compensation of processes. We present a formal specification of the transaction model and transaction management algorithms in set and graph theory, providing clear, unambiguous transaction semantics. The specification is straightforwardly mapped to a modular architecture, the implementation of which is first applied in a testing environment, then in the prototype of a commercial workflow management system. The modular nature of the resulting system allows easy distribution using middleware technology. The path from abstract semantics specification to concrete, real-world implementation of a workflow transaction mechanism is thus covered in a complete and coherent fashion. As such, this paper provides a complete framework for the application of well-founded transactional workflows. Received: 16 November 1999 / Accepted 29 August 2001 Published online: 6 November 2001     

A grid workflow Quality-of-Service estimation based on resource availability prediction

Accurate estimation of workflow Quality of Service (QoS) enhances the efficiency of scheduling algorithms. The availability and performance variations of Grid computing resources have made this estimation a great challenge. Most workflow QoS estimation algorithms are based on static performance of resources. In this paper, based on resources availability prediction, we propose an algorithm called WQE for estimating the QoS of a Grid workflow. WQE consists of two phases: resource monitoring and analysis and workflow QoS computation. In the first phase, two prediction algorithms are proposed to stochastically predict the availability state of resources. In the second phase, the QoS of each activity is estimated based on the host availability prediction result. The QoS of basic structures is computed by aggregating the QoS of their operands. Using a tree structure corresponding to the workflow, the QoS of basic structures is used to compute the total QoS of the workflow. The simulation results on Notre Dame University trace showed that the proposed method has higher estimation accuracy in comparison with HEFT.     

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

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

网格工作流调度算法研究综述*

作为一个NP完全问题,通常采用启发式算法来解决网格工作流调度。首先对网格工作流调度算法进 行了分类,然后对其典型算法进行了分析和讨论,并阐述了一些典型网格工作流调度系统,最后指出了现有算法 中的一些不足之处,展望了该领域的进一步研究方向。     

迁移工作流系统通信机制研究

迁移工作流是解决当前工作流管理领域不完全业务过程定义的一个新的研究方向，通信机制是迁移工作流系统实现的一个关键问题。本文在分析通信需要解决的主要问题的基础上，提出了一种适应迁移工作流系统特征的通信模型，给出了模型框架结构，并详细描述了其中的迁移实例通信算法。模型在实现可靠异步通信的同时，能够保证信件的顺序和exactly-once提交，降低寻址时间，减小三角路由的带宽占用，增强系统对规模扩大的适应能力，使算法在通信与迁移都较频繁时仍能保持较高的效率。     

ElasticSim: A Toolkit for Simulating Workflows with Cloud Resource Runtime Auto-Scaling and Stochastic Task Execution Times

Resource provisioning and scheduling are crucial for cloud workflow applications. Simulation is one of the most promising evaluation methods for different resource provisioning and scheduling algorithms. However, existing simulators for Cloud workflow applications fail to provide support for resource runtime auto-scaling and stochastic task execution time modeling. In this paper, a workflow simulator ElasticSim is introduced, which is an extension of the popular used CloudSim simulator by adding support for resource runtime auto-scaling and stochastic task execution time modeling. Most of existing workflow scheduling algorithms are static and are based on deterministic task execution times. By the aid of ElasticSim, the practical performance of existing static algorithms, when they are put into practice with stochastic task execution times, is evaluated. Experimental results show that about 2.8 % to 20 % additional resource rental cost is incurred for different cases and workflow deadlines are violated for most cases because of stochastic task execution times. Therefore, ElasticSim is a promising platform for evaluating the practical performance of workflow resource provisioning and scheduling algorithms, which supports resource runtime auto-scaling and stochastic task execution time modeling.     

动态工作流变更的有效处理

本文探讨了一种处理动态工作流系统变更的方法。首先介绍了几种常见的处理工作流变更的方法．然后提出了一个对当前工作流的修改进行合并的有效处理算法．最后给出了一个实例以验证算法的有效性。