Using time stream Petri nets for workflow modelling analysis and enactment

Abstract

Timing requirements are important aspects in workflow modelling, analysis and enactment. In the last few years, though, many workflow languages and tools have been proposed but only few of them address timing issues during enactment. This paper shows that time stream Petri nets (TSPNs), originally designed for multimedia/hypermedia modelling and analysis, are a well-suited formalism also for supporting the whole lifecycle of workflow processes with timing constraints. A novel approach to modelling, analysis and distributed enactment of workflow processes specified by TSPNs is proposed. Functional and temporal properties of a TSPN model can be checked using exhaustive verification or a DEVS-based simulation tool. Enactment rests on PN-Engine, a decentralized enactment engine based on the service-oriented computing paradigm, which enables execution of workflow processes where the coordinated activities may involve cross-boundary organizations. The approach is illustrated by means of a modelling example concerned with a wine-production process.

Keywords

workflow modeling analysis enactment time stream Petri nets DEVS simulation service oriented computing

1 Introduction

A workflow model¹ represents a business process in a form that supports automated manipulation. A workflow defines a set of activities and a set of procedural rules that determine the specific order in which the activities must be executed to achieve a common goal. A workflow language should at least be capable of capturing moment of choice, sequential composition, parallel execution and synchronization.² All of these constructs can be naturally expressed by Petri nets (PNs). Formal semantics, local state-based system description, and abundant analysis techniques and tools make PNs a good choice for workflow management systems. Workflows are case-based, i.e. every piece of work is executed for a specific case. In the control-flow dimension, a workflow process specifies how a case is routed, i.e. which tasks need to be executed and in what order. Modelling such a process in terms of a PN is rather straightforward: tasks map on transitions, routing conditions can be expressed by places, and cases are modelled by tokens. The workflow state corresponds to the net marking. The control-flow dimension of a workflow is usually expressed by WF-nets³ which are classical PNs which satisfy some simple structural properties.

The original contribution of this paper is threefold: (i) an exploitation of time stream Petri nets (TSPNs)^4,5 for workflow modelling, (b) a realization of TSPN analysis tools, in particular a DEVS-based discrete-event simulation framework, and (c) a development of a decentralized service-based enactment infrastructure for TSPNs which is capable of handling timing specifications at runtime.

TSPNs are more powerful than well-known time Petri nets (TPNs)^6,7 often used for the specification of time-dependent systems. A basic enhancement with respect to TPNs concerns the ability of explicitly expressing timing constraints of tasks and then detecting constraint violations both at the single task (i.e. single transition firing) level and at task sequence level. TSPNs associate timing validity intervals to incoming arcs of transitions. This allows not only to model activity durations but also to express timing constraints on the availability of the resources needed for completing an activity. A weak synchronization model applies to arcs but, as in TPNs, a strong synchronization model is associated with transition firings. Transitions can be annotated with one of several firing rules which give great flexibility to the modeller.

Distributed enactment of workflows specified by TSPNs is achieved by extending the features of PN-Engine,⁸ a control engine for the distributed execution of systems specified by PNs. The engine is founded on the service-oriented computing paradigm.^9,10,11,12 A key feature of PN-Engine is the absence of a centralized coordination entity which allows net evolution to strictly adhere to PN local firing semantics, i.e. net dynamic behaviour is ‘responsibility’ of the single transitions. The approach notably differs from those described in other works^3,13,14 which instead depend on a centralized engine which coordinates the distribution of activities among different sites. PN-Engine offers functionalities for deploying a workflow, i.e. making it operational and controlling its execution. PN-Engine was also adapted to support dynamically reconfigurable workflows.⁸ Current PN-Engine implementation depends on Jini¹⁵ service infrastructure.

The paper is structured as follows. Section 2 describes some related work. Section 3 reviews TSPN concepts whilst their exploitation for modelling workflows is discussed in section 4. Section 5 describes a wine-production process (WPP) model which is used as a running case study throughout the paper. Section 6 discusses some developed analysis tools and particularly a DEVS-based^16,17,18 simulation framework. In this section too some experiments concerning the analysis of the proposed wine-production process model are reported. Section 7 discusses the PN-Engine architecture and its adaptation to handling TSPN timing requirements. Section 8 covers implementation aspects of timing constraints at runtime and deployment and enactment issues of the WPP case study. Finally, conclusions are drawn with directions which deserve further work.

2 Related work

The ability to express timing requirements during the specification phase of a workflow process opens up the possibility of carrying out qualitative and quantitative analysis that take into account timing information affecting the runtime behaviour of the process.

Simulation is a widely used technique for analysing a workflow model (e.g. for discovering errors in the process definition, finding unbalanced resource utilization and bottlenecks, etc.). Although an abundance of simulation tools exist, the applicability of these tools is diversified.^19,20 The development of effective simulation tools is a challenging activity mainly for what is related to the adoption of a suitable formalism that allows a seamless weaving between the analysis and the enactment of a workflow.²¹

Protos²² is a process modelling and analysis tool based on PNs. Nevertheless, it also permits the specification of business processes without using formal semantics, e.g. for supporting conceptual modelling. Processes can be analysed with respect to data, user and logic perspective. Simulation is used to evaluate utilization rates, waiting times, throughput times and costs.

General-purpose simulation tools are also used in the domain of workflow systems.^19,21 CPN Tools²³ allows editing, simulation and analysis of coloured Petri nets. A fast simulator efficiently handles both untimed and timed extended nets. Correctness of a developed model can be checked by existing PN techniques such as the generation of state spaces and the analysis of boundedness and liveness properties, which are all implemented in CPN Tools.

A technique for automatically extracting the simulation model of a running process has been proposed by Rozinat et al.²⁰ The approach is based on the YAWL infrastructure,²² on a process mining tool and CPN Tools. The original process model along with resource information, process state and event log history is feed into the process mining tool which produces a refined model shaped for simulation by CPN Tools.

Other approaches for workflow modelling and analysis, which use timed extensions of PNs, are known in the literature. TPNs⁶ allow the association of a time interval constraining the possible firing time of a transition. The usage of TPNs as workflow specification language has been discussed by Ling and Schmidt²⁴ where, however, timing information is considered only during analysis.

A timed version of WF-nets, named TCWF-nets and based on timing constraint Petri nets (TCPNs),²⁵ has been introduced by Li et al.²⁶ where it has been employed for schedulability and boundedness analysis of workflows. TCPNs extend TPNs by adding minimum, maximum, and duration timing constraints to places and/or transitions.

The R/NT_WF_Net formalism, proposed by Wang and Zeng,²⁷ admits two different types of places respectively modelling available resources and activities that are being executed. Each activity is associated with a timing interval corresponding to its possible durations. The usage of R/NT_WF_Net, though, is limited to modelling and timing analysis.

All of the above-mentioned approaches address specification and analysis issues but neglect aspects related to the interpretation of timing specifications during workflow enactment. The latter is a recognized important problem, however, which has been not adequately dealt with also in approaches not related to PNs.^28,29,30 In the following we consider some examples of approaches to workflow simulation based on the DEVS¹⁶ formalism.

A web-based workflow simulation system that relies on DEVS has been proposed by Hong et al.³¹ A workflow model is specified as a DEVS model which in turn is transformed into an intermediate relational algebra representation suitable to be stored and processed by standard relational database systems. Workflow simulation is accomplished by a standalone Java application (DEVSim-Java) which accesses the intermediate relational representation using standard Java Database Connectivity (JDBC) API.

An environment for the distributed simulation of workflow models based on DEVS has been presented by Zacharewicz er al.³² A business process model is first expressed in a custom description language and then automatically transformed into a G-DEVS (Generalized-DEVS)³³ model so as to be simulated over HLA.³⁴

An approach to runtime workflow simulation, where the enactment server is directly exploited also for simulation purposes, has been proposed by Choi et al.³⁵ and refined by Lee et al.³⁶ During simulation, worklist handlers (see also Section 7) are replaced by software entities, called participant simulators that locally reproduce the evolution of real participants. Time synchronization is handled by a synchronization manager module, which is also called a Mediator because it is also in charge of mediating the interactions among participant simulators and the enactment engine. The behaviours of the synchronization manager and that of the participant simulators are specified as DEVS models.

