A Constraint-based Approach for a Declarative Temporal Business Process Modeling Language

A Constraint-based Approach for a Declarative Temporal Business Process Modeling Language Andres Jimenez-Ramirez1and Irene Barba1 Departamento de Lenguajes y Sistemas Inform´aticos, University of Seville, Spain, 1 Defining TConDec-R Process Models based on High-level Elements from CP We propose the mapping of TConDec-R process models to CSPs, resulting in CSP-TConDec-R problems. In the current section, we provide a definition of the latter in terms of high-level objects and global constraints from CP. Based on this, TConDec-R process models can be implemented in any constraint-based system being able to deal with the high-level objects and constraints considered in such definition. Consequently, the wide variety of existing algorithms provided by CP becomes applicable and we can use them for different purposes, e.g., checking the consistency of a given TConDec-R process model. According to the CSP model, we define the high-level object SchedAct to represent scheduling activities as follows: SchedAct :hst −CSP int, et −CSP int, res −CSP int, sel −CSP inti Additionally, to represent a sequence of scheduling activities, we consider the high-level object Sequence, which represents a sequence of elements. In this context, let sbe a sequence and prop be a property of the elements of s. Then, expression s.prop denotes a set of properties including property prop for each element of s. Considering this, each repeating activity is modeled as a high-level object called RepAct, which includes a sequence of SchedAct objects. To be more precise, the high-level object RepAct is defined as follows: RepAct :hdur −int, roles −Sequence(int), nt −CSP int, sacts −Sequence(SchedAct)i Note that property roles of the repeating activities is represented by a sequence of integers in such a way that the sequence includes the identifiers of the required roles. Since a process instance may be considered as a sequence of activity executions, we use the high-level object Sequence(SchedAct) to model process instances. The constraint-based approach we propose represents each TConDec-R constraint through a global constraint [4], i.e., a constraint that encapsulates the behavior of a set of other constraints [3]. On one hand, global (i.e., high-level) constraints represent high-level modeling abstractions that allow defining more compact models. The goal is to facilitate the specification of such models and, 2 Andres Jimenez-Ramirez1and Irene Barba1 hence, to reduce the risk of modeling errors. On the other hand, global constraints may be associated with more powerful filtering algorithms as they can take the semantics of combined simple constraints into account in order to increase the efficiency when solving a CSP [3]. This section provides a formalization of the global constraints related to the TConDec-R process models. This formalization, in turn, is based on global constraints from the constraint programming paradigm. To be more precise, the respective global constraints are taken from the catalogue of global constraints as introduced in [1] (see below). Such formalization is required in order to detail how the constraints of a TConDec-R process model are encoded when generating and implementing the respective CSP, i.e., the related CSP-TConDec-R problem. As aforementioned, TConDec-R constraints cover both Declare constraints and complex temporal constraints. To keep the number of time patterns manageable, design choices are used for their parametrization. As the number of resulting pattern variants (and, hence, TConDec-R constraints) is high, we consider one characteristic example for each group of TConDec-R constraints and demonstrate its formalization. To be more precise, for each selected TConDec-R constraint, its formalization is presented based on the given catalogue of global constraints [1]1. Moreover, the equivalent low-level (i.e., elementary) constraints of this formalization are provided as well. From this information, two equivalent implementations can be obtained: one of them is based on global constraints, whereas the other relies on low-level constraints. Note that the formalization of all TConDec-R constraints, which correspond to the same group, can be performed in a similar way. 1.1 Declare Existence Constraints Existence constraints are unary relationships constraining the number of times an activity may be executed in the context of a particular process instance. Example 1. (TConDec-R existence constraint). Exactly(A,n) specifies that the repeating activity Amust be executed exactly ntimes for each process instance. We formalize Exactly(A,n) using constraint exactly(N, Variables, Value) from the well-known Global Constraint Catalogue [1], which states that exactly Nvariables of V ariables must be equal to V alue: Exactly (A ,n) n: int A: RepAct High level : exactly (n , A. sacts .sel , 1) Low level : n = count(act in A. sacts ) act.sel 1Note that this catalogue is independent of any constraint-based language. A Constraint-based Approach for TConDec-R Models 3 1.2 Declare Relation Constraints Relation constraints are positive binary relationships used to either enforce or allow for the enactment of activities in certain situations. Example 2. (TConDec-R relation constraint). Precedence(A,B) specifies that activity Bmay only be executed if Ais executed before. We formalize Precedence(A, B) using constraint precedence(SchedActs) from the Global Constraint Catalogue [1]. This constraint states that all consecutive pairs of activities of the sequence SchedActs should be ordered: Precedence (A, B) A,B: RepAct High level : B. sacts [1]. sel =1 =⇒ precedence (hA. sacts [1] , B.sacts [1]i) Low level : B. sacts [1]. sel =1 =⇒A. sacts [1]. et ≤B. sacts [1]. st 1.3 Declare Negation Constraints Negation constraints are negative binary relationships used to forbid the enactment of certain activities in specific situations. Example 3. (TConDec-R negation constraint). NotCoexistence(A,B) expresses that Aand Bare mutually exclusive, i.e., Amust not be executed if Bis executed, and vice versa. We formalize NotCoexistence(A, B) using constraint atmost(N, Variables, Value) from the Global Constraint Catalogue [1]. In turn, this constraint states that at most Nvariables of V ariables must be equal to V alue: NotCoexistence(A, B) A,B: RepAct High level : exactly (1 , hA. sacts [1]. sel ,B. sacts [1]. seli, 1) Low level : A. sacts [1]. sel + B.sacts [1]. sel ≤1 1.4 Time Pattern TP1: Time Lags between Two Activities This temporal constraint pattern enables the definition of different kinds of time lags between two activities. 4 Andres Jimenez-Ramirez1and Irene Barba1 Example 4. (TConDec-R constraint related to TP1). TimeLagEndStart(A,B,Low,Up) expresses that for each execution Aiof Athere must exist at least one execution Bjof B in such a way that there is a time lag of at least Low time units and at most Up time units between the end time of Aiand the start time of Bj. Moreover, for each execution Bjof B there must exist at least one execution Ai of A in such a way that there is a time lag of at least Low time units and at most Up time units between the end time of Aiand the start time of Bj. We formalize TimeLagEndStart(A, B, Low, Up) using constraint among interval(Value, Variables, Low, Up) from the Global Constraint Catalogue [1]. This constraint states that V alue corresponds to the number of elements of V ariables taking a value that is located within the interval [Low,Up]: TimeLagEndStart (A, B , Low , Up) A,B: RepAct Low ,Up: int High level : forall(Aiin A. sacts ){ among_interval (1,B. sacts.st ,Ai.et +Low ,Ai.et+Up) } forall(Biin B. sacts ){ among_interval (1,A. sacts.et ,Bi.st -Low ,Bi.st -Up ) } Low level : forall(Aiin A. sacts ){ 1≤count (Bjin B.sacts ) Bj.st ≥Ai.et+Low ∧Bj.st ≤Ai.et +Up } forall(Biin B. sacts ){ 1≤count (Ajin A.sacts ) Aj.et ≤Bi.st - Low ∧Aj.et ≥Bi.st -Up } 1.5 Time Pattern TP2: Durations This temporal constraint pattern allows specifying the duration of a particular activity or process. Example 5. (TConDec-R constraint related to TP2). MaximumInstance- Duration(PI, D) expresses that the execution of a process instance must not take longer than D time units. We formalize MaximumInstanceDuration(PI, D) using constraint range(Variables, CTR, Value) from the Global Constraint Catalogue [1]. This constraint, in turn, states that the difference between the maximum and minimum value of V ariables must fulfill constraint ’CTR V alue’, where CTR ∈ {=,6=, <, ≤, >, ≥}: MaximumInstanceDuration (PI , D) A Constraint-based Approach for TConDec-R Models 5 PI: RepAct D: int High level : range (PI.sacts.st ∪PI. sacts .et , ≤, D) Low level maximum (PI .sacts . et ) - minimum (PI .sacts . st ) ≤D 1.6 Time Pattern TP4: Fixed Date Element The Fixed Date Element pattern provides support for specifying a deadline. Example 6. (TConDec-R constraint related to TP4). DeadlineEnd(A,Date) expresses that all executions of A should finish before Date. We formalize Dead- LineEnd(A, Date) using global constraint among interval [1]. Note that the latter was already explained in the context of Example 4: DeadLineEnd (A, Date ) A: RepAct Date : int High level : among_interval (|A. sacts|, A.sacts .et , 0, Date) Low level : forall ( schAct in A. sacts ){ schAct .et ≤Date } 1.7 Time Pattern TP5: Schedule Restricted Element This temporal constraint pattern allows restricting the execution of a particular activity or process by a schedule. Example 7. (TConDec-R constraint related to TP5). DailyScheduleStart(A,Low,Up) expresses that each execution of A must be started between Low and Up. We formalize DailyScheduleStart(A, Low, Up) using the global constraint among interval [1], which was already explained in the context of Example 4: DailyScheduleStart (A, Low , Up) A: RepAct Low , Up: int High level : among_interval (|A. sacts |, A. sacts .st , Low , Up) Low level : forall ( schAct in A. sacts ){ schAct .st ≥Low ∧schAct.st ≤Up } 6 Andres Jimenez-Ramirez1and Irene Barba1 1.8 Time Pattern TP6: Time-based Restrictions Time-based restrictions correspond to a temporal constraint pattern that provides support for restricting the number of times a particular activity or process may be executed within a predefined time frame. Example 8. (TConDec-R constraint related to TP6). TimeBasedExclusive1of2Daily(A,B) expresses that either the first execution of activity A or the first one of activity B (but not both) shall be scheduled on the same day. We formalize TimeBasedExclusive1of2Daily(A,B) using constraint alldifferent interval(Variables, Value) from the Global Constraint Catalogue [1]. This constraint, in turn, enforces all elements of V ariables to belong to distinct intervals defined by [V alue ·k, V alue ·(k+ 1) −1], where kis an integer: TimeBasedExclusive1of2Daily (A,B) A,B: RepAct High level : all_different_interval ( hA. sacts [1].st ,B. sacts [1]. sti , 24*60) Low level : A. sacts [1]. st /(24*60) 6=B. sacts [1]. st /(24*60) Note that the expression 24 ∗60 is used to specify the minutes contained in one day as the granularity of one minute is considered. In addition, operator ′/′ represents the integer part of the division of two numbers. 1.9 Time Pattern TP7: Validity Period This temporal constraint pattern allows restricting the lifetime of a particular activity or process to a given validity period. Example 9. (TConDec-R constraint related to TP7). ValidityStart(A,Date) expresses that any execution of activity A may only be started until Date is reached. Afterwards, activity A must not be executed anymore. We formalize ValidityStart(A,Date) using global constraint among interval [1], which was already explained in the context of Example 4: ValidityStart (A, Date ) A: RepAct Date : int High level : among_interval (|A. sacts|, A.sacts .st , 0, Date) Low level : forall ( schAct in A. sacts ){ schAct .st ≤Date } A Constraint-based Approach for TConDec-R Models 7 1.10 Time Pattern TP8: Time Dependent Variability This temporal constraint pattern allows varying control flow, depending on the execution time or time lags between activities and events respectively. Example 10. (TConDec-R constraint related to TP8). VariabilityTimeLagEndStart(A,B,C,Low,Up) expresses that if the first execution of activity B is not started within time lag [Low,Up] after finishing the first execution of activity A, activity C shall be executed. We formalize VariabilityTimeLagEndStart(A,B,C,Low,Up) using constraint in interval(Var, Low, Up) from the Global Constraint Catalogue [1]. This constraint enforces V ar to take a value within interval [Low, Up]: VariabilityTimeLagEndStart (A,B,C ,Low , Up) A,B,C: RepAct Low , Up: int High level : A. sacts [1]. sel =1 =⇒ in_interval (B. sacts [1]. st -A. sacts [1].et ,Low ,Up) ∨C. sacts [1]. sel =1 Low level : (A [1]. sel =1 ∧B. sacts [1]. st ≥A.sacts [1]. et + Low ∧B. sacts [1]. st ≤A.sacts [1]. et + Up) ∨C. sacts [1]. sel =1 1.11 Time Pattern TP9: Cyclic Elements This temporal constraint pattern provides support for specifying time lags between activities or activity instances contained within a loop structure. Example 11. (TConDec-R constraint related to TP9). CyclicStartStart(cA, T) expresses that between the start of each execution of A there must be at least T time units. We formalize CyclicStartStart(A, T) using constraint all min distance(Value, Variables) from the Global Constraint Catalogue [1]. This constraint enforces for each pair (vari, varj)∈V ariables to satisfy |vari−varj| ≥ V alue: CyclicStartStart (cA , T) A: RepAct T: int High level : all_min_distance (T, A. sacts .st) Low level : forall (i in [1 , A.nt -1]){ A. sacts [i +1]. st ≥A. sacts[i]. st + T } 8 Andres Jimenez-Ramirez1and Irene Barba1 1.12 Time Pattern TP10: Periodicity The periodicity pattern allows specifying periodically recurring activities based on an explicit periodicity rule. Example 12. (Constraint related to TP10). PeriodicityStart(A,T,Periodicity) expresses that activity A should be started at time T according to the given periodicity. We formalize PeriodicityStart(A,T,Periodicity) as follows: PeriodicityStart (A ,T, Periodicity ) A: RepAct T, Periodicity : int Low level : forall (i in [1 , A.nt ]){ 1= count ( act in A.sacts ) act .st = i* Periodicity +T } Regarding the formalization of the periodicity pattern (TP10), we could not find any global constraint in the considered catalogue [1] that fits with the needs of such pattern. Therefore, only the formalization based on low-level constraints is depicted as the formalization based on high-level constraints does not make sense for this pattern. Considering the mapping of TConDec-R process models to CSPs as well as the formalization of the TConDec-R constraints, the implementation of these process models can be performed in any constraint-based system that is able to deal with the high-level objects and global constraints of the considered catalogue (e.g., IBM ILOG CPLEX Optimization Studio [2]). Such implementation allows for different applications, i.e., to check for the consistency of a given TConDec-R process model, to check for the conformance of specific process instance with a given TConDec-R process model, or to generate process instances being compliant with such model. References 1. Global Constraint Catalog. http://sofdem.github.io/gccat/. [Online; accessed 20-June-2017]. 2. IBM. IBM ILOG CPLEX Optimization Studio. urlhttp://www- 03.ibm.com/software/products/en/ibmilogcpleoptistud/, 2016. [Online; accessed 11-July-2016]. 3. J.C. R´egin. Global constraints: A survey. In Hybrid optimization, pages 63–134. Springer, 2011. 4. F. Rossi, P. van Beek, and T. Walsh, editors. Handbook of Constraint Programming. Elsevier, 2006.