Classification and evaluation of timed running schemas for workflow based on process mining

The system running logs of a workflow contain much information about the behavior and logical structure between activities. In this paper, a mining approach is proposed to discover the structural and temporal model for a workflow from its timed running logs. The mining results are represented in the formalized form of Petri nets extended with two timing factors that allows validation or verification the actual behaviors, especially the temporal constraints between activities. According to the reachability graph of the extended Petri net model mined, all running schemas of a workflow can be generated, which defines the temporal constraints between running activities. By calculating the earliest and latest start time of each activity, the earliest starting and latest existing time of each state in the running schema can be determined. Based on the temporal relations between the timing factors of each running state, the running schemas can be classified into six classes. The effects of the six classes of running schemas on the implementation of the whole workflow are evaluated so as to obtain the best one that can ensure the workflow is finished in the shortest time. The standards for the ideal, reliable and favorable running schemas and their existence conditions are discussed, which can be used to evaluate the running logs and control the future running of a workflow.     

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

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

Performance modeling and analysis of workflow

Workflow model analysis is performed at logic, temporal, and performance levels. This paper mainly deals with the performance level issues. Workflow net (WF-net) is extended with time information to the timing workflow net (TWF-net). To provide a formal framework for modeling and analyzing workflow, this paper proposes a multidimension workflow net (MWF-net) that include multiple TWF-nets and the organization and resource information. The algorithm to decompose a free-choice and acyclic Petri nets (PN) into a set of T-components is extended to a TWF-net containing iteration structures. Then, resource availability and workload analysis is performed. A method for computing the lower bound of average turnaround time of transaction instances processed in a MWF-net is proposed. Finally a case study is used to show that the proposed method can be effectively utilized in practice.     

一个基于TWF-net的扩展时间工作流模型及其应用

时间约束是分布式企业工作流程建模中的一个重要因素．基于时间Petri网工作流模型(TWF-net)，通过分析TWF-net模型不足之处，建立了一种新的时间Petri网工作流模型——扩展时间Petri网工作流模型(XTWF-net)．通过构建规则，可将多个TWF-net合并为一个XTWF-net，以描述并行流程中的时间约束；通过引入与时区相关的时间映射函数，XTWF-net可以描述分布于不同时区的流程．最后给出一个利用XTWF-net描述分布式企业中业务流程的实例．     

基于时间Petri网的工作流模型分析

工作流管理的最终目的是实现适当的人在适当的时间执行适当的活动.企业要获得竞争力,需要在工作流模型中考虑与业务过程相关的时间约束.一个考虑时间因素的工作流模型,需要在投入运行前进行时间规范与验证,以保证工作流执行的时间协调.通过为工作流网元素扩展时间属性,得到集成业务过程时间约束的工作流模型??时间约束工作流网(TCWF-nets).基于对业务活动的可调度性分析,提出了时序一致性验证方法,确保工作流执行中活动之间时间交互的安全性.在所附加的时间约束下,该可调度分析方法不仅能够检测某一给定工作流调度的时间可行性,还能对特定的实例给出一个最优调度,使工作流执行延迟最小.研究结果表明,该方法支持业务过程的时间建模与分析,对于丰富现有工作流系统的时间管理功能以及增强现存工作流软件对动态业务环境的适应性具有重要意义.     

时间约束工作流的可调度性分析

提出一种时间约束工作流的可调度性分析方法。针对时间约束Petri网（Timing Constraint Petri Nets,TCPN）为普通Petri网无法建模多参与资源的不足,给出了扩展的时间约束Petri网（w-TCPN）的定义;结合w-TCPN的拓扑结构,从模型和实例两个层次,给出了w-TCPN变迁可调度的判定定理;提出了时间约束的调整策略。w-TCPN的研究使得时间约束工作流的建模和可调度性分析更加合理。     

基于资源和时间限制的多工作流网及可调度性验证

工作流建模阶段的验证工作对工作流的成功执行具有重要意义.首先分析了与工作流执行密切相关的资源和时间特性,考虑到工作流应用系统中总是有若干工作流并发执行,于是综合考虑结构、时间、资源限制三个层面,提出一个工作流应用系统一般性限制框架.基于该框架提出了多工作流网原型,并进一步给出了多工作流网下资源冲突和可调度性的概念,最后给出了多工作流网可调度性验证算法及其冲突解决方案.     

Dwelling time probability density distribution of instances in a workflow model