The approach described in this paper allows modelling, analysis and distributed enactment of workflows with timing constraints, where the TSPNs formalism is used in all of the phases of the process lifecycle. Workflow simulation relies on a mapping that transforms a TSPN model into an equivalent Parallel DEVS (PDEVS)¹⁶ model which is then fed to an efficient agent-based simulation tool.¹⁸ Although the DEVS formalism could be directly used for specifying a workflow model, its use would require the user to either to hand code basic workflow constructs or to resort to purposely designed reusable DEVS models which mimic them. In addition, the expression of timing constraints, their analysis and assessment would not be as natural as in TSPNs. Distributed enactment of TSPN workflow models depends on PN-Engine,⁸ which is a service-oriented infrastructure for the distributed execution of PN-based systems.

3 TSPNs

TSPNs^4,5 were originally introduced for modelling and analysis of multimedia/hypermedia systems. They are useful, more in general, for time-dependent systems where weak synchronization constraints may be adopted.

A TSPN is a tuple $(P, T, B, F, I_{nh}, M_{0}, IM, SYN, MA)$ where:

– $P$ is a finite non-empty set of places and $T$ is a finite non-empty set of transitions;

– $B$ is the backward incidence function, $B : P \times T \to ℕ$ and $F$ is the forward incidence function, $F : P \times T \to ℕ$ , where $ℕ$ denotes the set of natural numbers;

– $I_{nh}$ is the set of inhibitor arcs, $I_{nh} \subset P \times T$ where $(P, T) \in I_{nh} \Rightarrow B (p, t) = 0$ ;

– $M_{0}$ is the initial marking function, $M_{0} : P \to ℕ$ , which associates with each place a number of tokens;

– $IM$ is a function which associates with each arc, incoming to a transition, an interval defining its static temporal validity interval; $IM : A \to ℚ^{+} \times (ℚ^{+} \cup {\infty})$ , where $ℚ^{+}$ represents the set of non-negative rational values, $A = {a = (p, t) \in P \times T | B (p, t) \neq 0 \lor (p, t) \in I_{nh}}$ is the set of all incoming arcs and $IM (a) = [t_{min} (a), t_{max} (a)]$ is such that $t_{min} (a) \leq t_{max} (a)$ ;

– $SYN$ is a function which associates each transition with a firing rule $SYN : T \to {$ And, Weak-And, Or, Strong-Or, Master, Or-Master, And-Master, Strong-Master, Weak-Master, Pure-And $}$ ;

– $MA$ is a function that associates a master arc to each transition whose firing rule requires it, $MA : T_{m} : \to A$ , where $T_{m} = {t \in T | S Y N (t) \in$ {Master, Or-Master, And-Master, Strong-Master, Weak-Master $}}$ .

3.1 TSPN semantics

The marking of a TSPN is a function $M : P \to ℕ$ that associates each place with a number of tokens. An arc $a = (p, t) \in A$ is enabled by a marking $M$ iff: $a \in I_{nh} \Rightarrow M (p) = 0 \land a \notin I_{nh} \Rightarrow M (p) \geq B (p, t)$ . The set of arcs enabled by a marking $M$ is denoted by $enArc (M)$ . The set of incoming arcs of a transition $t$ is denoted as $A (t)$ . A transition $t$ is enabled by the marking $M$ iff: $A (t) \subseteq enArc (M)$ . The set of transitions which are enabled by a marking $M$ is denoted as $enabled (M)$ . The set of input places of a transition constitutes its preset. The set of output places of a transition is its postset. The state of a TSPN is defined as a pair $(M, I)$ where $M$ is a marking and $I$ is a mapping which associates each arc enabled by $M$ with a dynamic temporal validity interval, i.e. $I : enArc (M) \to ℚ^{+} \times (ℚ^{+} \cup {\infty})$ , $I (a) = [x (a), y (a)]$ . The initial state of a TSPN is given by $(M_{0}, I_{0})$ , where $\forall a \in enArc (M_{0})$ $I_{0} (a) = IM (a)$ . For any transition $t$ enabled by $M$ , its dynamic time interval $[low (t), up (t)]$ is determined as in Figure 1, where $a_{m} = MA (t)$ if $t \in T_{m}$ .

Figure 1.

Synch rules and dynamic firing interval.

In the case $low (t) > up (t)$ , $t$ is said to be violated. A transition $t$ is said to be fireable in $(M, I)$ if it is enabled in $M$ and not violated in $(M, I)$ . A transition $t_{f}$ , fireable in $(M, I)$ , may fire at relative time $θ$ if $low (t_{f}) \leq θ \leq min_{t \in fireable (M, I)} {up (t)}$ . Let $t$ be a transition fireable from state $S = (M, I)$ . The state $S' = (M', I')$ reached by firing $t$ at relative time $θ$ , is computed as $M' (p) = M (p) - B (p, t) + F (p, t)$ , $\forall p \in P$

