精炼工作流网的行为保持性质

本文定义了工作流网的精炼操作,研究了精炼工作流网的行为保持性质。结果表明精炼工作流网满足行为保持性质,即精炼工作流网的行为与原网和子网行为保持一致。在精炼工作流网行为保持性质的基础上,给出了基于原网语言和子网语言的精炼工作流网的语言刻画。本文结果有助于复杂工作流的设计、建模和验证。     

Three fundamental dimensions of scientific workflow interoperability: Model of computation, language, and execution environment

We investigate interoperability aspects of scientific workflow systems and argue that the workflow execution environment, the model of computation (MoC), and the workflow language form three dimensions that must be considered depending on the type of interoperability sought: at the activity, sub-workflow, or workflow levels. With a focus on the problems that affect interoperability, we illustrate how these issues are tackled by current scientific workflows as well as how similar problems have been addressed in related areas. Our long-term objective is to achieve (logical) interoperability between workflow systems operating under different MoCs, using distinct language features, and sharing activities running on different execution environments.     

A hierarchy of the class of apex NLC graph languages by bounds on the number of nonterminal nodes in productions

 In this paper, we consider derivation trees in apex NLC graph languages. We show that for every graph H in arbitrary apex NLC graph language, a decomposition tree of H can be constructed from a derivation tree of H. We also show that there exists a hierarchy in the class of apex NLC graph languages when we restrict the number of nonterminals in the right-hand sides of productions in apex NLC graph grammars. Received: 5 July 1994/12 February 1996     

Improving process models by discovering decision points

Workflow management systems (WfMS) are widely used by business enterprises as tools for administrating, automating and scheduling the business process activities with the available resources. Since the control flow specifications of workflows are manually designed, they entail assumptions and errors, leading to inaccurate workflow models. Decision points, the XOR nodes in a workflow graph model, determine the path chosen toward completion of any process invocation. In this work, we show that positioning the decision points at their earliest points can improve process efficiency by decreasing their uncertainties and identifying redundant activities. We present novel techniques to discover the earliest positions by analyzing workflow logs and to transform the model graph. The experimental results show that the transformed model is more efficient with respect to its average execution time and uncertainty, when compared to the original model.     

基于图结构的工作流技术分析和研究

通过对工作流基本组成元素和工作流动作特点的分析,利用工作流开展的时间差和人力资源的复用性,从并行工程的角度出发,提出了一种基于产品逻辑结构的柔性工作流思想,根据这一思想,结合产品形成过程的逻辑关系,利用有关图论的知识,构造了一个基于全息树结构的柔性工作流模型,实现了逻辑信息、工作流程的有机融合,同时也给出了支持这种柔性工作流模型的后台关系数据库结构。     

When does a workflow complete?

Workflow Management Systems (WFMS) coordinate execution of logically related multiple tasks in an organization. Each workflow that is executed on such a system is an instance of some workflow schema. A workflow schema is defined using a set of tasks that are coordinated using dependencies. Workflows generated from the same schema may differ with respect to the tasks executed. An important issue that must be addressed while designing a workflow is to decide what tasks are needed for the workflow to complete — we refer to this set of tasks as the completion set. Since different tasks are executed in different workflow instances, a workflow schema may be associated with multiple completion sets. Incorrect specification of completion sets may prohibit some workflow from completing. This, in turn, will cause the workflow to hold on to the resources and raise availability problems. Manually generating these sets for large workflow schemas can be an error-prone and tedious process.Our goal is to automate this process. We investigate the factors that affect the completion of a workflow. Specifically, we study the impact of control-flow dependencies on completion sets and show how this knowledge can be used for automatically generating these sets. We provide an algorithm that can be used by application developers to generate the completion sets associated with a workflow schema. Generating all possible completion sets for a large workflow is computationally intensive. Towards this end, we show how to approximately estimate the number of completion sets. If this number exceeds some threshold specified by the user, then we do not generate all completion sets.     

The relationship between workflow graphs and free-choice workflow nets