This paper presents a method to judge whether a business process is successful or not. A business process is deemed successful if a large enough proportion of instances dwell in a workflow (wait and be executed) for less than given period. By analyzing instances’ dwelling time distribution in a workflow, the proportion of instances which dwell in the workflow for less than any given period will be achieved. The performance analysis of workflow model plays an important role in the research of workflow techniques and efficient implementation of workflow management. It includes the analysis of instances’ dwelling time distribution in a workflow process. Multidimensional workflow net (MWF-net) includes multiple timing workflow nets (TWF-nets) and the organization and resource information. The processes of transaction instances form a queuing model in which the transaction instances act as customers and the resources act as servers. The key contribution of this paper is twofold. First, this paper presents a theoretical method to calculate the instances’ dwelling time probability density in a workflow where the activities are structured and predictable. Second, by this method the analysis of instances’ dwelling time distribution and satisfactory degree based on dwelling time can be achieved. The service time of an instance is specified by the firing delay of the corresponding transition (executing time of the corresponding activity). It is assumed that the service request (processing of a transaction instance) arrives with exponentially distributed inter-arrival times and the firing delay of a transition (executing time of the corresponding activity) follows exponential distribution. Then, the instances’ dwelling time probability density analysis in each activity and each control structure of a workflow model is performed. According to the above results a method is proposed for computing the instances’ dwelling time probability density in a workflow model. Finally an example is used to show that the proposed method can be effectively utilized in practice.     

延迟时间Petri网的验证分析

延迟时间Petri网（Delay Time Petri Nets，DTPN）是一类重要的时间扩展Petri网系统，解决了其他时间扩展Petri网（如时间Petri网）在保存时间约束时所面临的困难。可调度验证的目的是验证工作流模型时间约束的合理性，对流程实例的时间可达性进行仿真。提出一种基于DTPN的时间约束工作流验证分析方法。给出了DTPN的相关定义，并结合工作流控制结构描述了变迁可触发的时间条件；提出了DTPN触发点的概念以及基于此的验证分析算法；简要分析了DTPN的特性。DTPN的研究丰富完善了现有时间Petri网体系，具有积极的意义。     

基于Petri网的工作流模型

Petri网是一种很有效的模型描述语言，不仅能描述系统的结构特性，同时还能描述其动态特性，尤其适用于描述含有并行成分的系统，而工作流技术作为实现企业过程集成的有效手段，广泛用于各种场合。在简要介绍了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.     

改进的工作流合理性验证方法

工作流建模过程中存在的结构冲突很有可能导致整个系统无法正常运行,因此验证工作流中的结构合理性是非常重要的。目前尚无一种简单的算法能够验证循环结构及交叉结构的合理性,为此提出了一种改进的工作流合理性验证方法。该方法基于Petri网模型,将逻辑推导和真值表相结合,能够简单而有效地检测出工作流中的各种结构冲突。应用示例表明了该方法的有效性。     

基于时间约束Petri网的工作流动态一致性检验

工作流系统中的时间管理是工作流建模和分析的重要组成部分。支持动态修改是人们在实际应用中对工作流系统提出的新要求。文中在基于时间约束的Petri网模型基础上,根据时间约束推理规则,提出一种动态修改时间约束时检验工作流一致性的方法,从而丰富了工作流的时间管理功能。     

一种基于Petri网的工作流元模型研究

Petri网是建立离散系统模型有力的数学工具。为了解决基本Petri网建模能力不足的问题,Aalst提出了有代表性的WF-Net模型。提出的HSC-PN工作流元模型,基于WF-Net扩展,增加了模型元素静态属性、数据流全局共享和增强的活动块等特性。详细阐述了HSC-PN元模型的DTD文件规范,分析了该模型对工作流模式的支持、触发机制及验证方式。通过可视化的建模工具,生成符合DTD文件规约的流程模板XML文件表示。HSC-PN元模型具有更丰富的元素描述信息,简化了流程模型,具有更强的建模能力。     

Enforcing QoS in scientific workflow systems enacted over Cloud infrastructures

The ability to support Quality of Service (QoS) constraints is an important requirement in some scientific applications. With the increasing use of Cloud computing infrastructures, where access to resources is shared, dynamic and provisioned on-demand, identifying how QoS constraints can be supported becomes an important challenge. However, access to dedicated resources is often not possible in existing Cloud deployments and limited QoS guarantees are provided by many commercial providers (often restricted to error rate and availability, rather than particular QoS metrics such as latency or access time). We propose a workflow system architecture which enforces QoS for the simultaneous execution of multiple scientific workflows over a shared infrastructure (such as a Cloud environment). Our approach involves multiple pipeline workflow instances, with each instance having its own QoS requirements. These workflows are composed of a number of stages, with each stage being mapped to one or more physical resources. A stage involves a combination of data access, computation and data transfer capability. A token bucket-based data throttling framework is embedded into the workflow system architecture. Each workflow instance stage regulates the amount of data that is injected into the shared resources, allowing for bursts of data to be injected while at the same time providing isolation of workflow streams. We demonstrate our approach by using the Montage workflow, and develop a Reference net model of the workflow.     