{\begin{matrix} I' (a) = IM (a) if a \notin enArc (M) \lor a \notin enArc (\tilde{M}) \lor a \in A (t) \\ I' (a) = [max {x (a) - θ, 0}, y (a) - θ] otherwise \end{matrix}

where $\tilde{M} (p) = M (p) - B (p, t)$ , $\forall p \in P$ , i.e. $\tilde{M}$ is the intermediate marking resulting from the withdrawalsub-phase.

A transition $t'$ enabled in $M$ can lose its enabling during the atomic firing process of $t$ either in the intermediate marking $\tilde{M}$ or in the reached marking $M'$ . It is said to be non-persistent to the firing of $t$ . In contrast, a persistent transition (which is enabled in $M$ ) keeps its enabling during the whole firing process of $t$ . A transition is said newly enabled if it was not enabled in $M$ or in $\tilde{M}$ but it is enabled in $M'$ . While TPNs⁶ have only a strong semantics model for transition firings, TSPNs adopt a more flexible interpretation because timing constraints of arcs can be violated (i.e. current time is beyond the upper bound of the dynamic temporal validity interval of the arc) if the firing rule of the related transition allows it. In other words, a valid firing interval for an enabled transition may exist also in the case the timing constraints of some of the incoming arcs are violated. Once a valid timing interval is found for a transition, it constitutes a strong constraint on its firing. Therefore, TPSNs use a weak synchronization model for arcs but a strong one for transitions. A multiple enabled transition is assumed to fire its enablings one at a time (single server semantics). After its own firing, a transition $t$ which is still enabled is simply considered newly enabled.

3.2 Notes on the synchronization rules

The TSPN synchronization rules (see also Figure 2) can be driven by (a) the latest arriving process (And, Pure-And, Weak-And, And-Master) where the last arc that reaches the lower bound of its temporal interval allows the firing of its related transition, (b) the earliest arriving process (Or, Strong-Or, Or-Master) where the first arc which reaches its lower bound permits the firing of its related transition, and (c) the arriving of a statically selected process (Master, Strong-Master, Weak-Master), i.e. the transition can only fire when its master arc reaches the lower bound of its associated temporal interval.

Figure 2.

Summary of TSPN firing rules ( $P 2 - t$ is the master arc).

Differences between the And and Pure-And firing rules are useful to point out. When the temporal intervals overlap, they behave the same way: the transition can only fire in the intersection of the intervals. In the case some intervals are disjoint, at least one arc is violated when a process gets its minimum bound. In this situation, the And firing rule permits one single synchronization point which coincides with the lower bound of the latest arriving process. In other words, under the And firing rule a transition can always fire, but with the Pure-And the firing is impossible to occur when the intersection is void.

In the master scenario, Master and Or-Master are violated when the master arc is violated. In the case of a Strong-Master transition with a non-master arc already violated, there exists one single synchronization point which coincides with the lower bound of the dynamic interval of the master arc. Instead, a Weak-Master and And-Master can never be violated.

In any case, a transition can fire when it is both logically enabled (in the sense of classical PNs) and temporally ready (i.e. the lower bound of its dynamic temporal interval defined according to the adopted synchronization rule, has been reached). For simplicity, Figure 2 mirrors the absolute time model: the temporal validity intervals of the three arcs are absolutized with respect to the absolute time instants $t_{1}$ , $t_{2}$ and $t_{3}$ at which the arcs get logically enabled.

A subtle point of TSPN semantics is concerned with what we call the ‘last time point problem’. The problem is summarized in the TSPN model in Figure 3. Transition $T 1$ adopts the Master rule and the master arc is $P 2 - T 1$ . Transition $T 0$ can use the Pure-And rule. At time 5 transition $T 0$ should fire and at the same time the arc $P 2 - T 1$ has to decide whether it is violated or not. Owing to non-determinism the arc could conclude it is violated because transition $T 1$ is still disabled, but if the event of $T 0$ firing precedes that of violation check of the arc $P 2 - T 1$ , then at time 5 transition $T 1$ gets enabled and the arc detects it is not actually violated.

Figure 3.

A critical timing situation.

The problem can be solved by ensuring that all actions which occur at a given time are eventually completed before an arc can conclude it is violated. This is easy to achieve in simulation but can be less obvious in exhaustive verification.³⁷

4 TSPN as a workflow specification language

The use of TSPNs in the context of workflow modelling extends existing approaches based on basic PNs so as to enable quantitative and qualitative analysis of workflow behaviour while imposing synchronization constraints during the enactment. This work argues that TSPNs are an effective tool in the domain of workflow systems for two main reasons. First of all, timing intervals on arcs allow us to naturally express time constraints on both activities and resource utilization. Second, TSPNs have the capability of supporting different transition firing rules which are able to mirror different timing requirements in workflow process specification. In the following, the interpretation of transition firing in a workflow system is discussed and the effectiveness of TSPNs highlighted.

4.1 A workflow-based semantics of TSPN transitions

In the domain of workflow systems, the case of a transition which is bound to an activity to be performed usually raises two main interpretations of transition firing. In the first scenario the firing corresponds to the completion of an activity which has begun at the time the transition was enabled. In the second case the firing is associated with an atomic event corresponding to the start or the end of an activity. In this last case an activity, although in the state of being executed, is directly modelled in the net status by the marking of a place (see, for instance, place $PA$ in Figure 4(a)).

Figure 4.

Simple TSPN models.

Since TSPNs rely on race semantics for solving conflicts among transition firings, the first interpretation raises some issues concerning the meaning of the pre-emption of an activity during its execution and about concurrent utilization of a resource modelled by a place which is shared among conflicting transitions. As a consequence, as a general guideline, this work assumes that time intervals on input arcs of conflicting transitions are used to constrain the start/end events of modelled activities. In all other situations, arc temporal intervals can either express start/end events or the duration of activities. In the latter case, the firing of a transition will correspond to an end/completion event.

Given a workflow, the same activity can be carried out in different scenarios during process evolution. For instance, the activity of rejecting a loan can be executed even if the right documentation is not submitted at the right time or if a customer does not have the right requirements. To deal with these issues, a label can be associated with a transition. Each label uniquely identifies the activity (or the activity start/end event) to perform and the same label can be attached to multiple transitions.

Some simple excerpts of TSPN workflow models are reported in Figure 4. In Figure 4(a) the token in place $PC$ models a workflow case which, in order to be processed, requires the availability of a resource reflected by the marking of place $PR$ . The adopted Pure-And rule for transition $TS$ along with the time intervals attached to its incoming arcs impose that the resource is available to $TS$ only for a limited amount of time, i.e. from 2 to 3 time units since the corresponding token was put into place $PR$ . The firing of $TS$ models the start of the activity $A$ (see the label inside the angle brackets) whose execution is mirrored by a token into place $PA$ . The constraint of the arc $PA - TE$ models the activity duration whose completion is mirrored by the firing of transition $TE$ . In Figure 4(b), the And-Master rule is considered for transition $T$ . Here, the start of an activity requires a resource which in turn needs 2 time units to become usable (e.g. because of a setup operation) and then it is always ready to be used because the upper bound of the arc from $PR$ is ignored as implied by the adopted And-Master semantics. In Figure 4(c) the Strong-Master rule is used. Under this semantics, the lower bounds of all of the incoming arcs, except the master, are ignored. If at the time of the arrival of a token in $PR$ there is already a token into $PC$ , the transition may delay its firing up to the upper bound of the arc incoming from $PR$ . In contrast, when a token arrives into $PC$ after 3 time units from that of $PR$ , i.e. the arc from $PR$ is violated, the transition must fire as soon the master arc is fireable.

4.2 Specification and operational support of time patterns

Although temporal constraints have an important role in the context of business process management, the support of the time prospective appears limited in existing process management systems.^{28,29,30,38,39,40} Different time patterns were recently proposed in the literature^38,39 with the goal of systematic assessing and comparing timing issues. Time patterns can be used to analyse the expressiveness and effectiveness of an adopted modelling language and to evaluate the operational support to timing aspects offered by a workflow system.

With the exception of issues relevant to schedulability (e.g. the bank office is open on a weekday from 09:00 to 18:00 except for the legal holiday) and service-level agreement (e.g. a customer can contact the help desk up to five times every 24 hours), proposed patterns (time lag between activities, deadline, validity period, milestone and so forth)^38,39 reduce to consider: (i) time constraints between two events, (ii) time-dependent variability, i.e. the control flow of the process will vary due to time aspects. In the following, a short list of the so-called reduced patterns is proposed along with their TSPN modelling. Where not differently stated, the Pure-And firing rule for transitions and the default time interval $[0, \infty]$ for timing constraints on arcs are assumed.

4.2.1 Time lag between two events

This kind of pattern refers to a scenario where a time lag between two events needs to be respected. Let $e 1$ and $e 2$ be two events respectively associated with the firing of transitions $T 1$ and $T 2$ . Let $t (e 2)$ and $t (e 1)$ be the absolute times at which $e 2$ and $e 1$ respectively occur and let $[a, b]$ be a time interval with $a \in ℚ^{+}$ and $b \in ℚ^{+} \cup {\infty}$ and $a \leq b$ . The time lag constraint imposes that $t (e_{2}) \in [a + t (e 1), b + t (e 1)]$ . If $a = 0$ , then $e 2$ must not occur later than $b$ time units since $e 1$ , if $b = \infty$ then $e 2$ must not occur before $a$ time units elapsed since $e 1$ .

In Figures 5 and 6 are shown two TSPN models dealing with the time lag problem. Models are achieved by decorating transition $T 1$ and $T 2$ . This means that if a model already exists, e.g. the control flow dimension of a workflow is already defined, time lag constraints can be managed by simply decorating the original net.

Figure 5.

Time lag between two events: property checking.

Figure 6.

Time lag between two events: property enforcement.

Models in Figures 5 and 6 behave in a very different way from each other. In Figure 5 transition $T$ can fire only if $T 2$ fires in the interval $[a + t (e 1), b + t (e 1)]$ otherwise the arc $PA - T$ or $PB - T$ will become violated and, due to the Pure-And synchronization rule, transition $T$ never fires. As a consequence, the violation of one of the two arcs corresponds to the violation of the time lag constraint.

In Figure 6 the use of the Master synchronization rule ensures that: (i) if a token appears in place $P 2$ before the firing of $T 1$ then the firing of $T 2$ is deferred until its time becomes compliant with the time lag constraint; (ii) if the token in $P 1$ appears too late with respect to that in $P 2$ then the master arc becomes violated and $T 2$ never fires.

Decoration of Figure 5 does not modify the presets of transitions $T 1$ and $T 2$ . This means that the behaviour of the original net is not modified. As a consequence such decoration is useful for property checking, i.e. checking that the time lag constraint is satisfied during process evolution. Decoration of Figure 6 is useful instead for property enforcement, i.e. $e 2$ will occur in the system only if its time is compliant with the time lag constraint.

By using the Master rule in Figure 6, the dynamic firing interval of transition $T 2$ is determined only by the time interval associated with the master-arc. This means that, even if a token is already available in place $P 2$ when $T 1$ fires, the fire time of $T 2$ always belongs to $[a + t (e 1), b + t (e 1)]$ . To impose the additional constraint that $T 2$ has to be fired as soon as possible within the admitted time interval in the case $e 2$ is causally dependent on $e 1$ , i.e. $P$ is always marked when the arc $P 2 - T 2$ becomes enabled, Master can be equivalently replaced by Pure-And.

It is worthy of note that the time lag pattern could not be fully supported by using other time aware versions of PNs. For instance, by using TPNs,⁶ the constraint $t (e 2) \in [a + t (e 1), b + t (e 1)]$ cannot be expressed correctly but only as $t (e 2) \in [a + t (e 1), b + t (e 1))$ (for details refer to Boyer and Diaz⁷). Net behaviour is not deterministic in the last time point of the time lag constraint, i.e. a time violation could be signaled even if $e 2$ occurs exactly at time $b + t (e 1)$ (see also Section 3.2). Moreover, modelling the urgency of $T 2$ in Figure 6, which by using TSPN is simply obtained by changing the synchronization rule from Master to Pure-And, would require a net-redesign in the case other time aware versions of PNs are used. Similar considerations hold for the negative time lag pattern too.

4.2.2 Negative time lag between two events

This pattern is the dual of the time lag pattern. Let $e 1$ and $e 2$ be two events respectively associated with the firing of transitions $T 1$ and $T 2$ . Let $t (e 2)$ and $t (e 1)$ be the absolute times at which $e 2$ and $e 1$ respectively occur and let $a$ and $b$ be two time instants where $a \in ℚ^{+}$ and $b \in ℚ^{+} \cup {\infty}$ and $a \leq b$ . The negative time lag constraint imposes that $t (e 2) \leq t (e 1) + a \lor t (e 2) \geq t (e 1) + b$ , i.e. $t (e 2) \notin (a + t (e 1), b + t (e 1))$ . An important difference with respect to the time lag constraint is that $e 2$ can occur even if $e 1$ has not yet occurred. If $b = \infty$ , then $e 2$ must occur no later than $a$ time units since $e 1$ .

Figure 7 shows how to decorate transitions $T 1$ and $T 2$ in order to check whether the negative time lag constraint holds. The firing of transitions $Ta$ , $Tb$ , $Tc$ mirror the fact that $e 2$ is compliant with the negative time lag constraint. In particular, $Tc$ fires in the case $e 2$ occurs before $e 1$ ; $Ta$ fires in the case $t (e 2) \in [t (e 1), a + t (e 1)]$ ; $Tb$ fires if $t (e 2) \geq t (e 1) + b$ . The Master synchronization rule forces the dynamic firing interval of $Tc$ to depend only on the time constraint of the arc $PB - Tc$ . In the case the negative time lag constraint is not satisfied, $PB$ remains marked and all of its outgoing arcs will eventually become violated. The scenario where $b = \infty$ is simply achieved by removing transition $Tb$ .

Figure 7.

Negative time lag between two events: property checking.

In Figure 8 the negative time pattern is modelled under the point of view of property enforcement. The same label $< e 2 >$ is shared by three transitions each of which is constrained to fire in one of the three time intervals where $e 2$ can occur (i.e. $t (e 2) \leq t (e 1)$ , $t (e 2) \in [t (e 1), a + t (e 1)]$ , $t (e 2) \geq t (e 1) + b$ ). If $t (e 2) \in (a + t (e 1), b + t (e 1))$ transition $Tb$ delays $e 2$ until it becomes valid, i.e. $t (e 2) = t (e 1) + b$ . Would the firing of $Tb$ be permitted for any $t (e 2) \geq t (e 1) + b$ it is sufficient to use Weak-And (see Figure 1) as the synchronization rule instead of And. Also for property enforcement, the scenario where $b = \infty$ is obtained by simply removing $Tb$ .

Figure 8.

Negative time lag between two events: property enforcement.

The effect of removing $Ta$ , in both the implementations of the pattern, is that $e 2$ cannot occur until $b$ time units after $e 1$ have elapsed.

4.2.3 Time-dependent variability

This pattern allows us to deal with scenarios where the process control flow may vary during process evolution as a function of timing aspects. Let $[a, b]$ and $[c, d]$ be two possibly overlapping relative time intervals where $a, b \in ℚ^{+}$ and $c, d \in ℚ^{+} \cup {\infty}$ and $a \leq b$ and $c \leq d$ . Let $e$ be an event of interest whose occurrence time $t (e)$ is used to obtain two absolute time intervals $I 1 = [t (e) + a, t (e) + b]$ and $I 2 = [t (e) + c, t (e) + d]$ . Let $MC$ be a moment of choice where it is possible to choose among the occurrence of two events $e 1$ and $e 2$ . Let $T$ , $T 1$ and $T 2$ be the transitions whose firings are associated with events $e$ , $e 1$ and $e 2$ , respectively. The time-dependent variability pattern imposes that $T 1$ can fire if $t (e 1) \in I 1$ whilst $T 2$ can fire if $t (e 2) \in I 2$ . In the case where $I 1$ and $I 2$ overlaps, during the time interval given by $I 1 \cap I 2$ it is possible to choose independently $T 1$ or $T 2$ .

Figure 9 shows the decoration of transitions $T$ , $T 1$ and $T 2$ used to support this pattern. The moment of choice is modelled by a token in place $MC$ . In order to model urgency in the choice, i.e. $T 1$ or $T 2$ must fire as soon as possible, the Pure-And rule needs to be used in place of Master given that $P$ is always marked before $MC$ .

Figure 9.

Time-dependent variability.

5 A wine-production process model

This section illustrates the use of TSPNs and of time patterns for workflow modelling by considering an example of a simplified wine-production process (WPP) in the context of a small winery. The aim of this winery is the production of wine made from vintages of local vineyards. The WPP is made of the following phases: Destemming and crushing, Enzyme treatment, Filtration, Ageing and Bottling and labelling.

The fulfillment of the above phases requires various resources most of which are of a physical nature, e.g. holding tanks, press machines, and so on. Two types of human resources, required by the production process, are identified: the Quality checker (QC), which is responsible for controlling and warranting the quality of the phases from the arrival of raw material to the wine fermentation and for the quality assessment at the end of the ageing phase, and the Production operator (PO), which is involved in all of the operations that require the intervention of a human operator. Moreover, the WPP must satisfy some timing requirements in order to ensure a good quality of the wine. For example, the ageing phase cannot last more than 5 months.

Figure 10 shows the TSPN model of the WPP. The gray part refers to net elements which are added to manage time constraints and to enforce time-based behaviours (see Section 4.2). Places with dashed borders are references to actual places having the same names and are used to increase model readability. We assume a time unit of 1 hour for timing interval specifications and the Pure-And firing rule for transitions where not differently stated. All of the activities involving acquisition of human resources are modelled by transitions equipped with the $Weak - And$ synchronization rule. The adoption of such a rule, along with the time intervals established on incoming arcs, enforces a work break between two successive executions of activities requiring a given resource (respectively $[0, 1]$ for the quality checker and $[1, 2]$ for the production operator).

Figure 10.

The TSPN model for the wine-production workflow.

The process begins with the arrival of harvested grapes mirrored by tokens put into place GA. Tokens in places QC and PO correspond to the availability of the above-described human resources. It is assumed that work shifts of the human operators are managed outside the workflow management system. Marking of place GLS reflects the number of grape loads manageable by the winery. Two wine cells exist in the firm and each of them hosts some holding tanks used for the ageing phase. Tokens in places C1 and C2 reflect the number of available holding tanks.

Transitions TUG, TDC, and TFE correspond to the sequence of phases from grape unloading to enzyme treatment. In order to avoid must deterioration, the enzyme treatment must end no later than 20 hours since the delivery of the grapes. Such a constraint is enforced by resorting to the time lag pattern (see Section 4.2.1). Place PTC is added between transitions TUG and TFE and the time interval $[0, 20]$ is associated with its outgoing arc. A deadline miss on the enzyme treatment phase will cause a violation of transition TFE.

After the enzyme treatment the must remains for 12 hours in some small controlled fermentation tanks (places from PF1 to PF4) suitable for must conditioning. After that, the must is gathered into another larger tank (place PGM) where it continues its fermentation. When a quantity of must equal to the contents of four conditioning tanks is collected, it can be filtered (transitions TFO, TSFO and TEFO) and then transferred into a wine cell where a free holding tank is available. The filtration alone is not enough in the case the fermentation lasts more than 50 hours. In this case, it could be necessary to correct some organoleptic properties of the must. This requires the intervention of the quality checker (transitions TFC, TSFC, TEFC). The subnet PETD–TC–TEET, which behaves as a modular counter, measures the time elapsed since the begin of the fermentation phase of the oldest must at hand. In particular, (i) a token is added in PEDT each time an enzyme treatment ends, (ii) TEET fires when the first out of four of such tokens is available, (iii) TC cleans up the remaining three successive tokens. The constraint on the fermentation phase is imposed by adopting the time-dependent variability pattern (see Section 4.2.3). Two outgoing arcs are added to place PEET which respectively end on transitions TFO and TFC. These transitions are equipped with the $Pure - And$ rule that imposes the desired behaviours according to the time intervals on its incoming arcs. The transfer of the must into the wine cells is handled by the pair of transitions TMC1 and TEFC1 or by the pair TMC2 and TEFC2.

The availability of must ready for ageing is mirrored by the presence of tokens in PMA1 and PMA2. The must cannot remain in an holding tank for a time greater than 5 months otherwise it will deteriorate (transitions TWW1 and TWW2). The ageing phase starts as soon as all the holdings tanks in a wine cell are filled. This phase lasts a period ranging from 3 to 4 months (transition TSEC1 and TSEC2). It is worth nothing that time intervals on arcs outgoing places PMA1 and PMA2 are expressed in months.

When the ageing completes, holding tanks are emptied and the wine is moved for bottling (transitions TSBL1 and TEBL). The bottler machine may overheat during its operation. In such a situation, an overheat alarm is issued and the bottler, after completing the current job, is stopped for 4 hours. Transition TOVA models the asynchronous overheat alarm.

Pausing the bottler is achieved by using the negative time lag pattern (see Section 4.2.2): transition TSBL2 shares the same activity and the same preset/postset of TSBL1 and the arcs POA-TSBL1 and POA-TSBL2 ensures that each time an overheat event occurs the begin of bottling and labelling activity is postponed.

The process ends when the bottled wine is moved into a warehouse.

6 Analysis of TSPN models

Some tools were developed for supporting property checking of TSPN models. A first tool enables model checking of TSPNs through a model transformation into the terms of Uppaal timed automata.^41,42 The restriction is introduced by using natural numbers as bounds of time validity intervals. A TSPN model is turned into a collection of parallel processes corresponding to the active components of the model, namely transitions and input arcs of transitions. Clocks are associated with input arcs only. Transitions share and consult clocks of relevant input arcs. Cicirelli et al.³⁷ described a library of reusable Uppaal templates, among which one models the general timed behaviour of an input arc. The remaining templates are associated with transitions. Specifically, a distinct template was developed tailored to the requirements of a particular synchronization rule and a particular configuration (i.e. number) of the transition input arcs. The approach makes it possible to verify properties of general time-constrained models, e.g. of embedded real-time systems.³⁷ However, for large models, i.e. having a great number of transitions and of input arcs, model checking can be difficult to practice because of the very large and highly resource demanding (in memory space and time) state graph which Uppaal generates for property assessment. In these cases, a simulation tool can instead be used which although not a substitute of exhaustive verification, permits the modeller to investigate both the functional and temporal behaviour of a system.

The following summarizes a TSPN simulation tool which was achieved on top of ActorDEVS,¹⁷ i.e. an efficient agent-based framework in Java which supports PDEVS^16,18 modelling and simulation. A key point of the approach relates to conflict management of components⁴³ which is normally not allowed by standard PDEVS but is an essential feature for properly modelling and executing TSPN models. Towards this, only one imminent message at time is allowed to be processed by the simulation engine.

6.1 PDEVS concepts

A PDEVS model is specified as a collection of one or more components. There are two types of components: atomic (or behavioural) components, and coupled (or structural) components. A PDEVS atomic component is a structure $M$ defined as $M = < X, S, Y, δ_{int}, δ_{ext}, δ_{con}, λ, ta >$ where

$X$ is the set of input values;

$S$ is a set of states;

$Y$ is the set of output values;

$δ_{int} : S \to S$ is the internal transition function;

$δ_{ext} : Q \times X^{b} \to S$ is the external transition function, where $Q = {(s, e) | s \in S, 0 \leq e \leq ta (s)}$ is the set of total states $e$ is the elapsed time since last transition;

$X^{b}$ denotes the collection of bags over $X$ (in a bag some elements may occur more than once);

$δ_{con} : Q \times X^{b} \to S$ is the confluent transition function;

$λ : S \to Y^{b}$ is the output function;

$ta : S \to ℝ_{[0, \infty]}^{+}$ is the time advance function.

$S$ is normally the product of a set of control states (also called phases) and other sets built over the values of a certain number of data variables of the component.

Informal semantics of the above definitions are as follows. At any time the component is in some state $s \in S$ . The component can remain in $s$ for the time duration (dwell-time) $ta (s)$ . $ta (s)$ can be $0$ , in which case $s$ is said a transitory state, or it can be $\infty$ , in which case it is said to be in a passive state because the component can remain forever in $s$ if no external event interrupts. Provided no external event arrives, at the end of a (supposed finite) time value $ta (s)$ , the component moves to its next state $s' = δ_{int} (s)$ determined by the internal transition function $δ_{int}$ . In addition, just before making the internal transition, the component produces the output computed by the output function $λ (s)$ . During its stay in $s$ , the component can receive an external event $x$ which cancause $s$ to be exited earlier than $ta (s)$ . Let $e \leq ta (s)$ be the elapsed time since the entering time in $s$ (or, equivalently, the time of the last transition). The component then exits state $s$ moving to next state $s' = δ_{ext} (s, e, x)$ determined by the external transition function $δ_{ext}$ . As a particular case, the external event $x$ can arrive when $e = ta (s)$ . In this case two events occur simultaneously: the internal transition event and the external transition event. The next state $s'$ , in this collision situation, is determined by the confluent transition function $δ_{con}$ .

After entering state $s'$ , the new time advance value $ta (s')$ is computed and the same story continues. PDEVS emphasizes that a bag of simultaneous inputs can be received by the atomic component which in general can have a reaction to the combination of inputs which is different from the effect of sequential reactions to the separately received inputs.

