Dealing with synchronization in time constrained workflow is becoming a challenging issue. In this paper, we present a modelling approach based on Petri nets formalism for timed workflow systems with complex synchronization among tasks of different privileges (Master/Slave). To this aim, we consider the concept of rendezvous already introduced in the RTPN (Time Petri Nets with rendezvous), to define a subclass of RTPNs called Time Workflow-nets with Rendezvous (RTWF-nets). We discuss how this model can cover a large range of timed synchronization patterns in a very smart and compact framework.
In the late of the 70’s, the research on workflow systems has started and a lot of approaches and powerful tools have been proposed and developed. Generally, workflows represent processes describing how and when their elementary tasks should be accomplished, thus describing the control flow Copyright c by the paper’s authors. Copying permitted for private and academic purposes. of the workflow system. This may include different mechanisms ( e.g., sequence, choice, parallelism and synchronizations), usually called workflow patterns [Aal05]. For instance, synchronization in workflow system can be seen as a meeting point during the process where a set of tasks has to wait for others according to a given scheme (e.g the AND-join synchronizer pattern). Nowadays, the real challenge in workflow systems is to deal with situations where a variable number of tasks is processed under different synchronization and time constraints patterns. Indeed, adapting, replanning, and synchronizing workflows in response to an unexpected progress, delays, or technical conditions are necessary to maintain the safety of the systems. Furthermore, such requirements are becoming critical aspects in many domains as for example healthcare workflows [Car09]. For example, in transplantation surgery activity, we require the concurrent presence of the organ to be implanted, blood for the patient and the patient, that must arrive within the same hour at the hospital to avoid their functional degradation.
In this paper, we propose the use of RTPN (Time Petri Nets with Rendezvous) [Ham17], for the modelling and the analysis of complex workflow systems that include synchronization and time constraints among tasks. The RT P N introduces the paradigm of rendezvous to define various synchronization schemes under different time constraint orchestrations. With its expressiveness power, RTPN provides a compact framework to represent complex workflow systems in elegant way, that could hardly be handled by other existing models. After presenting and discussing the workflow patterns provided by RTPN, we define a subclass of RTPN, called RTWFN (Time Workflownets with Rendezvous ), which is dedicated for the specification of workflow systems.
The remaining of this paper is organized as follows: Section 2 discusses the related works. In section 3, we present our workflow model with timed rendezvous patterns. Section 4 presents the RTPN and RTWFN models before presenting the modelling approach. In section 5, case-study examples are presented. Finally, conclusions and comments on future work are given. 2
In this section, we review the key works defined in the literature that address workflow systems modelling and analysis.
Basic Petri nets have been used for the representation, the validation and the verification of business procedures in [Aal05]. In [Aal98], the authors introduce the WorkFlow net (WF-net) to specify the processing of a workflow. Afterwards, the WFnet has been extended to deal with data, time and other aspects. A various extensions are proposed: (i) the extension with time [Ada98]; (ii) the extension with color to model data [Rus09] ; (iii) the extension with hierarchy to structure large models [Aal08]; (iv) and finally combining some of the previous features [Fra17].
Different other models have been proposed in the literature : In [Wan08], the authors introduce the R/NT-WF Net to model workflows constrained by resources and a non-determined time. A procedure is given to compute the earliest and the latest times to start each activity. In [Bou08], a new formalism called the Time Recursive ECATNets (T-RECATNets) is proposed for modelling and analysing time constrained reconfigurable workflows. In [Ber12] componentbased timed-arc Petri Nets (CTAPN) are defined to model collaborative healthcare workflows. The authors in [Cic13] consider the TSPN model for modelling and enactment of complex workflows. The authors in [Yeh05], introduce the WFCS-nets (workflow with critical sections nets), to deal with synchronization and time constraints among activities while considering critical sections. In [Aal13] [Sai17], patterns are adapted to cope with interorganisational workflows (IOWF). An approach describing how the qualitative and quantitative analysis of the framework can be performed by using TCTL model checking is presented in [Bou14].
-b) Others Models : Other formalisms have been also considered to specify workflow systems, as the use of computational tree logic (CT L) in [Rus91], the event algebra in [Els09], multi-agent theory in [Alf16], UML activity diagrams in [Arn16], and State Charts [Wen12]. However, all the previous works do not consider time constraints. To deal with the latter, the authors in [Eder15] introduce the Timed Workflow Graph (TWG) defining a graph which is composed of a set of nodes (activities) and edges (control flow). Each activity is characterized by its duration and earliest and latest ending time. However, no delay between activities is defined, thus, leading to incorrect time evaluation. 3
Workflow modelling and analysis are very important aspects and become more complex when considering, in addition, synchronization and time constraints. We present in this section the essence of our approach by describing the different paradigms used in our modelling framework. 3.1
In our model, we consider a set of elementary work units called tasks, that collectively achieve the whole process. An atomic task is an activity that cannot be divided into sub-processes. Tasks can have different privileges (Master or Slave) and are associated with a time interval defining the earliest and the latest times within which they should occur. A Rendezvous is a time point during the workflow process where a set of tasks has to wait for others in order to perform a synchronization. A rendezvous, noted R, is the tuple (Tm, Ts, (Loc−, Loc+), (α−, α+, δ−, δ+)), such that: - Tm denotes the non empty set of master tasks involved in the scheme; Ts is the set of slave tasks. In the sequel, we note Tr = Ts ∪ Tm, and we assume that each task t is characterized by its own time constraints, given in the form of an interval [x(t), y(t)]. - (Loc−, Loc+) denotes the localities on which refer the delay parameters. Loc− is called the early time locality and Loc+ is the latest time locality. - The delay parameters (α−, α+, δ−, δ+) are positive rational numbers from Q+ ∪ {+∞} that specify the tolerable drifts between the synchronizing tasks in the rendezvous. The parameters α−and δ− are associated with the early time locality, while α+and δ+ are with the latest time locality. Page 77
According to the type of synchronization pattern, the early time locality Loc− can refer to one of the two following dates (see Fig.1): Loc− := M AX{x(t)}, namely at the earliest time of the ∀t∈Tm last master task that started its execution; or Loc− := M AX {x(t)}, namely at the earliest time ∀t∈Tr of the last task that started its execution.
Likewise, Loc+ can take two different dates: Loc+ := M IN {y(t)}, namely at the latest time ∀t∈Tm of the first master task that ends its execution; or Loc+ := M IN {y(t)}, namely at the latest time of ∀t∈Tr the first task that ends its execution.
For the sake of simplification, in the sequel the expression of the value of both localities will refer only to the set of transitions considered in the operators M IN or M AX , namely Tm or Tr rather than considering the whole expression. However, whatever the synchronization pattern in the Rendezvous we consider, it should be noticed that at least one of the two localities Loc− and Loc+ of the rendezvous must refer to the set of master tasks Tm. This is because the rendezvous must be driven by master tasks. 3.2
Let R = (Tm, Ts, (Loc−, Loc+), (α−, α+, δ−, δ+)) be a rendezvous. As illustrated in Fig.1, the earliest time to hold the rendezvous must occur: - no earlier than α− time units before the occurrence of the locality Loc−; and - no later than δ− time units after the occurrence of the locality Loc−.
The latest time to hold the rendezvous must occur: - no earlier than α+ time units before the occurrence of the locality Loc+; and - no later than δ+ time units after the occurrence of the locality Loc+;
It is noteworthy that the parameters α− and δ− are associated with the locality Loc−, while α+ and δ+ are associated with the locality Loc+. Let be M AX : the maximum value between the earliest time of the last master task that started its execution and the latest time of the first master task that ends its execution. Likewise, M IN : the smallest value between the earliest time of the last master task that started its execution and the latest time of the first master task that ended its execution.
According to the value of the delay parameters, the two localities, we define and discuss in the sequel a panel of useful synchronization patterns that are derived from the concept of rendezvous: a-Cobegin rendezvous: This regroups all the patterns such that the earliest time of the rendezvous is determined by the earliest start of one task among masters tasks or all the tasks, leading to different variants, as for example:
-1) if we have (α− = 0) and (δ− = 0 or ∞), then, the earliest time of the synchronization occurs at the earliest time of the last master task that started its execution. We call this pattern the cobegin master Synchronized rendezvous (see Fig 2.a)). Example: let’s consider the example of the transplantation surgery activity: if the organ arrives between [1, 3], the blood between [2, 3] and the patient between [2, 5], the earliest time the rendezvous occurs is 2.
-2) If we have(α− = ∞) and (δ− = 0 ), then the earliest time of the synchronization occurs at M IN (see Fig 2.b). This is called a strict cobegin rendezvous. Assuming the same example, if the organ arrives between [1, 2], the blood at [3, 3] and the patient between [2, 5]. The earliest time the rendezvous occurs is the minimum between (3, 2) = 2.
-3) If we have(α− = ∞) and (δ− = ∞ ), then the earliest time of the synchronization occurs at: - if Loc− = Tm : The earliest time of the first master task that stated its execution. We call this pattern, cobegin master-relaxed rendezvous (see Fig 4.g)). - if Loc− = Ts : The earliest time of the first task that stated its execution. We call this rendezvous cobegin-relaxed rendezvous
b-Coend related rendezvous: This regroups all the patterns such that the latest time of the rendezvous is determined by the latest ending time Page 78 of the fist task (among masters tasks or all the tasks); this leads to different variants, for instance: -1) If we have (δ+ = 0) and (α+ = 0 or ∞), then the latest time of the synchronization occurs at the latest time of the first master task that ends its execution. We call this pattern the coend master Synchronized rendezvous (see Fig 3.c). Example: Let’s consider the previous example, if the organ arrives between [1, 3], the blood between [2, 3] and the patient between [2, 5], the latest time of the rendezvous is 3.
-2) If we have(δ+ = ∞) and (α+ = 0 or ∞), then the latest time of the synchronization occurs at M AX (see Fig 3.d). This is called a hard Coend rendezvous. Example: if the organ arrives between [1, 2], the blood at [3, 3] and the patient between [2, 5], the latest time the rendezvous occurs is the maximum between (3, 2) = 3.
-3) If we have (δ+ = ∞) and (α+ = ∞), then the latest time of the synchronization occurs at: - (if Loc+ = Tm): The latest time of the last master task that ends its execution. We call this pattern the coend master-relaxed rendezvous. By taking the previous example, the synchronisation occurs at 5. - (if Loc+ = Ts): The latest time of the last task that ends its execution. We call this pattern the coend relaxed rendezvous.
By combining the previous patterns, or by considering specific conditions, we can define new subpatterns, as for example: 1. A Fully master synchronized rendezvous is both a cobegin master Synchronized and a coend master Synchronized rendezvous. (see Fig 5.e,f) 2. A Relaxed rendezvous is both a cobegin relaxed and a coend relaxed rendezvous (see Fig 4.g,h). 3. A Critical rendezvous, is a rendezvous such that Loc+ = Loc− . In other terms the earliest and the latest time of the occurrence of the rendezvous are the same. The rendezvous has to be executed in urgency and cannot be delayed once its offered. 3.3
A large range of synchronization schemes defined in the literature are covered by our model, and many others. For example for the basic rules of the T SP N model [Cic13], the Synchronized rendezvous coincides with either the And or the P ur − And rules (when considering a different variants of disjointed interval relations). This expresses that all tasks are present during the rendezvous. The Relaxed rendezvous is referred to the Or rule of T SP N , for instance. The Cobegin Synchronized rendezvous covers: the And, P ur − And, W eak − And, And − M aster, rules, whereas, the (Coend Synchronized) rendezvous covers: the And, P ur − And, Strong − Or, StrongM aster rules. The Cobegin Relaxed rendezvous covers the : Or, Strong − Or, Or − M aster, rules, whereas, Page 79 the Coend Relaxed covers the W eak − And, Or, W eak − M aster,rules. Our model covers also, the wait constraints of the parallel pattern [Car09]. However, our model is more expressive as it considers time constraints in form of intervals (not instants) and at different levels (not only between tasks), while assuming different privileges. For the best of our knowledge, no related works have addressed the timed synchronization between workflow tasks of different privileges. Synchronization and time constraints are generally studied separately. 4
RenIn this section, we first present the syntax and the semantics of the RTPN model as introduced in [Ham17], then we introduce a subclass of RTPN, called Workflow nets with timed rendezvous RTWFN. This model is dedicated to specify workflow systems. Finally, we present a RTWFN based modelling approach for workflow systems.
RT P N A classical Petri net (PN) is a directed bipartite graph with two types of nodes, called places and transitions. The nodes are connected via directed arcs and connections between two nodes of the same type are not allowed. Places are represented by circles and transitions by rectangles. We assume that the reader is familiar with Petri nets theory. In the RTPN model, time intervals are associated with each transition thus defining a Time Petri net (TPN). The TPN is then extended with a set of synchronization rules defined by the concept of rendezvous introduced previously. We recall hereafter the syntax and the semantics of the RT P N model. Formally, the syntax of the RT P N model is defined as follows:
Definition An RT P N is given by the tuple (P, T , B, F, M0, Is, RDVs) where: P and T are respectively two non empty disjoint sets of places and transitions; ; B and F are respectively the backward and the forward incidence functions B : P × T −→ N = {0, 1, 2, ..}; F : P × T −→ N ; M0 is the initial marking function that associates with each place a number of tokens M0 : P −→ N ; Is is the delay interval mapping function; Is : T −→ Q+ × Q+ ∪ {∞} , where Q+ is a set of null or positive rational values. We write Is(t) = [x0(t), y0(t)]. This gives the static time interval within which the transition t can fire, such that 0 ≤ x0(t) ≤ y0(t); RDVs denotes a finite set of synchronous Rendezvous . A Rendezvous R of RDVs is a synchronisation scheme that has the form (Tm, Ts, (Loc−, Loc+), (α−, α+, δ−, δ+)), where Tm and Ts are subsets of transitions. Tm ∩ Ts = ∅ and we note Tr = Tm ∪ Ts.Tm is a non empty and finite set of master transitions, and Ts the finite set of slave transitions. (Loc−, Loc+) are the localities considered in the rendezvous, values of which are in {(Tm, Tm), (Tm, Tr), (Tr, Tm)}. Finally, α−, α+, δ+ and δ− are the delay parameters that take their values in Q+ ∪ {+∞}.
In the RT P N model, a transition can be involved in more that one rendezvous. This denotes the case where an event or a process ( modelled by the transition) is subject to different alternative synchronization schemes. The selection of the rendezvous to execute is handled in non deterministic manner. However, a priority function on the set of rendezvous can be introduced as an additional parameter to solve the non determinism. In other respects, a transition that is not involved in any rendezvous of the RT P N is to progress in an asynchronous manner since it is not compelled by any synchronisation scheme. The RT P N model evolves by firing a rendezvous at each step. This implies the firing of all its transitions providing that some conditions are satisfied. Firing a rendezvous relies on the marking and on the corresponding synchronization pattern which entails to meet the dynamic time constraints of the model. Different semantics can be considered : a monoserver semantics, namely for any marking only one instance of a transition and by extension a rendezvous can be enabled (see the paper [Ham17] for more details); or a multi-server one which considers that a transition and hence a rendezvous can be enabled more than once for a given marking (refer to the papers [Abd15] [Bouch13]). 4.2
We introduce, in the following, the RTWFN model which is a particular case of a RTPN.
Definition A RTWFN noted RTw is a tuple (RT , pb, pe), such that: -RT = (P, T , B, F, M0, Is, RDVs is a Time Petri Net with rendezvous. -pb is a special place of P called the beginning place Page 80 of the workflow net, and we have: •pb = ∅ and M0(pb) 6= 0; -pe is a special place of P called the ending place of the workflow, and we have: pe• = ∅ and M0(pe) = 0 ; where: •x denotes the set of input transitions connected to the place x while x•: gives the set of output transitions connected to x .
The place pb denotes the source of the net while the place pe the sink of the net. The RTWFN should verify that there exists a run from the initial marking including the place pb to a final marking including the place pe ; we say that the net is strongly connected. 4.3
The RTWFN model of the whole workflow constrained by synchronization and time delays can be obtained by the following approach: -1)First we create the places pe and pb.
-2) A single task: Each elementary unit:(task ) is mapped into a transition t ∈ T and an input place p ∈ P . For time constraints a time interval is associated with each transition’s task I(t) = [x(t), y(t)], thus, defining the earliest and the latest time delay of the task. If no time constraint are imposed, this means that I(t) = [0, ∞), contrarily, with I(t) = [0, 0] the task cannot be delayed and must occur as soon as the input place is marked (See Fig.6.(x)). If the task is the first in the process then its input place is pb. If it is the last in the workflow then its output place is pe.
-3) Sequence: In the example of Fig 6.a, tasks t1 and t2 are executed sequentially, representing precedence constraints of task execution in the workflow;
-4) Choice: In Fig 6.b, t1 and t2 are in conflict and can never occur both;
-5) Concurrency: In Fig 6.c, tasks are in concurrency; they occur in parallel and are not in conflict. Their execution can be governed by synchronization patterns that are expressed in the form of rendezvous. 4.4
In this section, we present two case-studies to highlight how the RTWFN model is suitable to model worflow systems with complex synchronization patterns. (x) Let’s consider the example of ”An online vendor workflow ”, already presented in [Bet02]. The figure 7 depicts a portion of the whole RT W F N specification. In the problem description, different types of synchronization and time constraints have to be considered to ensure that all the products are delivered to the customer in a due time to better manage the warehouse resources. A and B correspond to the shipments that have to be made by two suppliers (of the same privilege). The task A, resp B is denoted by the transitions Ab and Ae(Beginning and and end of A) resp. the transitions Bb and Be(Beginning and the end of B). Both A and B must occur respectively between [3, 7] and [1, 3] after the the ending of the operation OP that lasts between [1, 10]. The tasks A and B have a duration between [1, 5]. Finally, the beginning of the local delivery task LD (denoted by the transition LDb), has to occur as soon as A and B complete. The final delivery task must begin after that all products are made available and none of the products must wait more than 2 time units at the warehouse. To express the previous synchronization requirements we introduce the following set of rendezvous RDV = {R1, R2} such that: R1 = ({tAb, tBb}, ∅, ({tAb, tBb}, {tAb, tBb}), (0, 0, 0, 0)) which means no temporal delay is considered at the beginning of A and B and represents a fully synchronized rendezvous as well as a Critical rendezvous. R1 can fire within: " ∀t∈{MtAAbX,tBb}{x(t)}, ∀t∈{MtAIbN,tBb} R2 = ({tAe, tBe}, ∅, ({tAe, tBe}, {tAe, tBe}), (0, 0, 2, 2)) Means that the earliest time to start delivery task can be advanced not more than 2 times units, and can be delayed to no more than 2 time units. Furthermore, R2 can fire within " # {y(t)} − 2 =[1,5-2] Page 81 =[1,3]. dezvous.
This pattern denotes a restricted renWe consider here the example of ST-segment Elevation Myocardial Infarction (STEMI), published by the American College of Cardiology/American Heart Association in 2004 [Car09]. The associated RTWFN is depicted in Fig. 8. The problem is as follows: when a patient comes to the Emergency Department (E.D.) (task T1), he can wait between approximatively [2, 4] minutes before being handled. Once he is admitted, the patient is examined first (task T2), which takes between [5, 20] minutes. If the diagnosis is a (STEMI) occurrence ( transition C1), then a well-know set of therapy and diagnosis tasks has to be performed. Otherwise, ( transition C2) a further patient evaluation has to be done (choice). Since the guideline considers only (STEMI) patients, we have decided to close the flow issued from C2 after the task T3. The flow from C1 is composed by three parallel sub-flows. The lowest from place B) refers to the main therapeutic action in presence of a myocardial infarction: reperfusion is obtained through a fibrinolytic therapy (transition T4 which is a slave task). The flow from place C refers to the complementary therapeutic action consisting of the assumption of beta blocker drugs (task T5) (master task). The uppermost flow (from place A) contains the possible activities related to therapies for ischemic discomfort. If the presence of ischemic discomfort (C2) is confirmed (transition I2), a nitroglycerin therapy is provided (task T6)(a second slave task). Otherwise (I1 no supplementary treatment is provided. After all these therapeutic actions, the workflow ends. As discussed in [Car09], we want to express the fact that the synchronization of the reperfusion (T4) and the oral therapy (T5) neither can start more than 2 minutes before nor can start more than 1 minute after the end of the oral therapy (T5). To this aim, We consider the following rendezvous in our model: R1 = ({T 5}, {T 4}, ({T 4, T 5}, {T 5}), (0, 0, 2, 1)) without a nitroglycerin therapy: T6; and R1 can fire within: ∀t∈M{TA5X,T4}{x(t)}, ∀tM∈{ITN5}{y(t) − 2} =[4,6-2]=[4,4]. This denotes a critical cobegin rendezvous ), or: = [4,6+1]=[4,7] ∀t∈M{TA5X,T4}{x(t)}, ∀tM∈{ITN5}{y(t) + 1} which denotes a cobegin synchronized rendezvous. 5
In this paper, we have presented a modelling approach for timed workflow systems with complex synchronizations. The approach is based on Petri net formalism, by a subclass of Time Petri Nets with rendezvous (RTPN), called time workflow nets with rendezvous RTWFN. The latter provides a large panel of concise synchronization patterns that can deal with any complex synchronization scheme in timed workflow systems. Further work will lead us to investigate a methodology for the analysis of the quantitative and the qualitative properties of the RTWFN model. Page 82 [Aal08] J.J Baek and L.K. Bisgaard and W.L.M.P Van der Aalst : From task descriptions via colored Petri nets towards an implementation of a new electronic patient record workflow system.
STTT 10(1): 15-28 2008. [Cic13] F. Cicirelli, A. Furfaro, L. Nigro: Using time stream Petri nets for workflow modelling analysis and enactment. Simulation 89(1): 6886, 2013.