On Schedulability Analysis of AADL Architecture with Storage Resource Constraint

Embedded systems have been widely applied in real-time automatic control systems, and most of these systems are safety-critical, for example, the engine control systems in an automobile and the avionics in an airplane. It is very important to verify the schedulability of such a real-time embedded system in its early design stages, so as to avoid unexpected loss for the debugging of architecture design problems. However, it has been proved to be a tough challenge to evaluate the schedulability of a Preemptive-Scheduling Real-Time (PSRT) system, especially when the constraints of system resources are taken into consideration. The cache memory built inside the processor is an exclusive-accessing resource shared by all the tasks deployed on the processor. In addition, the Cache-Related Preemption Delay (CRPD) caused by preemptive task scheduling will bring extra time to the execution time for all the tasks. Thus, the CRPD should be taken into consideration when the Worst-Case Execution Time (WCET) of tasks is estimated in a real-time system. A model-based evaluation and verification method of architecture schedulability, which is designed for priority-based PSRT systems, is proposed in this study to make cache resource constrained and CRPD related schedulability evaluation based on the AADL system architecture model. In the first step, the study enhances the property set of AADL storage elements to make it compatible with cache memory properties in a system architecture model. Secondly, the study proposes a set of algorithms to estimate the CRPDs of a task before it is completed; run system schedule simulation and construct the schedule sequence with the constraint of cache resources and CRPDs involved; and make WCET estimation of the tasks in such a CRPD considered, preemptive-scheduling execution sequence. Finally, the methods mentioned above are implemented within a prototype software toolkit, which is designed to make evaluation and verification of system schedulability within CRPD constraints. The toolkit is tested with a use case of aircraft airborne open-architecture intelligent information system. The result shows that, compared with the schedule sequence constructed without cache memory resource constraints, the WCET estimated for most tasks is extended, and the sequence order is changed. In some extreme cases, when CRPD is taken into consideration, some tasks are evaluated to be incompletable. The test shows that the method and algorithms proposed in this study are feasible.     

Workflow performance analysis and simulation based on multidimensional workflow net

Workflow model performance analysis plays an important role in the research of workflow techniques and efficient implementation of workflow management. Instances dwelling times (IDT) which consist of waiting times and handle times in a workflow model is a key performance analysis goal. In a workflow model the instances which act as customers and the resources which act as servers form a queuing network. Multidimensional workflow net (MWF-net) includes multiple timing workflow nets (TWF-nets) and the organization and resource information. This paper uses queuing theory and MWF-net to discuss mean value and probability distribution density function (PDDF) of IDT. It is assumed that the instances arrive with exponentially distributed inter-arrival times and the resources handle instances within exponentially distributed times or within constant times. First of all, the mean value and PDDF of IDT in each activity is calculated. Then the mean value and PDDF of IDT in each control structure of a workflow model is computed. According to the above results a method is proposed for computing the mean value and PDDF of IDT in a workflow model. Finally an example is used to show that the proposed method can be effectively utilized in practice.     

A practical method to analyze workflow logic models

The analysis of workflow is crucial to the correctness of workflow applications. This paper introduces a simple and practical method for analyzing workflow logic models. Firstly, some definitions of the models and some properties, such as throughness, no‐redundant‐transition and boundedness, are presented. Then, we propose an approach based on synchronized reachability graphs (SRGs) to verify these properties. The SRG uses the characteristics of synchronizers in workflow logic models and mitigates the state explosion by constructing synchronized occurrence sequences rather than interleaving occurrence sequences. This paper also proposes some refined and feasible reduction rules which can preserve vital properties of workflow logic models. Using these two techniques, the SRG‐based verification method can achieve higher efficiency. Furthermore, this research also develops a verification tool based on the method, presents the analysis results of some practical cases and compares our method with others. Copyright © 2007 John Wiley & Sons, Ltd.     

Modeling and Analysis for Workflow Constrained by Resources and Nondetermined Time: An Approach Based on Petri Nets

Time and resource management and verification are two important aspects of workflow management systems. In this paper, we present a modeling and analysis approach for a kind of workflow constrained by resources and nondetermined time based on Petri nets. Different from previous modeling approaches, there are two kinds of places in our model to represent the activities and resources of a workflow, respectively. For each activity place, its input and output transitions represent the start and termination of the activity, respectively, and there are two timing functions in it to define the minimum and maximum duration times of the corresponding activity. Using the constructed Petri net model, the earliest and latest times to start each activity can be calculated. With the reachability graph of the Petri net model, the timing factors influencing the implementation of the workflow can be calculated and verified. In this paper, the sufficient conditions for the existence of the best implementation case of a workflow are proved, and the method for obtaining such an implementation case is presented. The obtained results will benefit the evaluation and verification of the implementation of a workflow constrained by resources and nondetermined time.