In practice, an atomic component receives its inputs from typed input ports and generates outputs through typed output ports. Ports are architectural elements which favour modular system design. A component refers only to its interface ports. It has no knowledge about the identity of cooperating partners. A coupled component (subnet) is a port interconnection of existing atomic or coupled (hierarchical) components. Each component can be equipped with its own simulator. ActorDEVS, though, purposely uses a single simulation structure which serves an entire PDEVS flattened model where is minimized the number of exchanged messages.

6.2 Mapping TSPN on to PDEVS

A TSPN model is managed as a flat PDEVS coupled component. Each transition is an atomic model. Places are realized as topological passive data structures which hold marking information and know ports (messages) of connected transitions. Each time a place changes its marking, a notify message with the new place marking is sent to all of its relevant transitions. Input arcs are associated with input places of transitions. Every input arc stores, among other things, its static firing time interval and its latest enabling time instant (such an instant is infinity when the arc is not enabled).

The transformation from TSPN to PDEVS is actually accomplished manually. However, it can easily be automated by a supporting tool.

As shown in Figure 11 TSPNTransition component is a specialization of AtomicDEVS which defines common behaviour for atomic components (see Figure 13). Phases are coded as integers. Time can be dense/discrete, absolute/relative. The chosen time model is witnessed by the use of corresponding classes. A transition is characterized by its preset/postset and by its synchronization rule (a value of enumerated type Syn). The Info class captures the data part of a notify message and holds such information as a place id, the marking of this place and an indication if such marking was generated by a withdraw or deposit operation (as described later in this section). Time advance service to an enabled and temporally ready transition (i.e. current time is within its dynamic firing interval) is provided by Uniform which proposes as firing time a value uniformly distributed within the dynamic firing interval of the transition. A monitor object, i.e. an instance of a derived class of Monitor, is informed about firing/violation events of transitions, along with current time when such events occur.

