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.     

Verifying soundness of business processes: A decision process Petri nets approach

This paper presents a trajectory-tracking approach for verifying soundness of workflow/Petri nets represented by a decision-process Petri net. Well-formed business processes correspond to sound workflow nets. The advantage of this approach is its ability to represent the dynamic behavior of the business process. We show that the problem of finding an optimum trajectory for validation of well-formed business processes is solvable. To prove our statement we use the Lyapunov stability theory to tackle the soundness verification problem for decision-process Petri nets. As a result, applying Lyapunov theory, the well-formed verification (soundness) property is solved showing that the workflow net representation using decision process Petri nets is uniformly practically stable. It is important to note that in a complexity-theoretic sense checking the soundness property is computationally tractable, we calculate the computational complexity for solving the problem. We show the connection between workflow nets and partially ordered decision-process Petri net used for business process representation and analysis. Our computational experiment of supply chains demonstrate the viability of the modeling and solution approaches for solving computer science problems.     

Development of context-aware workflow systems based on Petri Net Markup Language

The Petri Net Markup Language (PNML) is originally an XML-based interchange format for Petri nets. Individual companies may specify their process models in Petri nets and exchange the Petri nets with other companies in PNML. This paper aims to demonstrate the capabilities of PNML in the development of applications instead of an industrial interchange format only. In this paper, we apply PNML to develop context-aware workflow systems. In existing literature, different methodologies for the design of context-aware systems have been proposed. However, workflow models have not been considered in these methodologies. Our interests in this paper are to propose a methodology to automatically generate context-aware action lists for users and effectively control resource allocation based on the state of the workflow systems. To achieve these objectives, we first propose Petri net models to describe the workflows. Next, we propose models to capture resource activities. Finally, the interactions between workflows and resources are combined to obtain a model for the whole processes. Based on the combined model, we propose architecture to automatically generate context-aware graphical user interface to guide the users and control resource allocation in workflow systems. We demonstrate our design methodology using a health care example.     

A Petri Net Approach to Support Resource Assignment in Project Management

Petri nets have long been used in modeling and simulating project execution because of their great capability to describe concurrent activities and simulate the evolvement of processes. Although a number of extended Petri net models have been proposed to model and simulate resource sharing and activity dependence in projects, none of them has ever included a resource assignment mechanism into their models. Because resource assignments influence how limited resources are allocated among conflicting activities, they may heavily affect the availability of resources and the execution of projects. Therefore, a model without considering resource-sharing and resource assignment strategies may lead to a misunderstanding about project scheduling, resource consumption behaviors, and estimated project time. Accordingly, this paper proposes a new extended Petri net model that can describe how resources are shared and assigned among concurrent activities of multiple projects. The proposed model is named as resource assignment Petri net (RAPN), which extends an object composition Petri net with new places, transitions, attributes, and firing rules to model resource-sharing and resource assignment strategies. Finally, we prove that RAPN can correctly model the resource consumption behaviors of projects and can correctly compute the total elapsed time of projects.     

Modeling and monitoring of E-commerce workflows

Electronic commerce (E-commerce) is an important Internet application that is significantly changing the way of commercial transaction. Due to the complexity of E-commerce systems and lack of well-designed formal models, providing a suitable method for their modeling and monitoring turns out to be a challenging job. This paper introduces labeled workflow nets (LWN) and their semantics on the basis of labeled Petri nets. Then an inter-organizational labeled workflow net (ILWN) - which can graphically model the dynamic behavior of the systems - is presented. Furthermore, the nonblocking property of ILWNs is defined to achieve a common goal of E-commerce participants. This nonblocking property helps to analyze the soundness of ILWNs and the undeniable property of interactive actions. The proposed framework for E-commerce workflows (ECW) can record a history of interactive events and monitor the execution of interactive activities to achieve a common goal. Therefore, it can elegantly model the execution of interorganizational workflows and analyze the accountability of cooperative activities. The main contribution of the paper is to present a new formal mechanism - ILWN. It can efficiently support the modeling and monitoring of ECWs. Finally, this paper illustrates how to use the proposed method by modeling and analyzing a Customer-Producer-Supplier example.     

Can I find a partner? Undecidability of partner existence for open nets

We study open nets as Petri net models of web services, with a link to the practically relevant language WS-BPEL. For those nets, we investigate the problem of operability which we consider as fundamental as the successful notion of soundness for workflow nets, i.e., Petri net models of business processes and workflows. While we could give algorithmic solutions to the operability problem for subclasses of open nets in earlier work, this article shows that the problem is in general undecidable.     

基于Petri网的工作流过程建模

