工作流时序约束模型分析与验证方法

为了解决工作流时间建模与时序一致性验证问题,以时序逻辑和模型检查为基础,提出了一种工作流时间建模与时序一致性验证方法.该方法用一阶逻辑描述工作流模型及其时间信息,用时序逻辑描述工作流的时序约束,用模型检查算法对时序约束进行验证与分析.该方法不是针对某一种时序约束提出来的,而是能够验证任何用时序逻辑描述的工作流时序约束.该方法还能够对未通过验证的时序约束提供工作流运行实例作为反例,帮助用户定位模型的问题.以一个工作流时间建模和时序一致性验证的实例证实了所提出方法的有效性.     

Dynamic checking of temporal constraints for concurrent workflows

At present, workflow management systems have not sufficiently dealt with the issues of time, involving time modelling at build-time and time management at run-time. They are lack of the ability to support the checking of temporal constraints at run-time. Although some approaches have been devised to tackle this problem, they are limited to a single workflow and use only static techniques to verify temporal constraints. In reality, there are multiple workflows executing concurrently in a workflow management system. There may well exist resource constraints between these concurrent workflows, which affect significantly the verification of temporal constraints at run-time. This paper proposes a novel approach for dynamic verification of temporal constraints for concurrent workflows. We first investigate resource constraints in workflow management systems, and then define concurrent workflow executions. Based on these definitions, we propose a verification method by analysing the temporal relationship and resource constraints between activities among concurrent workflows.     

SEAM: A state-entity-activity-model for a well-defined workflowdevelopment methodology

Current conceptual workflow models use either informally defined conceptual models or several formally defined conceptual models that capture different aspects of the workflow, e.g., the data, process, and organizational aspects of the workflow. To the best of our knowledge, there are no algorithms that can amalgamate these models to yield a single view of reality. A fragmented conceptual view is useful for systems analysis and documentation. However, it fails to realize the potential of conceptual models to provide a convenient interface to automate the design and management of workflows. First, as a step toward accomplishing this objective, we propose SEAM (State-Entity-Activity-Model), a conceptual workflow model defined in terms of set theory. Second, no attempt has been made, to the best of our knowledge, to incorporate time into a conceptual workflow model. SEAM incorporates the temporal aspect of workflows. Third, we apply SEAM to a real-life organizational unit's workflows. In this work, we show a subset of the workflows modeled for this organization using SEAM. We also demonstrate, via a prototype application, how the SEAM schema can be implemented on a relational database management system. We present the lessons we learned about the advantages obtained for the organization and, for developers who choose to use SEAM, we also present potential pitfalls in using the SEAM methodology to build workflow systems on relational platforms. The information contained in this work is sufficient enough to allow application developers to utilize SEAM as a methodology to analyze, design, and construct workflow applications on current relational database management systems. The definition of SEAM as a context-free grammar, definition of its semantics, and its mapping to relational platforms should be sufficient also, to allow the construction of an automated workflow design and construction tool with SEAM as the user interface     

A Provenance-based Adaptive Scheduling Heuristic for Parallel Scientific Workflows in Clouds

In the last years, scientific workflows have emerged as a fundamental abstraction for structuring and executing scientific experiments in computational environments. Scientific workflows are becoming increasingly complex and more demanding in terms of computational resources, thus requiring the usage of parallel techniques and high performance computing (HPC) environments. Meanwhile, clouds have emerged as a new paradigm where resources are virtualized and provided on demand. By using clouds, scientists have expanded beyond single parallel computers to hundreds or even thousands of virtual machines. Although the initial focus of clouds was to provide high throughput computing, clouds are already being used to provide an HPC environment where elastic resources can be instantiated on demand during the course of a scientific workflow. However, this model also raises many open, yet important, challenges such as scheduling workflow activities. Scheduling parallel scientific workflows in the cloud is a very complex task since we have to take into account many different criteria and to explore the elasticity characteristic for optimizing workflow execution. In this paper, we introduce an adaptive scheduling heuristic for parallel execution of scientific workflows in the cloud that is based on three criteria: total execution time (makespan), reliability and financial cost. Besides scheduling workflow activities based on a 3-objective cost model, this approach also scales resources up and down according to the restrictions imposed by scientists before workflow execution. This tuning is based on provenance data captured and queried at runtime. We conducted a thorough validation of our approach using a real bioinformatics workflow. The experiments were performed in SciCumulus, a cloud workflow engine for managing scientific workflow execution.     

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

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

Soundness-preserving reduction rules for reset workflow nets