Figure 11.

Class diagram of TSPN modelling in ActorDEVS.

Figure 14 recapitulates the public interface of TSPNTransition. As one can see, TSPNTransition implements the confluent function¹⁶ which gets invoked at each collision between an internal event and an external one arriving at last time of stay in a phase, so as for it to coincide with the external transition function. In this way, even at the last time point in the current phase, a transition can be disabled and then forbidden to complete its firing by a conflicting fired transition. To facilitate modelling, time is supposed not to be reset following a self-loop edge (external transition triggered by a received event) in a phase. The modeller can easily override this default behaviour through the use of a transitory phase (see for an example the CHECK phase in Figure 12).

Figure 12.

PDEVS model of a TSPN transition.

Figure 13.

Signature of basic methods of the AtomicDEVS class.

Figure 12 portrays the dynamic behaviour of a TSPN transition as modelled in PDEVS. Thick arrows denote external transitions triggered by a bag of Notify() messages. Thin arrows express internal transitions which are triggered by the elapsed time event in current phase. Before accomplishing an internal transition, the lambda() function (dashed arrows in Figure 12) is executed which generates output events to partner components. More in particular, the lambda() function of a fired transition creates a bag of Notify() messages as a consequence of changing the marking of places during its firing process. When coming back from CHECK to FIRING as a consequence of the elapsed time internal event, the lambda() function is simply void. A bag of messages is received by the external/confluent function of a TSPNTransition component, as an Iterable object. The en() predicate returns true if the transition is logically enabled (i.e. a sufficient number of tokens are available in the transition preset) and not time violated. As part of the en() service, the dynamic firing interval of the transition is determined, on the basis of the enabledness and temporal interval of the input arcs and the synchronization rule associated with the transition.