业务过程建模是整个工作流管理系统的基础,选择一种高效的建模技术对复杂多变的实际业务流程进行形式化表示对构建一个灵活的工作流管理系统起着至关重要的作用。本文利用了Petri网技术给业务过程建模,构造了一个灵活可分析的过程模型：首先介绍了相关的基于Petri网的工作流建模技术,接着描述了Petri网到工作流过程模型执行的映 射,然后给出了一个具体的基于Petri网建模方式的实例,最后利用随机Petri网和概率论的一些知识对该模型进行了时间性能分析。     

基于办公自动化系统的工作流模型与算法设计

随着计算机科学的飞速发展,大多数企事业单位都实施了办公自动化系统(OA)。而工作流技术是实现业务过程管理自动化的核心技术。通过对业务流程建模和业务流程实体的建模分析,设计了基于Petri网办公自动化系统的工作流原型系统。在现有Petri网和WF-net理论的基础上,设计了工作流实现算法,研究并建立了办公自动化系统的精简工作流模型。     

基于时间Petri网的工作流建模

随着工作流管理的发展,人们提出了很多扩展Petri网概念用于工作流建模。描述工作流中的资源、资源条件以及任务与资源条件之间的关系是一件很复杂的事情。而现有的用于描述工作流的Petri网在这方面,并不令人满意。该文特别强调资源的概念,在时间Petri网的基础上提出了一种新Petri网———资源条件/任务网(ResourceCondition/Tasknet,简称RC/TN),利用RC/TN网来进行工作流建模,描述工作流的执行过程。并将该工作流建模方法应用于OA流程的描述中。     

基于主动工作流视图的跨组织工作流管理和监控

跨组织工作流可以有效的利用不同企业的资源,提高企业的生产率,因而得到了越来越广泛的应用。如何使企业在增强对外交互能力的同时,保护企业内部的敏感信息,是跨组织工作流应用中的重要问题。工作流视图能有选择的隐藏企业私有工作流的细节,同时对外提供面向过程的接口,是一种有效的实现跨组织工作流的方法。在引入主动工作流视图概念的基础上,提出基于主动工作流视图的跨组织工作流管理和监控的体系结构,探讨了跨组织工作流的主动监控及其实现。     

基于反应型的Petri网工作流业务过程建模

传统的基于令牌机制的Petri网工作流模型虽然被广泛应用,但不能完整准确地反映工作流引擎运行时的实际情况。在充分考虑了系统运行时的实际场景之后,提出了一种基于反应型机制的Petri网工作流模型;然后分析了标准Petri网工作流模型到反应型Petri网工作流模型的转换方法和实现步骤,并给出了验证的思路。     

Petri net techniques for process planning cost estimation

The problem under consideration is the cost estimation of operation sequencing for nonlinear process planning, i.e. taking into consideration processing alternatives. In order to determine overall costs for feasible process plans, we take into account in our Petri net model of manufacturing process planning the costs caused by machine, setup and tool changing in addition to the pure operation cost. We present two modelling and cost estimation techniques based on Petri nets. Both are based on a new Petri net model: the PP-net (Process Planning net) which represents manufacturing knowledge in the form of precedence constraints and incorporates the cost of machining operation in each operation transition. The first method is based on building a complex Petri net called PPC-system (Process Planning Cost system) by integrating the PP-net and separate Petri nets describing the costs of machine, setup and tool changing. The second method proceeds in the cost calculation by attaching a specific data structure to each PP-net transition which describes the associated machine, setup and tool for the operation modelled by that transition. We apply the developed methods and calculate the optimum process plan to an industrial case study of a mechanical workpiece of moderate complexity.     

着色时间工作流网任务调度的时间约束分析

为实现工作流管理系统中的任务调度和时间管理,避免流程在多任务运转时产生溢出,提高流程的工作效率。采用不固定时延定义了着色时间Petri网,通过控制任务间的最小时距避免了溢出,并用任务监测器实现了相应的控制策略。以各任务间的时间间隔最小为优化目标,对串行、并行、条件选择和循环四种基本着色时间工作流网进行了时序分析和任务调度,推导出多任务在基本着色时间工作流网调度的数学模型和着色时间工作流网整体运行时间函数的计算公式。最后通过一个审批流程对论述的任务调度方法进行了验证。     

CorPN: managing instance correspondence in collaborative business processes

Driven by the booming global business, organisations are required to align their business processes into an inter-connected network. The sophisticated nature of collaboration results in dynamic and complex interactions and correlations between participating business processes. This inevitably poses challenges to business process management in terms of recognising the instance correspondence and analysing the interaction behaviours of collaborative business processes. Nevertheless, this issue has received very limited attention from inter-organisational workflow research. In this paper, a novel correspondence Petri net model called CorPN is developed to specify instance correspondence with extensions to classical WF-Nets. In addition, a method is established to analyse the behavioural properties of CorPN nets for the purpose of process verification and examination.     

基于Petri 网的工业设计过程管理工作流建模研究