The application of reduction rules to any Petri net may assist in its analysis as its reduced version may be significantly smaller while still retaining the original net’s essential properties. Reset nets extend Petri nets with the concept of a reset arc, allowing one to remove all tokens from a certain place. Such nets have a natural application in business process modelling where possible cancellation of activities need to be modelled explicitly and in workflow management where such process models with cancellation behaviours should be enacted correctly. As cancelling the entire workflow or even cancelling certain activities in a workflow has serious implications during execution (for instance, a workflow can deadlock because of cancellation), such workflows should be thoroughly tested before deployment. However, verification of large workflows with cancellation behaviour is time consuming and can become intractable due to the state space explosion problem. One way of speeding up verification of workflows based on reset nets is to apply reduction rules. Even though reduction rules exist for Petri nets and some of its subclasses and extensions, there are no documented reduction rules for reset nets. This paper systematically presents such reduction rules. Because we want to apply the results to the workflow domain, this paper focusses on reset workflow nets (RWF-nets), i.e. a subclass tailored to the modelling of workflows. The approach has been implemented in the context of the workflow system YAWL.     

Modeling and Analysis of Real-Time Cooperative Systems Using Petri Nets

The existing formal techniques are not suitable for elegantly modeling passing value indeterminacy and describing batch processing function in real-time cooperative systems. Moreover, the correct behavior of the systems depends on not only the logical correctness of the results obtained through running workflows but also the time of producing them before critical deadlines. For these purposes, this paper proposes an interorganizational logical workflow net (ILWN) for modeling and analyzing real-time cooperative systems based on time Petri nets, workflow techniques, and temporal logic. Through attaching logical expressions to some actions of an ILWN model, the size of the model is reduced. Thus, ILWNs can efficiently mitigate the state explosion problem to some extent. Also, this paper analyzes the soundness of a subclass of ILWNs: the or-restricted ILWNs. A rigorous analysis approach is given based on their static net structures only. The concepts and techniques proposed in this paper are illustrated with a seller-buyer example in electronic commerce.     

Modeling and Inference of Extended Interval Temporal Logic for Nondeterministic Intervals

Extended interval temporal logic (EITL), an extension of the traditional point-interval temporal logic (PITL), is proposed. In contrast to PITL that represents the dynamic aspects of deterministic intervals, EITL can model and reason about the temporal relations among nondeterministic intervals in discrete-event systems, in which the duration of an event is indeterminate and only the lower bound and upper bound of the ending time can be predicted in advance. Time Petri nets (TPNs) are used for modeling EITL, for they give a straightforward view of temporal relations between the extended intervals and also provide a number of theoretical and practical analysis methods. An inference engine based on the TPN modeling complemented with algebraic inequalities is proposed to construct an analytical representation of the EITL relations and solve qualitative temporal reasoning problems. Linear inference mechanism based on TPN reduction rules is used to infer new temporal relations and handle quantitative temporal reasoning problems with linear time complexity, as our example shows.     

Adding flexibility to workflows through incremental planning

Workflow management systems usually interpret a workflow definition rigidly. However, there are real life situations where users should be allowed to deviate from the prescribed static workflow definition for various reasons, including lack of information, unavailability of the required resources and unanticipated situations. Furthermore, workflow complexity may grow exponentially if all possible combinations of anticipated scenarios must be compiled into the workflow definition. To flexibilize workflow execution and help reduce workflow complexity, this paper proposes a dual strategy that combines a library of predefined typical workflows with a planner mechanism capable of incrementally synthesizing new workflows, at execution time. This dual strategy is motivated by the difficulty of designing emergency plans, modeled as workflows, which account for real-life complex crisis or accident scenarios.     

基于对象的角色工作流模型研究

工作流是流程集成的有效方法,但工作流模型在描述复杂的流程时语义和柔性不足,导致实用中工作流模型的仿真分析和运行能力欠佳;另一方面,对象技术作为一种很有潜力的流程建模方法,可以改善工作流的描述。它与工作流的结合,将有助于上述问题的解决。文章借助对象技术,分析了面向角色的工作流模型,并在此基础上讨论了其实现。     

基于构件的本体扩展工作流的构架研究与应用

几乎所有的行业都涉及工作流,用以协调任务之间的执行。由构件组成的工作流,可以提高系统的复用性,加快系统的开发和配置速度。但是构件之间句法语义的不同,决定了它们是不能直接组装的。论文提出基于本体扩展的工作流构件,使用本体来解决不同构件之间的元数据映射,并实现了基于构件的本体扩展工作流的框架,做出了具体实施。     

工作流技术在新一代电信运营综合管理支撑系统中的应用研究

介绍了工作流技术并以电信运营综合管理系统 (Business &Operation Support System,简称 BOSS)为背景 ,分析了工作流技术的具体实现 ,主要包括工作流技术介绍 ,工作流支撑的 BOSS架构、BOSS参考模型、BOSS体系结构、BOSS数据中心模型等几个方面     

