P ROD P ROC - Product and Production Process Modeling and Configuration ⋆ Dario Campagna and Andrea Formisano Dipartimento di Matematica e Informatica, Università di Perugia, Italy (dario.campagna|formis)@dmi.unipg.it Abstract. Software product configurators are an emerging technology that sup- ports companies in deploying mass customization strategies. Such strategies need to cover the management of the whole customizable product cycle. Adding pro- cess modeling and configuration features to a product configurator may improve its ability to assist mass customization development. In this paper, we describe a modeling framework that allows one to model both a product and its production process. We first introduce our framework focusing on its process modeling ca- pabilities. Then, we outline a possible implementation based on Constraint Logic Programming of such product/process configuration system. A comparison with some of the existing systems for product configuration and process modeling concludes the paper. 1 Introduction In the past years many companies started to operate according to mass customization strategies. Such strategies aim at selling products that satisfy customer’s needs, pre- serving as much as possible the advantages of mass production in terms of efficiency and productivity. The products offered by such companies, usually called configurable products, have a predefined basic structure that can be customized by combining a se- ries of available components and options (modules, accessories, etc.) or by specifying suitable parameters (lengths, tensions, etc.). Actually, a configurable product does not correspond to a specific physical object, but identify sets of (physical) objects that a company can realize. A configured product is a single variant of a configurable product, obtained by specifying each of its customizable attributes, which corresponds to a fully- specified physical object. The configuration process consists of a series of activities and operations ranging from the acquisition of information about the variant of the product requested by the customer, to the generation of data for its realization. The mass customization operating mode involves a series of difficulties that compa- nies struggle to resolve by using traditional software tools, designed for repetitive pro- ductions. As more companies started offering configurable products, different systems designed for supporting them in deploying mass customization strategies appeared. These systems are called software product configurators and allow one to effectively and efficiently deal with the configuration process [21]. They offer functionality for the ⋆ Research partially founded by GNCS-2011 and MIUR-PRIN-2008 projects, and grants 2009.010.0336 and 2010.011.0403. representation of configurable products through product models, and for organizing and managing the acquisition of information about the product variants to be realized. Mass customization strategies need to cover the management of the whole cus- tomization product cycle, from customer order to final manufacturing. Current soft- ware product configurators focus only on the support to product configuration, and do not cover aspects related to the production process planning. Extending the use of con- figuration techniques from products to processes, may avoid or reduce planning im- possibilities due to constraints introduced in the product configuration phase, as well as configuration impossibilities due to production planning requirements. Existing lan- guages/tools for process modeling, such as BPMN [28] and YAWL [24], do not offer suitable features for specifying production processes and process configuration. More- over, they lack the capability of modeling, in a single uniform setting, product models and their corresponding process models. The framework we propose, called P ROD - P ROC, intends to overcome these limitations and act as a core for a full-fledged config- uration system, covering the whole customization product cycle. 2 A Framework for Product/Production Modeling In this section we present the P ROD P ROC framework by exploiting a working example that will be used throughout the paper (cf., Sections 2.1 and 2.2). We also provide a brief description of P ROD P ROC semantics in term of model instances (Sect. 2.3). See [6] for a description of P ROD P ROC graphical modeling language. A P ROD P ROC model consists of a description of a product, a description of a pro- cess, and a set of constraints coupling the two. In order to introduce the P ROD P ROC features let us consider a rectangular base prefabricated component multi-story build- ing, together with its construction process. More specifically, a building is composed by the followings parts: story, roof, heating service, ventilation service, sanitary ser- vice, electrical/lighting service, suspended ceiling, floor, partition wall system. For the purposes of this paper, we consider two types of building: Warehouse: it is a single story building, it has no mandatory service except for the electrical/lighting service, it has no partition wall system and no suspended ceiling, it may have a basement. Office building: it may have a basement and up to three stories, all services except ventilation are mandatory, suspended ceiling and floor are mandatory for each story, each story may have a partition wall system. The building construction process can be split in four main phases: preparation and de- velopment of the building site; building shell and building envelope works; building ser- vices equipment; finishing works. (For a detailed description of such phases see [23].) 2.1 Product Description A product is modeled as a multi-graph, called product model graph, and a set of con- straints. The nodes of the graph represent the components of the product. The edges represent the has-part/is-part-of relations between product components. We require the presence of a node without entering edges in the product model graph. We call this Ventilation service ventilation sanitary Sanitary service {0,1} {0,1} Building 1 {0,1} Electr./Light. electr./light. heating Heating service service {0,1} basement first story Basement {0,1} 1 upper story roof Story Roof {0,1} ceiling walls floor {0,1} {0,1} {0,1} Partition wall Suspended ceiling Floor system Fig. 1. Building product model graph. node root node. Such a product description will represent a configurable product whose configuration can lead to the definition of different (producible) variants that can be represented as trees. Nodes of these trees correspond to physical components, whose characteristics are all determined. The tree structure describes how the single compo- nents taken together define a configured product. Fig. 1 shows the product model graph for our example. Edges are labeled with names describing the has-part relations and numbers indicating the admitted values for the cardinalities. Each node/component of a product model graph is characterized by a name, a set of variables representing configurable features of the component, and a set of constraints that may involve variables of the node as well as variables of its ancestors in the graph. Each variable is endowed with a finite domain (typically, a finite set of integers or strings), i.e., the set of its possible values. In the description of a configured product, physical components will be represented as instances of nodes in the product model graph. An instance of a node N odeN ame consists of the name N odeN ame, a unique id, and a set of variables equals to the one of N odeN ame. Each variable will have a value assigned. The instance of the root node will be the root of the configured product tree. For example, the node Building in Fig. 1, which is the root node of the product model graph, is defined as the triple hBuilding, VBuilding , CBuilding i, where the in- volved variables and the set of constraint are as follows: VBuilding = {hBuildingT ype, {Warehouse, Office building}i, hStoryN um, [1, 3]i, hW idth, [7, 90]i, hLength, [7, 90]i}, CBuilding = {BuildingT ype = Warehouse ⇒ StoryN um = 1}. Hence, a building is described by four features/variables, each one with a set of possi- ble values. Note that the single constraint associated with the node imposes that if the building is a warehouse, then it must have exactly one story. The node representing a story of the building is defined as hStory, VStory , CStory i, where: VStory = {hF loorN um, [1, 3]i, hHeight, [3, 15]i}, CStory = {F loorN um = hF loorN um, Story, [upper story]i + 1, F loorN um ≤ hStoryN um, Building, [f irst story, ⋆]i, hBuildingT ype, Building, [f irst story, ⋆]i = Office building ⇒ ⇒ Height ≥ 4 ∧ Height ≤ 5}. In this case we have two variables associated with the node Story, whose values are controlled by three constraints. Note that these constraints involve features/variables associated with ancestors of the node Story. To refer to specific variables in the an- cestors of a node, we introduce the notion of meta-variable, i.e., a triple of the form hV arN ame, AncestorN ame, M etaP athi. This triple denotes a variable V arN ame in an ancestor node AncestorN ame (e.g., BuildingT ype in the node Building). The third component of a meta-variable, M etaP ath, is a list of edge labels (see below) and describes a path connecting the two nodes in the graph (wildcards ‘_’ and ‘⋆’ can be used to represent arbitrary labels and a sequence of arbitrary labels, respectively). M etaP aths are used to define constraints that will have effect only on particular in- stances of a node. For example, the first constraint in CStory will have to hold only for those instances of node Story which are connected to another instance of node Story through an edge labeled upper story. Intuitively, a node constraint for the node N will have to hold for each instance of N , such that it has ancestors connected with it through paths matching with the M etaP aths occurring in the constraint. An edge is defined by: a name, two node names indicating the parent and the child nodes in the has-part relation, the cardinality of such relation (expressed as either an integer number or a variable), and a set of constraints. Such constraints may involve the cardinality variable (if any) as well as the variables of the parent node and of any of its ancestors (referred to by using meta-variables). An instance of an edge la- beled label connecting a node N with a node M , will be an edge labeled label, con- necting an instance of N and an instance of M . Let us consider the edges first story and upper story of our sample model. The former is the edge that relates the build- ing and its first story. It is defined as hf irst story, Building, Story, 1, ∅i. Note that the cardinality is imposed to be 1 and there is no constraint. The edge upper story represents the has-part relation over two adjacent stories of the building. It is de- fined as hupper story, Story, Story, Card, CCi, where the variable Card is defined as hCard, [0, 1]i, while the set of constraints is defined as follows: CC = {F loorN um = hStoryN um, Building, [f irst story, ⋆]i ⇒ Card = 0, F loorN um < hStoryN um, Building, [f irst story, ⋆]i ⇒ Card = 1}. The two constraints in CC control the number of instances of the node Story. An in- stance of the node Story will have as child another instance of node Story, if and only if its floor number is not equal to the number of stories of the building. Intuitively, a cardinality constraint for and edge e will have to hold for each instance of the parent node P in e, such that P has ancestors connected with it through paths matching with M etaP aths occurring in the constraint. As mentioned, a product description consists of a product model together with a set of global constraints. Such constraints, called model constraints, involve variables of nodes not necessary related by has-part relations (node model constraints) as well as cardinalities of different edges exiting from a node (cardinality model constraints). Also, global constraints like alldifferent [27] and aggregation constraints can be used to define node model constraints. Intuitively, a node model constraint will have to hold for all the tuples of node instances reached by paths matching with M etaP aths occurring in the constraint. The following is an example of cardinality model constraint: hupper story, Story, Story, Cardi = 6 hroof, Story, Roof, Cardi. This constraint states that, given an instance of the node Story the cardinality of the edge upper story and roof exiting from it must be different, i.e., an instance of the node Story can not have both an upper story and a roof. 2.2 Process Description P ROD P ROC allows one to model a process in terms of activities and temporal relations between them. Moreover, P ROD P ROC makes it possible to model process resource pro- duction and consumption, and to intermix the product and the process modeling phases. In general, a process consists of: a set of activities; a set of variables (as before, endowed with a finite domain of strings or of integers) representing process character- istics and involved resources; a set of temporal constraints between activities; a set of resource constraints; a set of constraints on activity durations. There are three kinds of activity: atomic activities, composite activities, and multiple instance activities. An atomic activity A is an event that happens in a time interval. It has associated a name and the following parameters: • two integer decision variables, tstart and tend , denoting the start time and end time of the activity. They define the time interval [tstart , tend ], subject to the implicit requirement that tend ≥ tstart ≥ 0. • a decision variable d = tend − tstart denoting the duration of the activity. • a flag exec ∈ {0, 1}. When d = 0 we say that A is an instantaneous activity. If exec = 1 holds, A is executed, otherwise (namely, if exec = 0) A is not executed. A composite activity is an event described in terms of a process. Hence, it has associated four variables analogously to an atomic activity, as explained earlier. Moreover, it is associated with a model of the process it represents. A multiple instance (atomic or composite) activity is an event that may occur multiple times. Together with the four variables (and possibly the sub-process model), a multiple instance activity has associated a decision variables (named inst) representing the number of times the activity can be executed. Temporal constraints between activities are inductively defined starting from atomic temporal constraints. Let A and B be to activities. We consider as atomic temporal constraints all the thirteen mutually exclusive binary relations which capture all the possible ways in which two intervals might overlap or not (as introduced by Allen in [3]), and some further constraints inspired by the constraint templates of the language ConDec [19]. The following are some examples of atomic temporal constraints (for lack of space we avoid listing all the possibilities): 1. A bef ore B to express that A is executed before B. Preparation and Building shell and Building services development of the building envelope equipment Finishing works building site before works before before or or or meets meets meets Fig. 2. Temporal constraint network for the building construction process. 2. A meets B to express that the execution of A ends at time point in which the execution of B starts. 3. A must−be−executed to express that A must be executed. 4. A is−absent to express that A can never be executed. 5. A not−co−existent−with B to express that either A or B can be executed (i.e., it is not possible to execute both A and B). 6. A succeeded−by B to express that when A is executed than B has to be executed after A. The constraints 1 and 2 are two of the binary relations of [3]. The constraints 3–6 have been inspired by the templates used in the language ConDec [19]. A temporal constraint is inductively defined as follows. • An atomic temporal constraint is a constraint. • If ϕ and ϑ are temporal constraint then ϕ and ϑ and ϕ or ϑ are temporal constraints. • If ϕ is a temporal constraint and c is a constraint on process variables, then c → ϕ is an if-conditional temporal constraint, stating that ϕ has to hold whenever c holds. Also, c ↔ ϕ is an iff-conditional temporal constraint, stating that ϕ has to hold if and only if c holds. Plainly, the truth of the atomic temporal constraints is related with the execution of the activities they involve. For instance, whenever for two activities A and B it holds that execA = 1 ∧ execB = 1, then the atomic formulas of the forms 1 and 2 must hold. A temporal constraint network CN is a pair hA, Ci, where A is a set of activities and C is a set of temporal constraints on activities in A. Fig. 2 shows the temporal constraint network for the building construction process. Fig. 3 shows the temporal constraint network for the sub-process represented by the composite activity called “Building ser- vices equipment”. In the figures, atomic activities are depicted as rectangles, composite activities as nested rectangles, multiple instance activities as overlapped rectangles. Bi- nary temporal constraints are represented as edges whose labels describe the temporal relations. If an activity is involved in a must be executed or in a is absent constraint, it is depicted as a dashed line rectangle or a dotted line rectangle, respectively. A con- ditional temporal constraints is depicted together with its activation condition. P ROD P ROC allows one to specify constraints on resource amounts [15] and activity durations. A resource constraint is a quadruple hA, R, q, T Ei, where A is an activity; R is an variable endowed with a finite integer domain; q is an integer or a variable en- dowed with a finite integer domain, defining the quantity of resource R consumed (if q < 0) or produced (if q > 0) by executing A; T E is a time extent that defines the time interval where the availability of resource R is affected by the execution of ac- tivity A. The possibilities for T E are: F romStartT oEnd, Af terStart, Af terEnd, Bef oreStart, Bef oreEnd, Always, with the obvious meaning. The following is an Roof insulation before before before or or or meets meets meets Ventilation rough Heating rough Sanitary rough assembly assembly assembly San = 1 Heat = 1 Vent = 1 succeeded_by succeeded_by succeeded_by Insulation heating, Pressure test sanitary, ventilation succeeded_by sanitary, heating Fig. 3. Temporal constraint network for the composite activity “Building services equipment”. example of resource constraints for the third phase of the building construction process. hRoof insulation, GeneralW orkers, hqGW , [−10, −4]i, F romStartT oEndi. This constraint specifies that the number of GeneralW orkers available is reduced of an amount between 4 and 10 during the execution of the activity Roof insulation. All the workers will return available as soon as the activity ends. Note that resource constraints may (implicitly) imply constraints on the number of instances of multiple instance ac- tivities. Another form of resource constraints establishes initial level constraints, i.e., expressions defining the quantity of a resource available at the time origin of a process. The basic form is initialLevel(R, iv), where R is a resource and iv ∈ N. An activity duration constraint has the form hA, Constrainti, where A is the name of an activity, and Constraint may involve the duration of A, process variables, and quantity variables for resource related to A. This is an example of activity duration con- straint for the third phase of the building construction process (where BuildingArea is a process variable, and qT , qC are quantity variables): BuildingArea Roof insulation, d = . 2 · |qGW | + 2 · |qT | + 3 · |qC | P ROD P ROC also allows one to couple elements for modeling a process and elements for modeling a product through constraints involving process variables and product variables. The following are examples in our sample model: hBuilding, sanitary, Cardi = San , hStoryN um, Building, []i = instF inishing works . For instance, the last one states that the number of stories of a building has to be equal to the value of instF inishing works (i.e., number of times the event F inishing works is executed). In general, constraints involving both product and process variables may help to detect/avoid planning impossibilities due to product configuration, and configuration impossibilities due to product configuration, during the configuration of a product. 2.3 P ROD P ROC Instances A P ROD P ROC model represents the collection of single (producible) variants of a con- figurable product and the processes to produce them. A P ROD P ROC instance represent one of such variant and its production process. To precisely define this notion we need to introduce first the notion of candidate instance. A P ROD P ROC candidate instance consists of the following components: • A set N of node instances, i.e., tuples of the form n = hN, i, VN i where N is a node in the product model graph, i ∈ N is an index (different for each instance of a node), VN is the set of variables of node N . • a set ANodes of assignments for all the node instance variables, i.e., expressions of the form V = value where V is a variable of node instance n and value belongs to the set of values for V . • A tree, called instance tree, that specifies the pairs of node instances in the relation has-part. Such a tree is defined as IT = hN , Ei, where E is a set of tuples f = hlabel, n, mi such that there exists an edge e = hlabel, N, M, Card, CCi in the product model graph, n is an instance of N and m is an instance of M . • A set ACards of assignments for all the instance cardinality variables, i.e., expres- sions of the form ICne = k where n is an instance of a node N , e is a quin- tuple hlabel, N, M, Card, CCi, ICne ≡ Card, and k is the number of the edges hlabel, n, mi, such that m is an instance of M , in the instance tree. • A set A of activity instances, i.e., pairs a = hA, ii where A is the name of an activity such that execA = 1 and i ∈ N is a unique id for instances of A. • A set E of flags execA , one for each activity A such that execA 6= 1. • A set AProc of assignments for all model variables and activity parameters (i.e., time instant variables, duration variables, execution flags, quantity resource variables, instance number variables), that is, expressions of the form P = value where P is a model variable or an activity parameter, and value ∈ Z or value belongs to the set of values for P . A P ROD P ROC instance is a candidate instance such that the assignments in ANodes ∪ ACards ∪ AP roc satisfy all the constraints in the P ROD P ROC model (node constraints, edges constraints, temporal constraints, resource constraints, etc.), appropriately instan- tiated with variables of node instances and activity instances in the candidate instance. The (constraint) instantiation mechanism produces a set of constraints on candidate instance variables from each constraint in the P ROD P ROC model. A candidate instance must satisfy all these constraints to qualify as an instance. We give here an intuitive explanation of how the instantiation mechanism works on different constraint types. Let us begin with node and cardinality constraints. Let c be a constraint belonging to the node N , or a constraint for an edge e between nodes N and M . Let us suppose that N1 , . . . , Nk are ancestors of N whose variables are involved in c, and let p1 , . . . , pk be M etaP aths such that, for i = 1, . . . , k, pi is a M etaP ath from Ni to N . We define Lnode as the set of k-tuple of node instances hn, n1 , . . . , nk i where: n is an instance of N ; for i = 1, . . . , k ni is an instance of Ni , connected with n through a path qi in the instance tree such that match(qi , pi ) = true holds. match is defined as follows.1 1 Given two lists l1 and l2 , l1 ◦ l2 denotes their concatenation. We denote with [x|l] the list obtained by prepending the element x to the list l.   true  if q = p  match(ps, mps) if q = [label|ps] ∧ (p = [label|mps] ∨ p = [_|mps])  match(q, p) = true if p = [⋆, label|ps]∧    ∧ ∃s.(q = s ◦ [label|ps] ∧ match(ps, mps)) f alse otherwise  For each k-tuple t ∈ Lnode , we obtain a constraint on instance variables appropriately substituting variables in c with variables of node instances in t. If c is a constraint for e, given a k-tuple hn, n1 , . . . , nk i on which to instantiate it, the cardinality occurring in it is substituted with the cardinality variable ICne . Node model constraints are instantiated in a slightly different way. Let c be a node model constraint. Let us suppose that N1 , . . . , Nk are the nodes whose variables are in- volved in c, let p1 , . . . , pk be M etaP aths such that, for i = 1, . . . , k, pi is a M etaP ath that ends in Ni . We define Lnmc as the set of ordered k-tuples of node instances hn1 , . . . , nk i, where for i = 1, . . . , k ni is an instance of Ni connected by a path qi with one of its ancestors in the instance tree, such that match(qi , pi ) = true holds. For each k-tuple t ∈ Lnmc , we obtain a constraint on instance variables appropriately substituting variables in c with variables of node instances in t. If c is an aggregation or an alldifferent constraint, then we define an equivalent constraint on the list consisting of all the node instances of N1 , . . . , Nk reached by a path matching with the corresponding M etaP ath. The instantiation of cardinality model constraint is very simple. Let c be a cardi- nality model constraint for the cardinalities of the edges with labels e1 , . . . , ek exiting from a node N . Let n1 , . . . , nh be instances of N . For all i ∈ {1, . . . , h}, we instantiate c appropriately substituting the cardinality variables occurring in it, with the instance cardinality variables ICne11 , . . . , ICnekk . Let us now consider process constraints. Let A be an activity, let a1 , . . . , ak be instances of A. Let r be the resource constraint hA, R, q, T Ei, we instantiate it on each instance of A, i.e., we obtain a constraint hai , R, qi , T Ei for each i = 1, . . . , k, where qi = q is a fresh variable. Let c be an activity duration constraint for A, for each i = 1, . . . , k we obtain a constraint substituting in c dA with dai , and each quantity variable q with the corresponding variable qi . Finally, let B an activity, let b1 , . . . , bh be instances of B. If c is a temporal constraint involving A and B, we obtain a constraint on activity instances for each ordered couple hi, ji, with i ∈ {1, . . . , k}, j ∈ {1, . . . , h}, substituting in c each occurrence of A with ai , and of B with bj . This mechanism can be easily extended to temporal constraints involving more than two activities. 3 Product and Process Configuration On top of the framework we described in Sect. 2 it is possible to implement a configu- ration system based on Constraint Logic Programming (CLP) [13]. In this section, we first explain how such a system can support a user through the configuration of a prod- uct and its production process. Then, we show how we can generate a CLP program from a model and a (partial) candidate instance. CLP-based configuration system (1) Initialization (2) Choice (5) CLP information (3) Change information program Finite System System domain interface engine (4) Start inference solver (8) Choice (6) Results consequences process User (7) Inference process results Fig. 4. Configuration process supported by a CLP-based system. A possible general structure of a configuration process supported by a CLP-based system is pictorially described in Fig. 4. First, the user initializes the system (1) se- lecting the model of the product/process to be configured. After such an initialization phase the user starts to make her/his choices by using the system interface (2). The in- terface communicates to the system engine (i.e., the piece of software that maintains a representation of the product/process under configuration, and checks the validity and consistency of user’s choices) each data variation specified by the user (3). The system engine updates the current partial configuration accordingly. Whenever an update of the partial configuration takes place, the user, through the system interface, can activate the engine inference process (4). The engine instantiates P ROD P ROC constraints on the current (partial) candidate instance, and encodes the product/process configuration problem in a CLP program (encoding a Constraint Satisfaction Problem, abbreviated to CSP). Then, it uses a finite domain solver to propagate the logical effects of user’s choices (5). Once the inference process ends (6), the engine returns to the interface the results of its computation (7). In its turns, the system interface communicates to the user the consequences of her/his choices on the (partial) configuration (8). In the following, we briefly explain how it is possible to obtain a CLP program from a P ROD P ROC model and a (partial) candidate instance (a candidate instance is partial when there are variables with no value assigned to) corresponding to it. We do this considering only the process side of a model, the operations necessary to obtain CLP variables and constraints for the product side are similar. Given a P ROD P ROC model and a corresponding (partial) candidate instance defined by a user, we can easily obtain a CSP hVAR, DOM, CON ST Ri, where VAR is a set of variables, DOM is a set of finite domain for variables in VAR, and CON ST R is a set of constraints on variables in VAR. VAR will contain a variable for each node in- stance variable, cardinality variable, activity parameter, process characteristic, resource, and quantity resource variable. DOM will contain a domain, obtained form the P ROD - P ROC model, for each variable in V. CON ST R will contain all the constraints that the (partial) candidate instance should satisfy. As we explained in Sect. 2.3, such con- straints are determined by an instantiation mechanism. We give here a formalization of such mechanism for the process side of a model. We define a function µ that, given the set of activity instances A, the set RDC = R ∪ D ∪ C, where R is the set of resource constraints, D is the set of activity duration constraints, C is the set of temporal con- straints, generates a set of constraints instantiated on activity instances. To define µ we preliminary need to introduce some basic notions. If c is a temporal constraint acts(c) is the list of activities involved in c. In the following we will denote with a an instance of an activity, and with pInsts(a) the set of instances of the process associated to a composite activity instance a. We say that a ↔Act A if and only if a is an instance of A. The function µ is defined as follows: S S µ(A, RCP, I) = a∈A α(a) ∪ c∈RCP γ(c, A). The function α generates the set of default constraints on duration, start time, and fin- ishing time for an activity instance a:  Comp t (a) if a is a composite activity instance α(a) = , t(a) otherwise tComp (a) = {tstart a = minb∈pInsts(a) tstartb , tend a = maxb∈pInsts(a) tend b , tend a ≥ t start a , d a = t end a − t start a , exec A = 1}, t(a) = {tstart a ≥ 0, tend a ≥ tstart a , da = tend a − tstart a , execA = 1}. The function γ instantiate a constraint c on activity instances in A.   {ha, R, qa , T Ei|a ∈ A∧  if c ∈ R∧    ∧ a ↔Act A ∧ qa = qA } ∧ c ≡ hA, R, qA , T Ei      c if c ∈ R∧ ∧ c ≡ initialLevel(R, iv)  γ(c, A)=    {c[dA /da , qA /qa ] | a ∈ A ∧ a ↔Act A} if c ∈ D {c[A1 /a1 , . . . , Ak /ak ] | if c ∈ C        [A1 , . . . , Ak ] = acts(c)∧ ∧ [a1 , . . . , ak ] ∈ Lact (c, [A1 , . . . , Ak ], A)}  The function Lact (c, [A1 , . . . , Ak ], A) generates all the k-tuple of activity instances that are instances of activities involved in a constraint V c: k Lact (c, [A1 , . . . , Ak ], A) = {[a1 , . . . , ak ] | j=1 (aj ∈ A ∧ aj ↔Act Aj )} From instantiated resource constraints and CSP variables for resources it is possi- ble to generate a cumulative constraint [1,4]. To obtain CSP constraints from all other constraints it is sufficient to substitute the instance variables with the corresponding CSP variables. Temporal constraints are defined on activities, but it is possible to com- pile them into propositional formulas on activity durations, starting times, and finishing times. Table 1 shows the translation for some of the atomic temporal constraints. Let ϕ and ϑ be temporal constraints, let ϕP and ϑP the corresponding propositional formulas. Then ϕ and ϑ, ϕ or ϑ, c → ϕ and c ↔ ϕ correspond to ϕP ∧ ϑP , ϕP ∨ ϑP , c ⇒ ϕP and c ⇔ ϕP , respectively. Given the constraint satisfaction problem CSP it is straightforward to obtain a CLP program encoding it, once a specific CLP system has been chosen, e.g., SICStus Prolog, SWI Prolog, or ECLiPse. 4 A Comparison with Existing Product/Process Modeling Tools In this section, we briefly compare the P ROD P ROC framework with some of the most important product configuration systems and process modeling tools to put in evidence its strength and limitations. Atomic temporal constraint Propositional formula A bef ore B tstart A < tstart B ∧ tend A < tstart B start start A meets B tA < tB end ∧ tA = tstart B A must−be−executed execA = 1 A is − absent execA = 0 A not−co−existent−with B execA + execB ≤ 1 A succeeded−by B execA = 1 ⇒ execB = 1 ∧ tstartB ≥ tend A Table 1. Atomic temporal constraints and corresponding propositional formulas. Product configuration systems based on Answer Set Programming (ASP) [11], e.g., Kumbang Configurator [16], provide a number of features that are specifically tailored to the modeling of software product families. On the one hand, this makes these systems appealing for a relevant range of application domains. On the other hand, it results in a lack of generality, which is probably the major drawback of this class of systems. In particular, they do not support global constraints, and they encounter some problems in the management of arithmetic constraints related to the so called grounding stage [16]. Systems based on binary decision diagrams (BDDs) for product configuration, e.g., Configit Product Modeler [8], trade the complexity of the construction of the BDD, that basically provides an encoding of all possible configurations [12], for the simplicity and efficiency of the configuration process. Despite their various appealing features, BDD- based systems suffer from some significant limitations. First, even though some work has been done on the introduction of modules [25,26], they basically support flat models only. Moreover, they find it difficult to cope with global constraints. Some attempts at combining BDD with CSP to tackle alldifferent constraints have been recently done [17]; however, they are confined to the case of flat models. We are not aware of any BDD system that deals with global constraints in a general and satisfactory way. Unlike ASP-based and BDD-based product configuration systems, CSP-based sys- tems allow the user to define non-flat models and to deal with global constraints. Unfor- tunately, the modeling expressiveness of CSP-based systems has a cost, i.e., backtrack- free configuration algorithms for CSP-based systems are often inefficient, while non backtrack-free ones need to explicitly deal with dead ends. Some well-known CSP- based configuration systems, such as ILOG Configurator [14] and Lava [10], seem to be no longer supported. A recent CSP-based configuration system is Morphos Config- uration Engine (MCE) [7]. From the point of view of process modeling, P ROD P ROC can be viewed as an extension of the MCE modeling language. In particular, it extends MCE modeling language with the following features: (1) cardinality variables, i.e., has-part/is-part-of relations can have non-fixed cardinalities; (2) product model graph, i.e., nodes and relations can define a graph, not only a tree; (3) cardinality constraints and cardinality model constraints, i.e., constraints can involve cardinalities of relations; (4) M etaP aths, i.e., a mechanism to refer node instance variables in constraints. In [22] the authors present an ontology representing a synthesis of resource-based, connection-based, function-based and structure-based product configuration approches. The P ROD P ROC framework covers only a subset of these concepts. However, it is not limited to product modeling and it defines a rich (numeric) constraint language, while it remains unclear to what extent the language used in [22] supports the formulation of configuration-domain specific constraints. P ROD P ROC can be viewed as the source code representation of a configuration sys- tem with respect to the MDA abstraction levels presented in [9]. P ROD P ROC product modeling elements can be mapped to UML/OCL in order to obtain platform specific (PSM) and platform independent (PIM) models. The mapping to OCL of M etaP aths containing ‘⋆’ wildcards and of model constraints requires some attention. For example, the latter do not have an explicit context as OCL constraint must have. In the past years, different formalisms have been proposed for process modeling. Among them we have: the Business Process Modeling Notation (BPMN) [28], Yet Another Workflow Language (YAWL) [24], DECLARE [19]. Languages like BPMN and YAWL model a process as a detailed specification of step-by-step procedures that should be followed during the execution. They adopt an imperative approach in process modeling, i.e., all possibilities have to be entered into their models by specifying their control-flows. BPMN has been developed under the coordination of the Object Man- agement Group. P ROD P ROC has in common with BPMN the notion of atomic activity, sub-process, and multiple instance activity. The effect of BPMN joins and splits on the process flow can be obtained by using temporal constraints. In P ROD P ROC there are no notions such as BPMN events, exception flows, and message flows. However, events can be modeled as instantaneous activities and data flowing between activities can be modeled with model variables. YAWL is a process modeling language whose intent is to directly supported all control flow patterns. P ROD P ROC has in common with YAWL the notion of task, multiple instance task, and composite task. YAWL join and split constructs are not present in P ROD P ROC, but using temporal constraints it is possible to obtain the same expressivity. As opposed to traditional imperative approaches to pro- cess modeling, DECLARE uses a constraint-based declarative approach. DECLARE models rely on constraints to implicitly determine the possible ordering of activities (any order that does not violate constraints is allowed). With respect to DECLARE, P ROD P ROC has in common the notion of activity and the use of temporal constraints to define the control flow of a process. The set of atomic temporal constraints is not as big as the set of template constraints available in DECLARE, however it is possible to easily combine the available ones so as to define all complex constraints of practical in- terest. Moreover, in P ROD P ROC it is possible to define multiple instance and composite activities, features that are not available in DECLARE. From the point of view of process modeling, P ROD P ROC combines modeling fea- tures of languages like BPMN and YAWL, with a declarative approach for control flow definition. Moreover, it presents features that, to the best of our knowledge, are not presents in other existing process modeling languages. These are: resource variables and resource constraints, activity duration constraints, and product related constraints. Thanks to these features, P ROD P ROC is suitable for modeling production processes and, in particular, to model mixed scheduling and planning problems related to production processes. Furthermore, a P ROD P ROC model does not only represent a process ready to be executed as a YAWL (or DECLARE) model does, it also allows one to describe a configurable process. Existing works on process configuration, e.g., [20], define process models with variation points, and aim at deriving different process model variants from a given model. Instead, we are interested in obtaining process instances, i.e., solutions to the scheduling/planning problem described by a P ROD P ROC model. The P ROD P ROC framework allows one to model products, their production pro- cesses, and to couple products with processes using constraints. The only works on the coupling of product and process modeling and configuration we are aware of are the ones by Aldanondo et al. [2]. They propose to consider simultaneously product config- uration and process planning problems as two constraint satisfaction problems; in order to propagate decision consequences between the two problems, they suggest to link the two constraint based models using coupling constraints. The development of P ROD - P ROC has been inspired by the papers of Aldanondo et al., in fact we have separated models for products and processes and, constraints for coupling them too. However, our modeling language is far more complex and expressive than the one presented in [2]. 5 Conclusions In this paper we focused on the problem of product and process modeling and con- figuration. In particular, we pointed out the lack of a tool covering both physical and production aspects of configurable products. To overcome this absence, we proposed a framework called P ROD P ROC, that allows one to model a configurable products and its production process. Moreover, we showed how it is possible to build a CLP-based configuration systems on top of this framework, and compared it to existing product configuration systems and process modeling tools. We have already implemented a first prototype of a CLP-based configuration system that uses P ROD P ROC. It covers only product modeling and configuration, but we are working to add to it process modeling and configuration capabilities. P RO P ROC and SysML [18] have various commonalities in terms of modeling features, despite the fact that their purposes are different. We plan to further investigate the relations that exists between the two modeling languages. We also plan to experiment our configuration system on different real-world application domains, and to compare it with commercial products, e.g., [5]. References 1. A. Aggoun and N. Beldiceanu. Extending chip in order to solve complex scheduling and placement problems. Mathematical and Computer Modelling, 17\ (7\ ):57–73, 1993. 2. M. Aldanondo and E. Vareilles. Configuration for mass customization: how to extend product configuration towards requirements and process configuration. J. of Intelligent Manufactur- ing, 19\ (5\ ):521–535, 2008. 3. J. F. Allen. Maintaining knowledge about temporal intervals. Commun. ACM, 26:832–843, 1983. 4. N. Beldiceanu and M. Carlsson. A New Multi-resource cumulatives Constraint with Nega- tive Heights. In P. Van Hentenryck, editor, CP 2002, volume 2470 of LNCS, pages 63–79. Springer Berlin / Heidelberg, 2006. 5. U. Blumöhr, M. Münch, and M. Ukalovic. Variant Configuration with SAP. SAP Press, 2009. 6. D. Campagna. A Graphical Framework for Supporting Mass Customization. In Proc. of the IJCAI’11 Workshop on Configuration, pages 1–8, 2011. 7. D. Campagna, C. D. Rosa, A. Dovier, A. Montanari, and C. Piazza. Morphos Configuration Engine: the Core of a Commercial Configuration System in CLP(FD). Fundam. Inform., 105\ (1-2\ ):105–133, 2010. 8. Configit A/S. Configit Product Modeler. http://www.configit.com. 9. A. Felfernig. Standardized Configuration Knowledge Representations as Technological Foundation for Mass Customization. IEEE Trans. on Engineering Management, 54\ (1\ ):41– 56, 2007. 10. G. Fleischanderl, G. Friedrich, A. Haselböck, H. Schreiner, and M. Stumptner. Config- uring Large Systems Using Generative Constraint Satisfaction. IEEE Intelligent Systems, 13\ (4\ ):59–68, 1998. 11. M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. In ICLP/SLP, pages 1070–1080, 1988. 12. T. Hadzic, S. Subbarayan, R. M. Jensen, H. R. Andersen, J. Moller, and H. Hulgaard. Fast backtrack-free product configuration using a precompiled solution space representation. In Proc. of the International Conference on Economic, Technical and Organizational Aspects of Product Configuration Systems, pages 131–138. 2004. 13. J. Jaffar and M. J. Maher. Constraint logic programming: A survey. J. Log. Program., 19/20:503–581, 1994. 14. U. Junker. The Logic of ILOG (J\ )Configurator: Combining Constraint Programming with a Description Logic. In Proc. of the IJCAI’03 Workshop on Configuration, pages 13–20. 2003. 15. P. Laborie. Algorithms for propagating resource constraints in AI planning and scheduling: existing approaches and new results. Artif. Intell., 143:151–188, February 2003. 16. V. Myllärniemi, T. Asikainen, T. Männistö, and T. Soininen. Kumbang configurator - a configurator tool for software product families. In Proc. of the IJCAI’05 Workshop on Con- figuration, pages 51–56. 2005. 17. A. H. Nørgaard, M. R. Boysen, R. M. Jensen, and P. Tiedemann. Combining Binary De- cision Diagrams and Backtracking Search for Scalable Backtrack-Free Interactive Product Configuration. In Proc. of the IJCAI’09 Workshop on Configuration, 2009. 18. OMG. OMG Systems Modeling Language. http://www.omgsysml.org. 19. M. Pesic, H. Schonenberg, and W. van der Aalst. DECLARE: Full support for loosely- structured processes. In EDOC’07, pages 287–287, 2007. 20. M. L. Rosa. Managing Variability in Process-Aware Information Systems. PhD thesis, Queensland University of Technology, Brisbane, Australia, 2009. 21. D. Sabin and R. Weigel. Product configuration frameworks-a survey. IEEE Intelligent Sys- tems, 13:42–49, 1998. 22. T. Soininen, J. Tiihonen, T. Männistö, and R. Sulonen. Towards a general ontology of con- figuration. Artif. Intell. Eng. Des. Anal. Manuf., 12:357–372, September 1998. 23. H. Sommer. Project Management for Building Construction. Springer, 2010. 24. A. H. M. ter Hofstede, W. van der Aalst, M. Adams, and N. Russell. Modern Business Process Automation - YAWL and its Support Environment. Springer, 2010. 25. E. R. van der Meer and H. R. Andersen. BDD-based Recursive and Conditional Modular Interactive Product Configuration. In Proc. of Workshop on CSP Techniques with Immediate Application (CP’04), pages 112–126, 2004. 26. E. R. van der Meer, A. Wasowski, and H. R. Andersen. Efficient interactive configuration of unbounded modular systems. In Proc. of the 2006 ACM symposium on Applied computing, SAC ’06, pages 409–414. ACM, 2006. 27. W. J. van Hoeve. The alldifferent Constraint: A Survey, 2001. 28. S. A. White and D. Miers. BPMN modeling and reference guide: understanding and using BPMN. Lighthouse Point, 2008. A Model Instantiation and CSP creation In this section, exploiting the building model introduced in Sect. 2, we show an ex- ample of P ROD P ROC partial candidate instance, and describe the CSP we obtain from it. The purpose of the example is twofold: first, to show how multiple instances of a node affect the constraint instantiation and the CSP corresponding to a model instance; second, to better describe the encoding of the process description into a CSP, in partic- ular the generation of a cumulative constraint from resources and instantiated resource constraints. Fig. 5 shows the instance tree of the partial candidate instance we consider. It con- sists of one instance of the root node (i.e., the node Building) of the product model graph depicted in Fig. 1, one instance of the node Electr./Light. service, two instances of the node Story, and one instance of the node Roof. Building, ID 1 electr./light. first story Electr./Light. Story, ID 1 service, ID 1 upper story Story, ID 2 roof Roof, ID 1 Fig. 5. Instance tree of a building partial candidate instance. The activity instances and the instantiated temporal constraints of the construction process for the building instance showed in Fig. 5 are depicted in Fig. 6. In the following we will denote as hV ar, N ode-ii the variable V ar of the instance with id i of the node N ode. Since we are considering a partial candidate instance, some of the node instance variables and process variables may have a value assigned to. For example, we may have hStoryN um, Building-1i = 2 and San = 0. As mentioned in Sect. 2.3, a candidate instance is an instance if it satisfies all the constraints defined in the model, appropriately instantiated on instance variables. The instantiation of the node constraints for the nodes Building and Story listed in Sect. 2.1 leads to the following constraints on the variables of node instances in Fig.5. before or Finishing works, meets ID = 1 Preparation and Building shell and Building services development of the building envelope equipment, ID = 1 building site, ID = 1 before works, ID = 1 before or or meets meets before Finishing works, or ID = 2 meets Roof insulation, ID = 1 Fig. 6. Activities and temporal constraints for the building partial candidate instance. hBuildingT ype, Building-1i = Warehouse ⇒ hStoryN um, Building-1i = 1, hF loorN um, Story-1i ≤ hStoryN um, Building-1i, hBuildingT ype, Building-1i = Office building ⇒ ⇒ hHeight, Story-1i ≥ 4 ∧ hHeight, Story-1i ≤ 5, hF loorN um, Story-2i = hF loorN um, Story-1i + 1, hF loorN um, Story-2i ≤ hStoryN um, Building-1i, hBuildingT ype, Building-1i = Office building ⇒ ⇒ hHeight, Story-2i ≥ 4 ∧ hHeight, Story-2i ≤ 5. Instantiating the cardinality constraints for the edge upper story, introduced in Sect 2.1, we obtain: upper story hF loorN um, Story-1i = hStoryN um, Building-1i ⇒ ICStory -1 = 0, upper story hF loorN um, Story-1i < hStoryN um, Building-1i ⇒ ICStory -1 = 1, upper story hF loorN um, Story-2i = hStoryN um, Building-1i ⇒ ICStory -2 = 0, upper story hF loorN um, Story-2i < hStoryN um, Building-1i ⇒ ICStory -2 = 1. Finally, the instantiation of the cardinality model constraint showed in Sect. 2.1 leads to the constraint: upper story roof ICStory -2 6= ICStory -2 . For each activity instance we have constraints on duration, starting and finishing time. For example, for the composite activity instance “Finishing works” with id 1 we have: tstart Finishing works-1 = minb∈pInsts(Finishing works-1) tb start , end tFinishing works-1 = maxb∈pInsts(Finishing works-1) tendb , tend start Finishing works-1 ≥ tFinishing works-1 , dFinishing works-1 = tend start Finishing works-1 − tFinishing works-1 . While for the activity instance “Roof insulation” with id 1 we have: tstart end Roof insulation-1 ≥ 0, tRoof insulation-1 ≥ 0, end start tRoof insulation-1 ≥ tRoof insulation-1 , dRoof insulation-1 = tend start Roof insulation-1 − tRoof insulation-1 . Instantiating the resource and duration constraints for the activity Roof insulation intro- duced in Sect. 2.2 we obtain: hRoof insulation-1, GeneralW orkers, hqGW , [−10, −4]i, F romStartT oEndi, BuildingArea Roof insulation-1, d = . 2 · |qGW | + 2 · |qT | + 3 · |qC | The instantiation of the constraint involving both product and process variables showed in Sect. 2.2 leads to the following constraints: sanitary ICBuilding -1 = San , hStoryN um, Building-1i = instF inishing works . From the P ROD P ROC partial candidate instance we just described and its instanti- ated constraints, we can construct a CSP with the following characteristics (we use the SWI-Prolog notation for variables, domains and constraints). – A finite domain (FD) variable for each node instance variable, e.g., for the variable hStoryN um, Building-1i the FD variable StoryNum_Building_1; roof – A FD variable for each instance cardinality variable, e.g, for ICStory -2 the FD variable IC_roof_Story_2; – FD variables for starting time, ending time, duration of each activity instance, e.g., T_start_Roof_insulation_1, T_end_Roof_insulation_1, and D_Roof_insulation_1 for the activity instance “Roof insulation” with id 1; – FD variables for execution flags of activities with no instance; – FD variables for process and resource variables, e.g., BuildingArea for the process variable BuildingArea, GeneralWorkers for the resource variable GeneralW orkers; – A domain constraint for each FD variable, e.g., IC_roof_Story_2 in 0..1; – A constraint on an FD variable for each assignments, obtained by substituting each instance variable with the corresponding FD variable; – A constraint on FD variables for each instantiated constraint, obtained by substitut- ing each instance variable with the corresponding FD variable; – For each composite activity instance, a minimum and a maximum constraint on start and end times, e.g., for the instance with id 1 of the activity “Finishing works” the constraint minimum(T_start_Finishing_works_1,Ts) and the con- straint maximum(T_end_Finishing_works_1,Te), where Ts, Te are re- spectively the list of start and end times of the activity in the process related to the instance with id 1 of “Finishing works”; – A constraint on FD variables for each instantiated temporal constraint, obtained by substituting start times, end times, and execution flags with the corresponding FD variables in the propositional formula equivalent to the temporal constraint; – A constraint on FD variables for each instantiated duration constraint, obtained by substituting duration, process and resource variables with the corresponding FD variables; – A constraint of the form cumulatives(Tasks,Machines) where Tasks is a list of task predicates, one for each instantiated resource constraint, and Machines is a list of machine predicates, one for each resource. For example, for the resource constraint showed in Sect. 2.2 and the resource GeneralW orkers we define the predicates task(T_start_Roof_insulation_1,D_Roof_insulation_1, T_end_Roof_insulation_1,Q_GW,GeneralWorkers, FromStartToEnd) machine(GeneralWorkers,0..10,10) B CLP-based Configuration System We are using SWI-Prolog to develop a CLP-based configuration system that exploits the close relation that exists between configuration problems and CSPs.2 In particular, we are using the SWI-Prolog pce library to implement the system graphical user in- terface, and the clpfd library for constraint propagation and labeling purposes. The current version of the system is limited to product modeling. Fig. 7 shows the graphical user interface that allows a user to define a product description using P ROD P ROC. The interface presents (on the left, from top to bottom) controls for graphical element se- lection, creation of nodes, creation of edges, and creation of sets of model constraints. Moreover, there is a menu named “Check” with controls for checking model syntactic correctness, and for automatically generate product instances to check model validity. Fig. 7. Graphical user interface for product description creation and checking. 2 We chose CLP instead of Constraint Programming for the advantages the former gives in terms of rapid software prototyping.