The atomic firing process of a transition t occurs in two steps: first tokens are withdrawn from the preset of t, then tokens are deposited in the postset of t. A critical point is concerned with the detection of under firing transitions which lose their enabling during the first withdrawal step of the firing process of t, but are anyway enabled at the end of the firing process. Such transitions must correctly be handled as newly enabled transitions.

In order to realize the firing process, different notify messages are employed to separately carry out a withdraw marking and a deposit marking relevant to a given transition. In Figure 12, the arrival of a bag of Notify() messages in the FIRING phase, causes a self-loop external transition in the case the transition is persistent to current firing, i.e. it is enabled both during and at the end of the firing. As soon as a transition detects that it loses its enabling in a withdrawal step, but it is enabled in the deposit phase, it switches from FIRING to the CHECK transitory phase. From CHECK the transition can re-enter the FIRING phase if the transition finds itself ultimately enabled in the deposit step, otherwise it comes to the PASSIVE phase. It should be noted that due to interleaving of concurrent actions occurring at a same time, it is possible that an under CHECK transition can lose its enabling due to the firing process of another conflicting transition.

A TSPN model is configured by first creating the place objects and the transition components. For each transition the synchronization rule and the monitor object are furnished. Places are then added to the preset/postset of transitions (see the methods in Figure 14). After that input arc connections among places and transitions are established. Model bootstrap is finally ensured by defining the initial marking for each place which in turn generates the initial message bags for transitions.

Figure 14.

Signature of public methods of the TSPNTransition class.

6.3 WPP workflow analysis

The wine production workflow was simulated using a dense time model in order to analyse some fundamental functional and temporal properties. The investigated functional properties are:

proper case termination;

avoidance of dangling tasks.

The temporal properties are:

fulfillment of the time constraint on the enzyme treatment phase;

checking the time constraint on the fermentation phase;

avoidance of wine waste during the ageing phase;

a pause of 4 hours for the bottler each time the overhead alarm is raised.

Moreover, an estimation of the time intervals needed for completing the enzyme treatment, the fermentation phase and the bottling is provided.

Proper case termination refers to the fact that for each grape load the process will eventually end either with a transfer of bottles into the warehouse or with the attainment of wasted wine. This property is satisfied if the initial marking of place GA is equal to the sum of tokens contained in BIW, PWW1, PWW2 at the simulation end.

Avoidance of dangling tasks means that each task contributes to process evolution. This property was checked by counting how many times each transition fires during the simulation. Obviously, for the modelled process, it is preferable that all transitions but TWW1 and TWW2 fire at least once.

The TSPN/DEVS model of the wine process was submitted to the simulator along with a monitor class specifically developed for counting transition firings, checking the marking of the net during its evolution, highlighting transition violations and gathering and processing transition fire times.

Several simulation experiments were carried out. Each experiment lasts until all of the model cases are completely handled (i.e. wine is produced and stored to warehouse).

Simulation results are reported in Table 1.

Table 1.

Simulation results.

Property	Result
Proper case termination	All grape loads are correctly handled
Dangling tasks	All transitions but TWW1 and TWW2 fire at least once
Time constraint on the enzyme treatment phase	Fulfilled (transition TFE is never violated)
Filtering & Correction activity	Correctly executed
Wasted wine	No (places PWW1 and PWW2 remain empty)
Bottling pause after overheat	Always fulfilled
Duration of the enzyme treatment phase	$[9.00, 17.49]$ hours
Duration of the fermentation phase	$[41.97, 57.58]$ hours
Percentage of execution of Filtering activities with respect to Filtering & Correction activities	72.32%
Bottling time interval	$[6.09, 13.79]$ hours

Measuring the time interval during which place PEET is marked does not suffice for checking fulfillment of the constraint imposed on the fermentation phase. Two other properties have to be satisfied: firings of transition TEET and TC are always interleaved, transition TEET never violates its own timing constraints. A violation of TEET constraints would imply a delay in detecting the end of the enzyme treatment.

Experimental results confirm that, from the simulation point of view, the modelled process is temporally and functionally correct.

7 Enactment of TSPN models

Enactment of TSPNs models rests on the use of PN-Engine⁸ architecture. PN-Engine is a software platform that offers functionalities for deploying a distributed process modelled as a PN, making it operational and controlling its execution. The platform is based on Jini¹⁵ and JavaSpace.⁴⁴ Jini is used as the underlying service brokering infrastructure, borrowing the advantages of dynamic registration, service lookup, notification of remote events, distributed object access and platform independence enabled by Java. JavaSpace is a tuple-space⁴⁵ permitting information sharing among distributed services of a Jini system. Information within a space, i.e. entries, can be read/written/taken by competing services thus implicitly synchronizing to one another.

The architecture of PN-Engine is depicted in Figure 15.

Figure 15.

PN-Engine architecture.

The core component, i.e. that controlling net instances’ enactment, is not a monolithic software entity, like in the WfMC reference model,^1,46 but it is made up of a set of interacting services deployed over a distributed context. This architectural aspect is fundamental for achieving the decentralized execution of the control logic.

For each task of a process model, PN-Engine automatically creates and publishes an instance of a Jini service, named TransitionService. This service embeds the logic for evaluating the preconditions that need to be satisfied in order to begin task execution and for (indirectly) notifying its completion to other interested TransitionService. There are two main usage patterns of Jini services. In a first scenario, which is the only one supported by Web Services, clients interact with the service, which runs on a remote provider, by exchanging network messages. In a second scenario, the service code is transparently downloaded and locally executed by the client. In this case, interactions between client and service code are no longer mediated by the provider and network communications are avoided. The adoption of the latter usage pattern for the TransitionService is the key to achieving decentralized process enactment.

Real task executors which participate in the process, namely worklist handlers in the case of human resources and invoked applications in the other cases, need to download the TransitionService code relevant to the activities they are in charge of. Actually, TransitionService(s) are pieces of the enactment engine automatically deployed and running on the side of worklist handlers and invoked applications. Current version of PN-Engine relies on JavaSpace as the communication infrastructure enabling TransitionService(s) to share and manage (part of) process control data for coordinating their behaviours. With processes modelled as PNs, control data correspond to net marking which is reflected by PlaceEntry objects stored in the tuple space. For each place in the net, a PlaceEntry is written into the space. Initial marking is established as part of the deployment phase. Other data, relevant to transition status and configuration (indicating, e.g., the adopted firing rules), are managed as entries into the space. In particular, for each transition, a TransitionStatus and a TransitionConf object is considered.

During net evolution, the management of the above-described entries is responsibility of TransitionService(s) that are in charge of handling all of the aspects related to transition firings.

PN-Engine supports an implicit workflow partitioning because, being based on the service metaphor, TransitionService(s) can be operating on different cross-boundary organizations or departments. In this case, the presence of a single JavaSpace service may represent a performance bottleneck. Usually, activities handled by a given organization are relative to a specific part of the business process and are strictly correlated among them while they have low or no coupling with other activities. A good deployment strategy consists in resorting to a distinct JavaSpace service for storing place entries relevant to a set of high coupled transitions, e.g. those corresponding to a sub-process handled by a given organization or department. However, places that are shared by transitions whose activities are carried out by different organizations must be replicated in the respective spaces and their accesses/modifications must occur under transaction to ensure atomicity and consistency. PN-Engine handles this issue directly by exploiting the native transaction support offered by JavaSpace.

TransitionService(s) interact with worklist handlers and invoked applications by requiring them to implement a specific Java interface named TransitionListener. When a TransitionService realizes that the corresponding activity could be executed, it notifies this event to the listener which is in charge of performing the activity. When the execution of the activity is completed the service gets informed by the listener. This approach allows the net definition and deployment to be decoupled from the actual executors that carry out process activities.

Entities implementing the TransionListener interface get bound to TransitionService(s) through the mediation of a service named ActivityManagerService.