Workflow graphs represent the main control-flow constructs of industrial process modeling languages such as BPMN, EPC and UML activity diagrams, whereas free-choice workflow nets are a well understood class of Petri nets that possesses many efficient analysis techniques. In this paper, we provide new results on the translation between workflow graphs and free-choice workflow nets.We distinguish workflow graphs with and without inclusive Or-logic. For workflow graphs without inclusive logic, we show that workflow graphs and free-choice workflow nets are essentially the same thing. More precisely, each workflow graph and each free-choice workflow net can be brought into an equivalent normal form such that the normal forms are, in some sense, isomorphic. This result gives rise to a translation from arbitrary free-choice workflow nets to workflow graphs.For workflow graphs with inclusive logic, we provide various techniques to replace inclusive Or-joins by subgraphs without inclusive logic, thus giving rise to translations from workflow graphs to free-choice nets. Additionally, we characterize the applicability of these replacements. Finally, we also display a simple workflow graph with an inclusive Or-join, which, in some sense, cannot be replaced. This shows a limitation of translating inclusive logic into free-choice nets and illustrates also a difficulty of translating inclusive logic into general Petri nets.     

Log-based transactional workflow mining

A continuous evolution of business process parameters, constraints and needs, hardly foreseeable initially, requires a continuous design from the business process management systems. In this article we are interested in developing a reactive design through process log analysis ensuring process re-engineering and execution reliability. We propose to analyse workflow logs to discover workflow transactional behaviour and to subsequently improve and correct related recovery mechanisms. Our approach starts by collecting workflow logs. Then, we build, by statistical analysis techniques, an intermediate representation specifying elementary dependencies between activities. These dependencies are refined to mine the transactional workflow model. The analysis of the discrepancies between the discovered model and the initially designed model enables us to detect design gaps, concerning particularly the recovery mechanisms. Thus, based on this mining step, we apply a set of rules on the initially designed workflow to improve workflow reliability. The work presented in this paper was partially supported by the EU under the SUPER project (FP6-026850) and by the Lion project supported by Science Foundation Ireland under Grant No. SFI/02/CE1/I131.     

一种改进的基于模板的工作流过程定义方法

随着工作流技术在企业业务流程管理中的广泛应用,人们对工作流管理系统的描述能力和动态变更能力提出了更高的要求。针对目前的工作流过程定义方法在这两个方面的不足,本文提出了一种基于模板机制的工作流过程定义方法。该方法在现有的工作流过程定义模型的基础上,加入了新的过程模板和活动接口元素。本文由此扩展了工作流过程定义语言,增加了支持模板描述的机制。实际应用的结果表明,该方法和现有的工作流过程定义方法相比,显著提高了模型描述能力,使得过程模型具有了较强的可重用性和可扩展性,并具备了一定的动态变更能力。     

aH算法:工作流挖掘中一种能挖掘隐含任务的扩展a算法

正确发现流程实际运作情况对工作流管理有着重要的意义。工作流挖掘抽取系统日志信息,挖掘流程的真实运作模型。其中挖掘隐含任务是工作流挖掘中待研究问题之一。基于a算法,提出了能挖掘隐含任务的挖掘算法aH。分析了隐含任务出现的可能情况,通过判断并行任务的位置关系,往工作流网中添加隐含任务;然后合并相同的隐含任务,去掉冗余隐含任务,以完善结果模型。实现了。算法原型,实验证实了方法的可行性及有效性,并分析了方法的不足之处。     

工作流过程定义规范

1 引言工作流过程定义规范定义了一个通用的交换格式,对业务流程进行形式化的说明。这种通用的交换格式,可支持不同产品间过程定义的传送。规范也内在地包括了开发环境和运行环境形式上的分离,这使得由建模工具生成的过程定义,能作为许多其它WFMS运行时产品的输入,符合了用户所要求的建模和产品运行的独立性。     

一种提高系统柔性的工作流模型

工作流技术是实现过程集成的有效途径之一，其研究和应用日益受到重视。工作流模型是工作流技术的重要组成部分，本文介绍了一种基于活动网络的柔性工作流模型，从模型的角度描述了组成工作流的基本元素类型及图形表示，讨论了此工作流模型的形式定义，并给出了一个工作流模型的例子。     

基于Web的工作流引擎设计

给出了一个基于Web的工作流引擎的设计方案，它以工作流管理联盟(Workflow Management Coalition)的XPDL(XML Process Definition Language)语言为过程定义语言，用J2EE架构构建系统。并介绍了工作流管理系统的设计。     