On Modeling and Verification of Temporal Constraints in Production Workflows

The dynamic nature of events, in particular business processes, is a natural and accepted feature of today’s business environment. Therefore, workflow systems, if they are to successfully model portions of the real world, need to acknowledge the temporal aspect of business processes. This is particularly true for processes where any deviation from the prescribed model is either very expensive, dangerous or even illegal. Such processes include legal processes, airline maintenance or hazardous material handling. However, time modeling in workflows is still an open research problem. This paper proposes a framework for time modeling in production workflows. Relevant temporal constraints are presented, and rules for their verification are defined. Furthermore, to enable visualization of some temporal constraints, a concept of “duration space” is introduced. The duration algorithm which calculates the shortest/longest workflow instance is presented. It is a generalization of two categories of algorithms: the shortest-path partitioning algorithm and the Critical Path Method (CPM). Based on the duration algorithm, the verification algorithm is designed to check the consistency of introduced temporal constraints.     

Workflows for Heliophysics

In this paper we describe how we have introduced workflows into the working practices of a community for whom the concept of workflows is very new, namely the heliophysics community. Heliophysics is a branch of astrophysics which studies the Sun and the interactions between the Sun and the planets, by tracking solar events as they travel throughout the Solar system. Heliophysics produces two major challenges for workflow technology. Firstly it is a systems science where research is currently developed by many different communities who need reliable data models and metadata to be able to work together. Thus it has major challenges in the semantics of workflows. Secondly, the problem of time is critical in heliophysics; the workflows must take account of the propagation of events outwards from the sun. They have to address the four dimensional nature of space and time in terms of the indexing of data. We discuss how we have built an environment for Heliophysics workflows building on and extending the Taverna workflow system and utilising the myExperiment site for sharing workflows. We also describe how we have integrated the workflows into the existing practices of the communities involved in Heliophysics by developing a web portal which can hide the technical details from the users, who can concentrate on the data from their scientific point of view rather than on the methods used to integrate and process the data. This work has been developed in the EU Framework 7 project HELIO, and is being disseminated to the worldwide Heliophysics community, since Heliophysics requires integration of effort on a global scale.     

跨组织工作流的动态协同技术研究

跨组织的工作流致力于跨越组织边界进行业务重组。针对多个组织间动态协同的复杂性,在组织间协作过程中必须考虑对组织的隐私信息、已建立的工作流和已建立的工作流管理系统的保护,解决成员间进行信息共享时出现的问题,从而真正实现协同商务。为满足这些需求,提出了基于视图的方法,这个方法考虑了工作流和资源的部分可见性,不同程度的可见性可以使企业保持其内部工作流隐私和安全性所需的水平,从而把工作流的可见性降低到合作所需的最低水平。研究的目的是使得组织在增强对外交互能力的同时,保护组织内部的敏感信息。     

An implementation of inference in temporal branching time models

Issues concerning the implementation of temporal reasoning (inference) for models based on branching time logic as applied to intelligent decision support systems are considered. The focus is on the construction of a qualitative (interval) and quantitative (metric) branching time model. The inference is reduced to solving the temporal constraint satisfaction problem, and the corresponding procedures (algorithms) are proposed. An example of the practical application of the proposed techniques in a prototype of a real-time intelligent decision support system is described.     

扩展时段时序逻辑的模型、一致性和推理

给出了扩展时段时序逻辑的时间Petri网（TPN）模型构造方法，在构造模型的同时对时序关系进行一致性检验，在模型的基础上提出了一种时序关系推理算法，这种推理算法基于TPN模型的性质及基本不等式规则，可由一组已知的扩展时段时序关系推出一些未知的扩展时段时序关系，这种推广理算法的优势在于利用了TNP模型的分析技术，减小了推理的时间复杂度比单纯利用不等式规则的推理更直观，也更简单，是一种有效的方法，最后，对扩展时段时序逻辑的TPN模型进行了扩充，增强了其模型和分析的能力。     

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

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

扩展时段时序逻辑的推理机制

该文在扩展时段时序逻辑的基础上提出了一种推理机制，这种推理机制基于时间Petri网模型及基本不等式规则，可由一组已知的扩展时段时序关系推出一些未知的扩展时段时序关系，对不确定时间段内发生的事件及其相互关系具有较好的描述能力，这种推理机制的优势在于定性地对扩展时段之间的时序关系进行推理分析，利用时间Petri网模型，可以对复杂时序逻辑关系进行化简，比单纯利用不等式规则的推理更直观，也更简单，是一种行之有效的方法。