The NetManager service is used by who plays the role of the engine manager. This service offers functionalities for feeding a process description into the system, deploying it and controlling the execution of its instances.

The node which is responsible of providing all of the above-mentioned services is called PNEngineProvider. In particular, the TransitionService(s) relevant to a given net definition are dynamically created and published once a new process definition is setup by the NetManager.

The behaviour of a TransitionService actually is capable also of coping with the case where multiple instances of it exist, i.e. when more listeners are registered to a single transition. In this scenario only the first among these services which gets bound to a listener will actively participate in the transition firing, i.e. in the withdrawal and deposit phases. The remaining instances, instead, will only be informed about the transition firing. PN-Engine is able to deal with this situation making a distinction between active and passive TransitionService (see Figure 16). Obviously the firing ends when all listeners complete the execution of their activities. The TransitionStatus object associated with a transition gets updated each time a TransitionService completes its activity thus allowing us to determine when all activities have been terminated.

Figure 16.

A transition having multiple listeners.

8 Handling timing requirements at runtime

In order to support TSPNs, PN-Engine was extended by introducing a new class, named TSPNTransitionImpl, that implements TransitionService functionalities. Such class handles all of the aspects related to the management of timing constraints. Figure 17 shows a statechart modelling the behaviour of an instance of TSPNTransitionImpl. At start-up, each transition service finds itself in the Disabled state where it waits for the arrival of events notifying a change in the marking of places in its preset. Whenever one such notification is received, the service checks the enabling status of its incoming arcs. When an arc becomes enabled, the occurrence time of the notification event is stored. As soon as all of the incoming arcs are enabled, the service computes the transition dynamic firing interval according to the transition synchronization rule. Then, it schedules a timer to expire at the absolute time corresponding to the lower bound of the dynamic firing interval and afterwards it switches to the Enabled macro state. Listeners are notified when such a state is entered.

Figure 17.

Statechart modelling the behaviour of a TSPN-TransitionService.

While in the Enabled state, the transition service listens to events related to marking changes. There are two types of such messages: WithdrawalEvt and DepositEvt. The first type is related to the token withdrawal phase of another transition which establishes an intermediate marking. The service reacts to these events by replying to the sending service with a WithdrawalAck message. This must be done in order to ensure that the intermediate marking is taken into account by all of the interested transitions before the beginning of the deposit phase of the firing transition. The DepositEvt message type, instead, concerns a deposit phase and does not require any reply message. If a WithdrawalEvt or a DepositEvt causes the disabling of one incoming arc of the transition service, the service goes back to the Disabled state and aborts what it was doing in the Enabled macro state (as described in the following). The default sub-state of Enabled is Waiting, where the service waits for the expiration of the timer set upon entering Enabled. At timer expiration, which means that the transition is now fireable, the service moves to the Firing sub-state, where it schedules another timer to occur at the absolute time corresponding to the upper bound of the dynamic firing interval and afterwards it notifies all of its listeners that the corresponding activity may be started or completed (see Section 4.1). While in Firing, the service waits for an acknowledgement message from each of its listeners. As soon as all of these acknowledgements are received, the service switches to the Locking sub-state where it locks the places of its preset. As it succeeds in acquiring the lock, the service checks whether the transition is still enabled. This control is made because the transition may have been disabled in the meanwhile but the related events have not yet been received. If the transition is found to be still enabled, the lock ownership ensures that the withdrawal phase can safely begin, so the service moves to the Withdrawal state. In contrast, the lock is released and the service waits for the notifications not yet received. As said before, if the Enabled state is left because the transition has been disabled, some clean-up has to be done: listeners are notified by sending them an activity-revocation message, set timers are cancelled. While in the Enabled state, the timer expiration corresponding to the upper bound of the dynamic firing interval causes the Error state to be entered and clean-up operations to be done as above. Upon entering the Withdrawal state, tokens are removed from the transition preset, WithdrawalEvt messages are transmitted to relevant transition services and Commit messages are sent to transition listeners. On gathering all of the WithdrawalAck messages, the transition service switches to the Deposit state where it begins the deposit phase by requiring a lock on the postset places. After the lock is acquired, the marking of these places is first updated, then all of the owned locks are released, the relevant DepositEvt messages are sent and, finally, the Disabled state or the Enabled state is entered depending on the enabling status of the transition after its own firing. It is assumed that the time needed for solving conflicts among transitions and the time related to network delay and to the use of JavaSpace are negligible with respect to the time needed for executing the real coordinated activities.

8.1 Workflow deployment and execution

The proposed WPP model was executed on three Win platforms Pentium IV 3.4 GHz interconnected by a 1 GB Ethernet switch. One computing node was used as a service provider for the PN-Engine services, Jini and JavaSpace. Remaining nodes were used for hosting TransitionListener(s) which, in a real scenario, would be deployed accordingly to the actual placement of the resources within the winery context. Two Transition Listener(s) were considered respectively for the QC and the PO. Each listener looks up for the TransitionService(s) relevant to the transitions it has to listen to, then it registers upon them. This phase is carried out by using the ActivityManagerService (see Figure 18(a)) which assists with lookup and registration steps. A listener bound to a human resource simply acts as a notifier.

Figure 18.

Graphical user interfaces.

When an enabling event is delivered, the relevant activity is highlighted in the operator’s GUI (see Figure 18(b)). A subsequent firing event causes the flashing of the field GUI associated with the activity. When this occurs, a start-event or completion-event requires to be managed and the human operator has to press the corresponding button in order to signal her/his readiness to accomplish the assignment. Owing to the race firing semantics, it may happen that a starting-event may be revoked due to a pre-emption. As a consequence, the human operator must wait for the arrival of a final notification confirming that she/he can put into effect the activity (commit message) or signaling that the operation has been revoked (abort message).

9 Conclusions

In this paper we have proposed an approach to modelling, analysis and execution of workflows with timing constraints using TSPNs. TSPNs have the capability of supporting various timing requirements in workflow process specification. Moreover, satisfying certain time constraints rather than others can be achieved by simply changing synchronization firing rules of modelled transitions. Property analysis can be based on model checking or on a DEVS centred simulation tool. Distributed enactment depends on PN-Engine,⁸ a service-based enactment engine characterized by the absence of a centralized control entity.

On-going work is geared at:

identifying other time patterns^38,39 where the various TSPN firing-rules can be best applied;

experimenting with race-with-memory semantics in order to specifically support patterns relevant to service-level agreement;

investigating techniques for managing dynamic reconfiguration of workflows⁸ in the presence of time constraints;

implementing a data-exchange mechanism among TransitionListener(s), e.g. by attaching data to tokens in the space;

investigating error recovery policies and fault-tolerance issues during workflow execution;⁴⁷

experimenting with PN-Engine for the orchestration of composed services.

Footnotes

Funding

This research received no specific grant from any funding agency in the public, commercial, or not-for-profit sectors.

Author biographies

Franco Cicirelli, PhD, is a computer science post-doctoral fellow at University of Calabria (Unical), DEIS - Department of Electronics Informatics and Systems Science, performing research on agent and service paradigms for the development of distributed systems, parallel simulation, Petri nets, distributed measurement systems. He is a member of the ACM.

Angelo Furfaro, PhD, is a computer science assistant professor at Unical, DEIS, teaching software engineering. His research interests include multi-agent systems, service-oriented computing, Petri nets, parallel simulation, verification of time-dependent systems, distributed measurement systems. He is a member of the ACM.

Libero Nigro is a professor of computer science at Unical, DEIS, where he teaches object-oriented programming and real-time systems courses. He is the responsible for the Software Engineering Laboratory (). His current research interests include: software engineering of time-dependent and distributed systems, real-time systems, Petri nets, modelling and parallel simulation of complex systems, multi-agent systems, service-oriented computing. He is a member of the ACM and the IEEE.

References

Hollingsworth

. The Workflow Reference Model. Technical Report TC00-1003, Workflow Management Coalition, 1995.

van der Aalst

WMP

Barros

ter Hofstede

Kiepuszewski

. Advanced workflow patterns. In Proceedings of 7th International Conference on Cooperative Information Systems, 2000, pp. 18–29.

van der Aalst

WMP

. The application of Petri nets to workflow management. Journal of Circuits, Systems and Computers 1998; 8: 21–66.

Diaz

Sénac

