Business processes typically have to observe temporal requirements or constraints such as the duration of activities, deadlines for the process execution and admissible laps between events (in particular the start and end of activities) [1,2,3,4,5]. Recently, significant progress was made to check a process model for the existence of conflicts between temporal constraints, i.e., mutually exclusive satisfaction of temporal constraints. To this end, several notions of temporal correctness, such as consistency, controllability, conditional controllability and dynamic controllability, with different degrees of expressiveness, strictness and problem complexity have been developed (see, e.g., [6,7,8,9]).
The most elaborated notion for the correctness of temporally constrained business processes is dynamic controllability (DC) [10,6,9]. Dynamic controllability ensures that the temporal constraints are free from any potential conflict under any foreseeable circumstance [11]. Dynamic controllability is the most relaxed criterion to guarantee that it is possible to steer the execution of a business process in such a way that no temporal constraint violations occur at run-time despite uncertainties. Uncertainties arise when the process controller cannot know the precise duration of some activities (e.g., of invoked services) beforehand, and because of conditional execution paths that cannot be influenced.
Sound and complete algorithms are now available to effectively check whether specifications of temporally constrained business processes are dynamically controllable. The major approaches to check the dynamic controllability of processes are based on different kinds of temporal constraint networks [12], in particular Simple Temporal Network with Uncertainty (STNU) and Conditional Simple Temporal Network with Uncertainty (CSTNU). Business process models with temporal constraints can be transformed into an equivalent STNU or CSTNU by applying a set of transformation rules [13]. So the dynamic controllability of a business process is delegated to checking whether its corresponding STNU or CSTNU is dynamically controllable. At this time, effective techniques for checking dynamic controllability of STNUs, such as the MMV- [14] and the RUL-system [15,10] (respectively for CSTNUs [16]) have been proposed. These algorithms apply rules to infer temporal constraints until no additional constraint can be deduced (DC holds), or a contradiction is detected (DC does not hold).
Nevertheless, supporting the design of temporally constrained processes and supporting the negotiation of temporal requirements need more than checking procedures returning "true" or "false", as current procedures do. However, based on these procedures, we were able to develop a system that provides significantly greater support for designers and requirements engineers, to analyze the cause of conflicts, to incrementally add constraints, and to compute which additional constraints are feasible.
Here, we present a temporal process designer that offers the following features:
• If a process is not dynamically controllable, we provide a procedure that shows the subsets of constraints that are in conflict. A designer then might adjust some of these constraints to resolve these conflicts and achieve dynamic controllability. • Temporal constraints may be added or deleted without the necessity to run the checking algorithm from scratch again. If a constraint is removed, all implicit constraints, which were derived from the removed constraint, are also removed and the other derived constraints remain. • The tool is able to compute the strictest constraint (e.g., the strictest deadline, the longest or shortest possible duration of an activity, the minimum and maximum time lap between two events, etc.) without losing dynamic controllability. This is, in particular, helpful for requirements engineering where some of the constraints are fixed (e.g., laws, nature, etc.) and other temporal requirements are adjustable goals or subject of negotiations [17], which allows resolving existing conflicts.
In this paper, we base our considerations on STNUs, which are simpler and have lower complexity than CSTNUs and are therefore better suited to present the principles of the approach and the features of the temporal process designer.
The remainder of this paper is structured as follows: in Sect. 2 we introduce a process model and discuss preliminary concepts; in Sect. 3 we analyze desirable features for supporting the design of processes with temporal constraints; in Sect. 4 we present a designer tool supporting these features; in Sect. 5 we discuss related work; in Sect. 6 we draw conclusions.
In this section, we introduce a process model that covers the most commonly found control flow patterns: sequence, inclusive and disjunctive splits, and the corresponding joins. We currently consider only processes that are acyclic and block-structured, which prevents the design flaws pointed out in [18].
As regards the temporal aspect of the process model, it allows the definition of activity durations, process deadline, and upper-and lower-bound constraints between events (start and end of activities). Time in the process model is measured in chronons, an abstract time unit representing, e.g., hours, days, ..., with domain the set of natural numbers, thus time points can be placed on an increasing time axis starting at 𝑧𝑒𝑟𝑜. Durations are defined as the distance between two time points on the time axis. For each activity, the process model specifies a duration range, i.e., an interval delimited by the minimum and maximum allowed duration for the activity execution. The process model allows the definition of contingent, non-contingent, and semi-contingent activity durations [19]. Contingent durations cannot be controlled, which means that it cannot be known in advance how long they will actually take: each actual duration is discovered at the completion of the associated activity. Non-contingent activity durations, instead, can be controlled at any time by the process controller, who can steer them to meet temporal constraints. Finally, semi-contingent activity durations can be decided by the executor, but each such duration can be chosen only up to the start time of the corresponding activity, and cannot be further changed.
A process 𝑃 is a tuple (𝑁 , 𝐸, 𝐶, Ω), where:
• 𝑁 is a set of nodes 𝑛 with 𝑛.𝑡𝑦𝑝𝑒 ∈ {𝑠𝑡𝑎𝑟𝑡, 𝑎𝑐𝑡𝑖𝑣𝑖𝑡𝑦, 𝑥𝑜𝑟 − 𝑠𝑝𝑙𝑖𝑡, 𝑥𝑜𝑟 − 𝑗𝑜𝑖𝑛, 𝑝𝑎𝑟 − 𝑠𝑝𝑙𝑖𝑡, 𝑝𝑎𝑟 − 𝑗𝑜𝑖𝑛, 𝑒𝑛𝑑}. Each 𝑛 ∈ 𝑁 is associated with two events: 𝑛.𝑠 and 𝑛.𝑒, representing the 𝑠𝑡𝑎𝑟𝑡 and 𝑒𝑛𝑑 events of 𝑛. • 𝐸 is a set of edges 𝑒 = (𝑛1, 𝑛2) defining precedence constraints.
• 𝐶 is a set of temporal constraints:
-duration constraints 𝑑(𝑛, 𝑛 𝑚𝑖𝑛 , 𝑛 𝑚𝑎𝑥 , 𝑑𝑢𝑟) ∀𝑛 ∈ 𝑁, where 𝑛 𝑚𝑖𝑛 , 𝑛 𝑚𝑎𝑥 ∈ ℕ, 𝑑𝑢𝑟 ∈ {𝑐, 𝑠𝑐, 𝑛𝑐}, stating that 𝑛 takes some time in [𝑛 𝑚𝑖𝑛 , 𝑛 𝑚𝑎𝑥 ]. 𝑛 can be contingent (𝑑𝑢𝑟 = 𝑐), semicontingent (𝑑𝑢𝑟 = 𝑠𝑐), non-contingent (𝑑𝑢𝑟 = 𝑛𝑐); -upper-bound constraints 𝑢𝑏𝑐(𝑎, 𝑏, 𝛿), where 𝑎, 𝑏 ∈ 𝑁 𝑒 , 𝛿 ∈ ℕ, requiring that 𝑏 ≤ 𝑎 + 𝛿; -lower-bound constraints 𝑙𝑏𝑐(𝑎, 𝑏, 𝛿), where 𝑎, 𝑏 ∈ 𝑁 𝑒 , 𝛿 ∈ ℕ, requiring that 𝑏 ≥ 𝑎 + 𝛿.
• Ω ∈ ℕ is the process deadline, specifying the maximum process duration.
To formally express the temporal semantics of the process model of Def. 1, we follow the approach shown in [20] and rely on the Simple Temporal Network with Uncertainty (STNU ). The STNU is a sound formalism to encode temporal problems in the presence of contingent and non-contingent durations. Furthermore, the STNU offers sound and complete algorithms for inferring temporal knowledge and checking temporal correctness. To be self contained, we present the STNU only informally, and refer the reader to [14] for a detailed formalization.
An STNU 𝑆(𝒯 , ℒ , 𝒞 ) is a network composed of nodes and edges. Nodes (set 𝒯) represent time points, and edges (set ℒ ∪ 𝒞) represent temporal constraints between time points. One special node 𝑍 ∈ 𝒯 represents the origin, or 𝑧𝑒𝑟𝑜 time point, after which all other time points occur. Edges can be either non-contingent (set 𝒞) or contingent (set ℒ). A non-contingent edge (𝐴, 𝐵, 𝛿) between two time points 𝐴 and 𝐵 represents a constraint, which the executor must satisfy, i.e., she must assign a value to 𝐵 such that 𝐵 ≤ 𝐴 + 𝛿 holds. A contingent edge, also called link, (𝐴 𝐶 , 𝑙, 𝑢, 𝐶) between two time points 𝐴 𝐶 and 𝐶 states that the value of 𝐶 will be observed to be between 𝑙 and 𝑢 after the value of 𝐴 𝐶 .
To express the temporal semantics of a process model, the process model can be mapped into a temporally equivalent STNU, i.e., the STNU is a complete encoding of all the elements of the process temporal aspect. The mapping is realized by applying mapping rules as follows:
Definition 2 (STNU-mapping). Let 𝑃(𝑁 , 𝐸, 𝐶, Ω) be a process model. The STNU 𝑆(𝒯 , ℒ , 𝒞 ) equivalent to 𝑃 is obtained by applying the following rules:
The mapping rules in Def. 2 transform the start and end events of the process model into two STNU nodes (rule 1); each process node into two STNU nodes, one for the start and one for the end of the process node (rule 2). With rule 3, each precedence constraint of the process model is mapped into a non-contingent STNU edge. The two STNU nodes resulting from a process node are connected by either a contingent link having the minimum and maximum duration bounds for the node duration if the duration is contingent (rule 4), or a pair of non-contingent edges if the duration is non-contingent or semi-contingent. All temporal constraints and the process deadline are mapped into non-contingent STNU edges (rules 6-8).
With the above mapping, we obtain a formal STNU encoding that includes all the temporal elements of the process model from Def. 1.
As shown in [20], the mapping of a process model into an STNU allows verifying the dynamic controllability (DC) of the process model by checking the DC of its equivalent STNU. Different methods exist for checking the DC of an STNU; here, we adopt the approach based on constraint propagation, due to its ability to infer implicit temporal knowledge. Essentially, DC is checked by propagating the constraints of an STNU until either a constraint causing a negative cyclein the sense of graph theory -is derived (then the STNU is not DC), or no more propagation is possible (then the STNU is DC). Here, we refer to constraints given by the modeler as preexisting or explicit; to constraints inferred through propagation as derived or implicit.
In this work, we adopt the RUL-system [10], which is a sound-and-complete and efficient constraint propagation system. For space reasons, we only briefly introduce the system and constraint propagation; for details we refer to [10].
The system consists of three distinct rules (RELAX, UPPER and LOWER) describing how implicit constraints can be derived from existing ones in an STNU. In general, each rule applies to three STNU nodes 𝐴, 𝐵, 𝐶 connected by consecutive constraints 𝑐1 and 𝑐2 (𝐴 The constraint propagation algorithm continuously iterates over the set of all combinations of three STNU nodes, and checks for the applicability of any of the three rules, until no rule can be applied or a negative cycle is derived. A negative cycle indicates that a set of constraints are contradicting, i.e., one constraint can only be fulfilled if another one is violated.
As an example, consider an STNU fragment with nodes 𝐴, 𝐵 and a constraint requiring 𝐵 to happen at most 3 time units after 𝐴 (edge 𝐴 3 − → 𝐵). Suppose that, with the RUL-system, another constraint has been derived, requiring 𝐴 to happen at least 4 time units before 𝐵. This results in the following edges: 𝐴
− − → 𝐴, hence a negative cycle, meaning that the STNU is not DC.
It is easy to see that a negative cycle entails a negative self-cycle, e.g., 𝐴 −1 − − → 𝐴. We use this observation to speed up our implementation of the DC-checking procedure.
In this section, we discuss actions that a process designer may perform when constructing a time-constrained process model, and present, for each action, how the design process may be optimized by our tool. Therefore we introduce first a conceptual model of our design approach (see Fig. 1).
The very first step for the process designer is to formalize a given process with temporal requirements. Our tool supports process modelling with an extended notation of UML activity diagrams that allows to explicitly model processes with temporal constraints (we call this extension Temporal Activity Diagrams).
In order to provide rigorous temporal support to the designer's actions, we transform the process model into an equivalent STNU, following the mapping rules described in Def. 2. This step is referenced by the initialize() operation in Fig. 1. An STNU is the formal representation of the temporal requirements of the process model and builds the foundation for our contribution since all operations are performed on STNU level. Once the process model has been initialized, we propose to check for pre-existing conflicts by running the checkDC() operation on the initial STNU. As described in Sect. 2.3, checking for dynamic controllability of an STNU is based on constraint propagation, thus requires to compute the STNU closure STNU*, i.e., the STNU with all propagated constraints. We use this fact as an advantage for an incremental design approachonly the closure STNU* is kept and updated in real time through operations of adding, removing or updating temporal constraints according to the changes in the process model.
However, the central question when designing processes with temporal constraints is whether the current process model yields a conflict (i.e., at least one constraint cannot be fulfilled without violating any other). Thus, a process designer may repeatedly check for dynamic controllability
Designer 1. If the model is DC (i.e., free of conflicts), a process modeller may go on and add further constraints. As an optimization, the complete STNU mapping is done only the first time the checking procedure is called. Further adding constraints does not require recomputing the closure with the implicit constraints. Therefore, the equivalent STNU for the DC-check is incrementally constructed by adding each time a new constraint to the STNU*. The DC-checking procedure only updates previously derived constraints if necessary. 2. If, during the design of a process, the DC-checking procedure reveals that the model is not DC (by discovering a negative cycle), with the incremental DC-checking, this means that the last added constraint yields a conflict with some preexisting constraints. At this point, a process designer needs to identify which constraints actually cause the conflict, and may check which alternative constraint would instead introduce no conflict.
In the following, we describe how we can identify conflicting temporal constraints by keeping track of the provenance of derived constraints during execution of the DC-checking procedure, and how we can compute the most restrictive constraint such that a given model remains conflict-free. In order to enhance the reader's understanding of the approach, we introduce a small running example.
In Fig. 2 we show an example activity diagram of a process with temporal constraints. There are four activities (𝐴, 𝐵, 𝐶, 𝐷), whereas 𝐵 and 𝐶 are executed in parallel. Each activity is associated with a duration and duration type (contingent, non-contingent). There are also two upper-bound constraints: one requires the process to end within 25 time units, and one requires 𝐷 to start at most 5 time units after 𝐴 has finished.
The application of the DC-checking algorithm will derive the negative self-loop 𝐷 −1 − − → 𝐷, meaning that the given process model is not DC. If the system could keep track of how implicit constraints are derived, we would know that the negative self loop origins in the contradiction between the UBC that requires 𝐷 to start at most 5 time units after 𝐴 and the maximum duration of 6 time units of the contingent activity 𝐶. Due to the uncertain duration of 𝐶, 𝐷 can start at the earliest 6 time units after 𝐴 finished, resulting in the fact that it is impossible to satisfy both constraints. In the next section, we show how to identify the origin of such a conflict.
Given a conflict between constraints, how can a process designer determine which existing temporal constraints have to be adjusted such that dynamic controllability can be achieved? A possible solution is to keep track of how implicit constraints are derived.
For any implicit constraint 𝑐, there are exactly two other constraints 𝑐 ′ , 𝑐 ″ for which the application of either the RELAX, UPPER or LOWER rule derives 𝑐. So for each implicit constraint 𝑐 there is a triple 𝑝 𝑐 = ⟨𝑐 ′ , 𝑐 ″ , 𝑟⟩ called provenance of 𝑐, where 𝑐 ′ and 𝑐 ″ are constraints and 𝑟 is the rule that derived 𝑐: Definition 3 (Provenance of a Constraint). Let 𝑆(𝒯 , ℒ , 𝒞 ) be an STNU. Let 𝑐 ∈ 𝒞 be an implicit constraint; let 𝑟 ∈ {𝑅𝐸𝐿𝐴𝑋 , 𝑈 𝑃𝑃𝐸𝑅, 𝐿𝑂𝑊 𝐸𝑅}; let 𝑐 ′ , 𝑐 ″ ∈ 𝒞 ∪ ℒ such that 𝑐 = 𝑟(𝑐 ′ , 𝑐 ″ ) 1 .
The provenance of 𝑐 is 𝑝 𝑐 = ⟨𝑐 ′ , 𝑐 ″ , 𝑟⟩, and it indicates that 𝑐 is the implicit constraint derived from the application of rule 𝑟 to constraints 𝑐 ′ , 𝑐 ″ .
Computing the transitive closure of the provenance of a constraint 𝑐, we can determine the preexisting constraints from which 𝑐 was derived. We call the transitive closure of the provenance the history of 𝑐, and the preexisting nodes in the history the origin of 𝑐. Definition 4 (History and Origin of a Constraint). Let 𝑆(𝒯 , ℒ , 𝒞 ) be an STNU. Let 𝑐 ∈ 𝒞 be an implicit constraint with provenance 𝑝 𝑐 = ⟨𝑐 ′ , 𝑐 ″ , 𝑟⟩.
The history of 𝑐 is the transitive closure 𝑝 + 𝑐 of 𝑝 𝑐 . The origin of 𝑐 is the set of preexisting constraints 𝑐 𝑒 𝑖 ∈ 𝑝 + 𝑐 such that 𝑝 𝑐 𝑒 𝑖 = ∅. Since any derived edge by the RUL-system comes from triangular reductions, the history of each constraint can be represented as binary tree, in which internal nodes represent implicit constraints, edges from a node to its children represent the node provenance, and leaf nodes represent preexisting constraints.
As an example, let 𝑆 be an STNU derived by the transformation of the example process described in Sect. 3.1, the subset of nodes {𝐴.𝑒, 𝐶.𝑠, 𝐶.𝑒, 𝐷.𝑠} and a subset of constraints 𝑐0(𝐴.𝑒 In order to identify which constraints cause the conflict we now compute 𝑝 + 𝑐6 , the transitive closure of 𝑝 𝑐6 , by computing the provenance of 𝑐0 and 𝑐5. Since 𝑐0 is a pre-existing constraint we already identified one of the conflicting constraints. For 𝑐5, however, we still have to compute the provenance. The origin of 𝑐5 are the leaf nodes 𝑐1, 𝑐2, 𝑐3 of the binary tree (see Fig. 3). Since both 𝑐1 and 𝑐3 are precedence constraints (given by the process flow), we can determine 𝑐2 and 𝑐0 as conflicting constraints meaning that the negative self loop origins in the contradiction between the UBC that requires 𝐷 to start at most 5 time units after 𝐴 and the maximum duration of 6 time units of the contingent activity 𝐶. Due to the uncertain duration of 𝐶, 𝐷 can start at the earliest 6 time units after 𝐴 finished, resulting in the impossibility to satisfy both constraints.
To support the identification of constraints causing a contradiction with a newly added constraint, it is therefore useful to keep track of the provenance of constraints. By maintaining the provenance of each derived constraint during constraint propagation (e.g., as a binary tree), a designer can inspect the history of a constraint forming a self-loop in the case of a non-DC process model, and modify these constraints in order to resolve the conflict between constraints.
When process designers know the origin of a conflict between constraints, they might consider removing selected constraints to resolve the conflict. Usually, removing constraints requires re-running the DC-checking procedure, re-computing already derived implicit constraints.
An optimization is possible if we keep track of the provenance of each derived constraint generated with the modified RUL-system. We can use the provenance of each implicit constraint for optimizing the design process, by only re-computing the necessary constraints. For any removed constraint 𝑐, we remove all constraints 𝑐 ′ where 𝑐 ∈ 𝑝 + 𝑐 ′ . Any other constraint can be kept and does not have to be recomputed, since its history does not include 𝑐.
It may not always be possible to remove a constraint that is causing a conflict from a process model. Alternatively, a process designer may need to adjust existing constraints, so that the process model becomes DC, without over-constraining the model. Thus, we might ask the question: given any two nodes in an STNU, which is the most restrictive non-contingent constraint that can be added without introducing a conflict with preexisting constraints?
The most restrictive non-contingent constraint is defined as follows:
Definition 5 (Most Restrictive Non-contingent Constraint). Let 𝑆(𝒯 , ℒ , 𝒞 ) be an STNU. Let 𝐴, 𝐵 ∈ 𝒯 be two STNU nodes. The most restrictive non-contingent constraint between 𝐴 and 𝐵 is 𝐴 − 𝐵 ≤ 𝛿, with 𝛿 the minimum value such that 𝑆(𝒯 , ℒ , 𝒞 ∪ {𝐴 − 𝐵 ≤ 𝛿}) is DC, and for any
From Def. 5 it follows that, given the most restrictive constraint 𝑐 = 𝐴 − 𝐵 ≤ 𝛿, adding any non-contingent constraint 𝐴 − 𝐵 ≤ 𝛿 ″ , if 𝛿 ≤ 𝛿 ″ , will preserve DC property. However, it is sufficient to find the most restrictive constraint, since it is always possible to relax a constraint without introducing conflicts. We consider only non-contingent constraints, because contingent constraints come from external sources and cannot be controlled by the modeler.
Our proposed binary search approach to finding the most restrictive non-contingent constraint is shown in Alg. 1. The approach works as follows: for any two nodes 𝐴, 𝐵 in a STNU 𝑆, we can determine the most restrictive non-contingent constraint 𝑐 = 𝐴 − 𝐵 ≤ 𝛿 by adding 𝑐 to 𝑆, run execute the DC-checking procedure and then either increase the value of 𝛿 if 𝑆 is not DC, or decrease 𝛿 if 𝑆 is DC. This is done recursively, as it is a common practise for binary search. The procedure halts if 𝑆 is DC and 𝛿 cannot decrease by the smallest possible value without letting 𝑆 be not DC. Since we keep the provenance of derived constraints, we do not have to start from scratch every time we increase (or decrease) 𝛿 and check if 𝑆 is DC: we can simply drop all constraints derived from 𝑐, and keep any other.
In case of our running example (described in Sect. 3.1), we already know that 𝑐2 and 𝑐0 are in a conflict (see Sect.3.2). We assume that 𝑐2 cannot be adjusted since it describes the maximum duration of a contingent activity. Thus, a process designer might wish to adjust 𝑐0 such that the process model is DC. The described approach will determine that for 𝑐0(𝐴.𝑒 𝛿 − → 𝐷.𝑠) with any 𝛿 ≥ 6 the process model is DC.
We implemented the features presented in Sect. 3 into a process designer tool, and performed a series of experiments on a set of processes to show that our approach is feasible.
For our implementation we focused on providing an intuitive and lightweight modelling environment for processes with temporal constraints2 , rather than a fully fledged BPMN editor. Thus, we chose to use UML activity diagrams as an underlying modelling language and extended it with temporal constructs such as activity durations and upper-and lower-bound constraints according to the process model (see Def. 1).
The application was developed using ReactJs, a lightweight JavaScript library for implementing web applications. This library was chosen, because it is an easy to use and modern library with a vast amount of packages for different use cases. For drawing the graphs the library react-flow was used, because it is an highly customizeable and flexible react-library for creating graphs of all sorts. The react application also communicates with a spring webservice, which provides the main functionality of the designer tool -checking for inconsistencies and computing most restrictive non-contingent constraints.
Modelling processes is easy. A user can pick a modelling element (start/end event, activity, fork/join) an drag it to the canvas. Start/end events and for/join nodes do not have any special properties. Activities, however, require a minimum and a maximum duration and a type. Allowed types are non-contingent, contingent and semi-contingent. Inserting flow edges requires the user to connect center handles of two elements. Connecting top or bottom handles allows to insert a temporal constraint. Temporal constraints can either be UBC or LBC. As a modeler designs a process with the operations discussed in Sect. 3, the equivalent STNU is automatically constructed for the DC-check of the process model. Figure 4 shows a screenshot of the tools user interface.
In order to show the practical applicability of the designer tool, we measured the computation times for the two main functionalities 1) incremental dynamic controllability checking and 2) the computation of most restrictive non-contingent constraints on a regular Windows 10 physical machine with an i7 CPU and 16GB of RAM. As a basis, we used a set of 50 pre-generated random process models with different size and configuration of constraints. For each experiment we structured our set of process models into subsets of similar size. This resulted in 5 subsets with 10, 20, 30, 40 and 50 activities (each subset including 10 processes). With growing size, also the amount of temporal constraints within the process models increases, giving us the smallest process with a total of 25 STNU nodes and 2 temporal constraints and the largest process with a total of 129 STNU nodes and 10 temporal constraints.
In Table 1 we show the measured minimum, maximum, and average times for checking dynamic controllability on the processes of the test set.
Table 2 shows the measured minimum, maximum, and average times for computing the most restricitve non-contingent constraint with binary search (described in Alg. 1). Overview of computation times for the execution of Alg. 1.
The design of business processes with temporal constraints has been considered in several prior works. In [21] the concepts of upper-and lower-bound constraints were introduced. The work in [22] addressed the representation of such temporal constraints and activity durations in a BPMN-like language. In [7] the authors raised the need to distinguish between contingent and non-contingent durations in business process, while the authors of [19] introduced the notion of semi-contingent durations. Finally, [5] posed an essential basis for the consolidation of patterns of temporal constraints in the design of business processes. Checking the controllability of dynamic systems such as business processes is subject to extensive research, with most approaches based on mapping to some kinds of Temporal Constraint Networks ( [12,23]), or Timed Automata [24,25].
A recent publication [26] proposes a tool for modelling business processes as time-aware extension of a the BPMN notation (TimeAwareBPMN-js). The authors adapted the bpmn-js toolkit offered by Camunda to allow modelling processes with temporal constraints on a subset of BPMN elements and provides functionality for checking for dynamic controllability. In contrast to [26], our proposed modeling tool incrementally constructs the STNU equivalent to the process model, and is able to show to the process designer the provenance of any implicit temporal constraint, aiding the adjustment of temporal constraints.
To the best of our knowledge, there exists only one technique dedicated to the problem of finding the most restrictive constraint between two time points, found in [23]. The approach in [23] introduces piece-wise linear functions to the formalism of STNUs and uses a modified version of the MMV constraint propagation system [14]. Although this approach is elegant, we propose a binary search as a competitive and in fact more simple alternative approach.
Adequate engineering of temporal requirements is essential for successful execution of timeconstrained business processes. However, practitioners could not benefit from advancements in the research so far, as existing algorithms were focusing on checking given process models rather than supporting the development of correct process models. The ambition of this work was to leverage on recent theoretical results to develop a system supporting the needs and tasks of process designers to reach models free from conflicting constraints.
We developed a tool to support both designing time-constrained process models, as well as negotiating temporal requirements by assuring that the temporal constraints are not conflicting. Our approach assumes that it is within the capacity of a process controller to steer the execution of a process in a way that no temporal constraint is violated. The tool offers a number of features for verifying temporal properties (e.g., dynamic controllability, provenance of inconsistencies), and for giving guidance (e.g., which are the admissible temporal constraints) in the design of a time-constrained process.
We regard our work as a significant contribution to bridging the gap between theoretical research achievements and practical applications. For the future, we plan to extend our tool to offer more expressive temporal constraint networks, to cater for different process model notations, in particular, BPMN and EPC, and advanced temporal control structures.