工业设计过程建模是产品设计过程管理研究的关键环节,直接影响着项目开发周 期和整体效益,但目前工业设计行业没有针对设计过程管理有效的建模技术及其系统。为实现 对工业设计企业设计过程动态性、结构性和有序性管理,在产品设计过程管理中引入面向过程 的组织管理与流程优化的工作流技术及Petri 网建模方法;然后根据对设计过程管理流程的研 究,构建了设计过程管理工作流程图;进而结合工作流技术、Petri 网过程建模方法和工业设计 过程管理流程提出工业设计过程管理的4 个阶段工作流建模方法：本体分析、元素提取、元素 概括、元素带入;最后,以工业设计过程管理建模领域为例构建了基于Petri 网的工业设计过程 管理工作流模型,在此基础上实现了工业设计过程管理原型系统。     

Petri网的工作流模型建模研究

实现工作流技术的关键环节在于工作流的概念模型,而其中的过程建模又是构建工作流管理系统的基础,因此,对建立工作流模型的研究和应用比较多。近几年,随着业务流程建模、工作流概念的出现以及Petri网技术的发展,Petri网也被用于工作流模型的建立。该文在介绍工作流模型和Petri网基本概念的基础上,介绍工作流的四种基本流程结构,并以工作流的四种基本流程结构为出发点,给出了如何把它们映射成符合工作流网定义的模型的一种方法。     

Verifying workflow processes: a transformation-based approach

Workflow modeling is a challenging activity and designers are likely to introduce errors, especially in complex industrial processes. Effective process verification is essential at design time because the cost of fixing errors during runtime is substantially higher. However, most user-oriented workflow modeling languages lack formal semantics that hinders such verification. In this paper, we propose a generic approach based on the model transformation to verify workflow processes. The model transformation includes two steps: first, it formalizes the desirable semantics of each modeling element; secondly, it translates a workflow process with clear semantics to an equivalent Petri net. Thus, we can verify the original workflow process using existing Petri net theory and analysis tools. As a comprehensive case study, verifying workflow processes in an industrial modeling language (TiPLM) is presented. Experimental evaluations on verifying real-world business processes validate our approach.     

Collaborative composition of processes in holonic manufacturing systems

Although it provides a flexible architecture to deal with changes and uncertainties, holonic manufacturing systems (HMS) also pose challenges in design and implementation. A challenge is to design a problem solving environment to guide the holons in HMS such that the decisions made by the individual holons as a whole collaboratively compose the production processes for the tasks. The objective of this paper is to propose a problem solving environment for the composition of minimal cost processes in HMS. Given a specific product type and due date, the problem is to dynamically compose a complete process in HMS to process the product by the due date. To achieve the objective, we combine multi-agent systems technology with Petri nets in this paper. We first propose architecture and a two-layer contract net protocol to describe the negotiation between order holons, product holons and resource holons in HMS. To determine whether it is feasible for a set product holons and resource holons to compose a process for an order holon, we propose Petri net models to capture the workflows and activities in product holons and resource holons, respectively. To optimize the cost in the composed manufacturing process, the concept of activity-based costing is adopted to assign the cost of the activities to Petri nets. The advantages of our design methodology include specification of workflows and resource activities with PNML to minimize the cost. To realize the two-layer contract net protocol relies on a mechanism for a holon to discover the services provided by other holons. We proposed a scheme for publication and discovery of holon services based on FIPA compliant multi-agent system platform. Based on the service publication and discovery scheme, interactions between holons with the two-layer contract net protocol can be realized. We develop a HMS system to solve the process composition problem.     

基于时间约束Petri网的工作流可调度性分析

引入时间参数控制工作流高效执行是工作流技术研究的重要内容之一。在工作流的Petri网模型中引入时间参数,不仅可以对工作流中的活动进行时间约束,而且能建立相应的工作流时间约束Petri网模型。文中在分析该模型的时间约束和可调度性的基础上,提出了对工作流可调度性分析验证方法及其相应的算法,最后通过一个实例说明了分析验证的过程。     

Workflow mining: discovering process models from event logs

Contemporary workflow management systems are driven by explicit process models, i.e., a completely specified workflow design is required in order to enact a given workflow process. Creating a workflow design is a complicated time-consuming process and, typically, there are discrepancies between the actual workflow processes and the processes as perceived by the management. Therefore, we have developed techniques for discovering workflow models. The starting point for such techniques is a so-called "workflow log" containing information about the workflow process as it is actually being executed. We present a new algorithm to extract a process model from such a log and represent it in terms of a Petri net. However, we also demonstrate that it is not possible to discover arbitrary workflow processes. We explore a class of workflow processes that can be discovered. We show that the /spl alpha/-algorithm can successfully mine any workflow represented by a so-called SWF-net.