一种基于XML的工作流过程定义语言

主要阐述在FlowStep中所使用的基于XML的工作流过程定义语言。FlowStep是一种基于Web的分布式工作流管理系统。在本系统的工作流过程建模中,根据不同类型的任务,分别定义其XML文件,并最终生成一个可以被工作流引擎解释的工作流过程定义。     

一种基于XML的工作流过程定义语言研究与应用

针对目前工作流过程描述语言灵活性不够的问题,从工作流系统的Web化以及适应异构应用环境角度出发,将工作流过程定义与工作流执行相分离,继承了WfMC的XPDL标准和XML的优点,提蹬了一种基于XML的工作流定义语言XML—WfPDL,并介绍了语言的设计思想、主要概念及实现的相关技术。最后,给出了利用该语言开发实现的一个网上审批软件系统。     

All Structured Programs Have Small Tree Width and Good Register Allocation

The register allocation problem for an imperative program is often modeled as the coloring problem of the interference graph of the control-flow graph of the program. The interference graph of a flow graphGis the intersection graph of some connected subgraphs ofG. These connected subgraphs represent the lives, or life times, of variables, so the coloring problem models that two variables with overlapping life times should be in different registers. For general programs with unrestricted gotos, the interference graph can be any graph, and hence we cannot in general color within a factorO(n) from optimality unless NP=P. It is shown that if a graph has tree widthk, we can efficiently color any intersection graph of connected subgraphs within a factor (k/2+1) from optimality. Moreover, it is shown that structured (≡goto-free) programs, including, for example, short circuit evaluations and multiple exits from loops, have tree width at most 6. Thus, for every structured program, we can do register allocation efficiently within a factor 4 from optimality, regardless of how many registers are needed. The bounded tree decomposition may be derived directly from the parsing of a structured program, and it implies that the many techniques for bounded tree width may now be applied in compiler optimization, solving problems in linear time that are NP-hard, or even P-space hard, for general graphs.     

Coding of chemical structures based on a line notation

An algorithm for coding of chemical structures is proposed based on a chemistry oriented line notation language. The latter is based on simple rules providing an almost convention free specification of molecular connectivity. A very useful feature of the proposed molecular code is that it has a line notation form, i.e. it can be interpreted according to the line notation language rules. Both the line notation language and molecular code are based on the principle of decomposition of the molecular graph into biconnected components (cyclic fragments or single atoms). The decomposition graph is a tree, each vertex of which stands for a biconnected component. Within the coding algorithm first the codes for each biconnected component are formed and then they are used as vertex labels of the decomposition tree. Since large chemical graphs usually consist of several biconnected components this method improves, to a great extent, the average time complexity of the algorithm. Terminal cyclic radicals and chain fragments of the molecular graph appear as unique substrings in the line notation code which enhances their computer perception.     

On verification of nested workflows with extra constraints: From theory to practice

Workflows are used to formally describe processes of various types such as business and manufacturing processes. One of the critical tasks of workflow management is automated discovery of possible flaws in the workflow – workflow verification. In this paper, we formalize the problem of workflow verification as the problem of verifying that there exists a feasible process for each task in the workflow. This problem is tractable for nested workflows that are the workflows with a hierarchical structure similar to hierarchical task networks in planning. However, we show that if extra synchronization, precedence, or causal constraints are added to the nested structure, the workflow verification problem becomes NP-complete. We present a workflow verification algorithm for nested workflows with extra constraints that is based on constraint satisfaction techniques and exploits an incremental temporal reasoning algorithm. We then experimentally demonstrate efficiency of the proposed techniques on randomly generated workflows with various structures and sizes. The paper is concluded by notes on exploiting the presented techniques in the application FlowOpt for modeling, optimizing, visualizing, and analyzing production workflows.     

面向对象的工作流建模工具的设计与实现

在工作流技术和方法的基础上,深入研究了WfMC工作流参考模型、工作流常用建模方法和过程定义语言,采用面向对象的建模方法对工作流进行建模,最后结合实例验证了设计器在处理复杂的工作流过程中具有一定的应用价值,从而为今后工作流的动态执行模型的建立打下了良好的基础.