. Time stream Petri nets: A model for timed multimedia information. In Proceedings of the 15th International Conference on Application and Theory of Petri Nets, London, UK, 1994, pp. 219–238.

Sénac

Diaz

Leger

de Saqui-Sannes

. Modeling logical and temporal synchronization in hypermedia systems. IEEE Journal on Selected Areas in Communications 1996; 14: 84–103.

Merlin

Farber

. Recoverability of communication protocols–implications of a theoretical study. IEEE Transactions on Communications 1976; 24: 1036–1043.

Boyer

Diaz

. Non equivalence between time Petri nets and time stream Petri nets. In Proceedings of the 8th International Workshop on Petri Nets and Performance Models, 1999, pp. 198–207.

Cicirelli

Furfaro

Nigro

. A service-based architecture for dynamically reconfigurable workflows. Journal of Systems and Software 2010; 83: 1148–1164.

Papazoglou

Georgakopoulos

. Service-oriented computing, introduction. Communications of the ACM 2003; 46(10): 24–28.

10.

Bennett

Layzell

Budgen

Brereton

Macaulay

Munro

. Service-based software: the future for flexible software. In Proceedings of 7th Asia-Pacific Software Engineering Conference, 2000, pp. 214–221.

11.

Perrey

Lycett

. Service-oriented architecture. In Proceedings of the Symposium on Applications and the Internet Workshop (SAINT’03), 2003, pp. 116–119.

12.

Cicirelli

Nigro

. A General Brokering Architecture Layer and its Application to Video on-Demand over the Internet. Informatica - An International Journal of Computing and Informatics 2007; 31: 29–39.

13.

Verbeek

HMW

Basten

van der Aals

WMP

. Diagnosing workflow processes using Woflan. The Computer Journal 2001; 44: 246–279.

14.

Guan

Hernandez

Bangalore

Gray

Skjellum

Velusamy

. Grid-flow: a grid-enabled scientific workflow system with a Petri-net-based interface. Concurrency and Computation: Practice and Experience 2006; 18: 1115–1140.

15.

Edwards

. Core Jini, 2nd edition. Englewood Cliffs, NJ: Prentice Hall, 2001.

16.

Zeigler

Praehofer

Kim

. Theory of Modeling and Simulation. New York: Academic Press, 2000.

17.

Cicirelli

Furfaro

Nigro

. A DEVS M&S framework based on Java and actors. In Proceedings of 2nd European Modeling and Simulation Symposium (EMSS’06), Barcelona, Spain, 4–6 October 2006, pp. 337–342.

18.

Cicirelli

Furfaro

Nigro

. Actor-based simulation of PDEVS systems over HLA. In Proceedings of 41st Annual Simulation Symposium (ANSS’08), Ottawa, Canada, 14–16 April 2008, pp. 229–236.

19.

Jansen-vullers

Netjes

. Business process simulation–a tool survey. In Workshop and Tutorial on Practical Use of Coloured Petri Nets and the CPN, Aarhus, Denmark, October 2006.

20.

Rozinat

Wynn

van der Aalst

WMP

ter Hofstede

AHM

Fidge

. Workflow simulation for operational decision support. Data Knowledge Engineering 2009; 68: 834–850.

21.

Nakatumba

Rozinat

Russell

. Business process simulation: How to get it right. In International Handbook on Business Process Management. Berlin: Springer-Verlag, 2009.

22.

Verbeek

HMW

van Hattem

Reijers

de Munk

. Protos 7.0: Simulation made accessible. In Proceedings of International Conference on Application and Theory of Petri Nets (ICATPN 2005) (Lecture Notes in Computer Science, vol. 3536). Berlin: Springer-Verlag, 2004, pp. 465–474.

23.

Jensen

Kristensen

Wells

. Coloured Petri nets and CPN tools for modelling and validation of concurrent systems. International Journal on Software Tools for Technology Transfer 2007; 9: 213–254.

24.

Ling

Schmidt

. Time Petri nets for workflow modelling and analysis. In Proceedings IEEE International Conference on Systems, Man, and Cybernetics, vol. 4, 2000, pp. 3039–3044.

25.

Tsai

JJP

Jennhwa Yang

Chang

Y-H

. Timing constraint Petri nets and their application to schedulability analysis of real-time system specifications. IEEE Transactions on Software Engineering 1995; 21: 32–49.

26.

Fan

Zhou

. Timing constraint workflow nets for workflow analysis. IEEE Transactions on Systems, Man and Cybernetics, Part A 2003; 33: 179–193.

27.

Wang

Zeng

. Modeling and analysis for workflow constrained by resources and nondetermined time: An approach based on Petri nets. IEEE Transactions on Systems, Man and Cybernetics, Part A 2008; 38: 802–817.

28.

Fan

. A time management method in workflow management system. In Proceedings Workshops at the Grid and Pervasive Computing Conference GPC ‘09, 2009, pp. 3–10.

29.

Yang

. Dynamic checking of temporal constraints for concurrent workflows. Electronic Commerce Research and Applications 2005; 4: 124–142.

30.

Eder

Panagos

. Managing time in workflow systems. Workflow Handbook 2001. Future Strategies Inc., 2001, pp. 109–132.

31.

Hong

Lee

Kim

. DEVS framework instrumented with database for web-based workflow modeling simulation. In Proceedings of the International Conference on Web-Based Modeling and Simulation, San Francisco, CA, 17–20 January 1999, pp. 113–118.

32.

Zacharewicz

Frydman

Giambiasi

. G-DEVS/HLA environment for distributed simulations of workflows. SIMULATION 2008; 84: 197–213.

33.

Giambiasi

Escude

Ghosh

. G-DEVS: A generalized discrete event specification for accurate modeling of dynamic systems. Transactions of the SCS International 2000; 17: 120–134.

34.

Kuhl

Dahmann

Weatherly

. Creating Computer Simulation Systems: An Introduction to the High Level Architecture. Upper Saddle River, NJ: Prentice-Hall, 2000.

35.

Choi

Lee

Kang

. DEVS modeling of run-time workflow simulation and its application. In Proceedings of 22nd European Conference on Modelling and Simulation (ECMS 2008), Cyprus, 3–6 June 2008, pp. 31–36.

36.

Lee

Shin

Choi

. Mediator approach to direct workflow simulation. Simulation Modelling Practice and Theory 2010; 18: 650–662.

37.

Cicirelli

Furfaro

Nigro

. Modelling and analysing real time system specifications using time stream Petri nets. In Proceedings of 30th IFAC Workshop on Real-Time Programming and 4th International Workshop on Real-Time Software (WRTP/RTS’09), Mragowo, Poland, 12–14 October 2009.

38.

Lanz

Weber

Reichert

. Workflow time patterns for process-aware information systems. In Proceedings of 11th International Workshop BPMDS and 15th International Conference EMMSAD at CAiSE 2010, 7–8 June 2010, pp. 95–107.

39.

Niculae

. Time Patterns in Workflow Management Systems. Technical report, BPMcenter.org, 2011.

40.

Combi

Gozzi

Juárez

Oliboni

Pozzi

. Conceptual modeling of temporal clinical workflows. In 14th International Symposium on Temporal Representation and Reasoning (TIME 2007), 2007, pp. 70–81.

41.

Behrmann

David

Larsen

. A tutorial on Uppaal. In Formal Methods for the Design of Real-time Systems (Lecture Notes in Computer Science, vol. 3185). Berlin: Springer-Verlag, 2004, pp. 200–236.

42.

Uppaal on-line, http://www.uppaal.com, September 2010.

43.

Cicirelli

Furfaro

Nigro

. Conflict management in PDEVS: An experience in modelling and simulation of time Petri nets. In Proceedings of Summer Computer Simulation Conference (SCSC’07), San Diego, CA, 15–18 July 2007, pp. 349–356.

44.

Flenner

. Jini and JavaSpaces Application Development. SAMS, 2001.

45.

Carriero

Gelernter

. How to write parallel programs. Cambridge, MA: MIT Press, 1990.

46.

Workflow Management Coalition. Workflow reference model, http://www.wfmc.org/reference-model.html, accessed November 2009.

47.

Adams

ter Hofstede

AHM

van der Aalst

WMP

Edmond

. Dynamic, extensible and context-aware exception handling for workflow. In Proceedings of the 15th International Conference on Cooperative Information Systems (CoopIS 2007), Vilamoura, Algarve, Portugal, November 2007, pp. 95–112.