A Graphical Framework for Supporting Mass Customization ∗ Dario Campagna Dept. of Mathematics and Computer Science University of Perugia, Italy dario.campagna@dmi.unipg.it Abstract Inspired by the works of Aldanondo et al. (see, e.g., [Al- danondo and Vareilles, 2008]), we devised a graphical frame- Many companies deploying mass customization work for modeling configurable products, whose producible strategies adopt product configuration systems to variants can be represented as trees, and their production pro- support their activities. While such systems focus cesses. The intent of our framework is to allow the propa- mainly on configuration process support, mass cus- gation of consequences of product configuration decision to- tomization needs to cover the management of the ward the planning of its production process, and the propaga- whole customizable product cycle. In this paper, tion of consequences of process planning decision toward the we describe a graphical modeling framework that product configuration. allows one to model both a product and its pro- The paper is organized as follows. First, we introduce our duction process. We first introduce our framework. framework in Sect. 2. Then, in Sect. 3 we show how a config- Then, we outline a possible implementation based uration system based on Constraint Logic Programming can on Constraint Logic Programming of such prod- be implemented on top of it. A comparison with some of the uct/process configuration system. A comparison existing product configuration systems and process modeling with some existing product configuration systems tools is outlined in Sect. 4. An assessment of the work done and process modeling tools concludes the paper. and of future research directions is given in Sect. 5. 1 Introduction 2 A Graphical Framework for Product/Process Modeling Product configuration systems are software of interest for companies deploying mass customization strategies, since In this section, we present the P ROD P ROC graphical frame- they can support them in the management of configuration work (cf. Sections 2.1 and 2.2). Moreover, we provide a processes. In the past years many research studies have been brief description of P ROD P ROC semantics in terms of model conducted on this topic (see, e.g., [Sabin and Weigel, 1998]), instances (Sect. 2.3). and different software product configurators have been pro- A P ROD P ROC model consists of a product description, a posed (see, e.g., [Fleischanderl et al., 1998; Junker, 2003; process description, and a set of constraints coupling the two. Configit A/S, 2009; Myllärniemi et al., 2005]). To better present the different modeling features offered by Process modeling tools, instead, allows one to effectively our framework, we will exploit a working example. In partic- deal with (business) process management. In general, they ular, we will consider a bicycle with its production process. allow the user to define a description of a process, and guide she/he through the process execution. Also within 2.1 Product Modeling Features this field it is possible to find tools and scientific works We are interested in modeling configurable products whose (see, e.g, [White and Miers, 2008; ter Hofstede et al., 2010; corresponding (producible) variants can be represented as Pesic et al., 2007]). trees. Nodes of these trees correspond to physical compo- Mass customization needs to cover the management of the nents, whose characteristics are all determined. The tree whole customizable product cycle, from product configura- structure describes how the single components taken together tion to product production. Current product configuration define a configured product. systems and researches on product configuration, focus only Hence, we model a configurable product as a multi-graph, on product modeling and on techniques for configuration pro- called product model graph, and a set of constraints. Nodes of cess support. They do not cover product production process the multi-graph represent well-defined components of a prod- problematics, despite the advantages that coupling of product uct (e.g., the frame of a bicycle). While edges model has- with process modeling and configuration could give. part/is-part-of relations between product components. We require the presence of a node without entering edges in the ∗ This work is partially supported by GNCS and MIUR projects. product model graph. We call this node root node. A prod- Frame Wheel uct model represents a configurable product. Its configura- Frame front wheel 1 Wheel tion can lead to the definition of different (producible) prod- variables variables Frame Wheel uct variants. constraints rear wheel 1 constraints Each node/component consists of a name, a set of variables ⟨Card,{0,1}⟩ rear gears modeling configurable characteristics of the component, and Gears Gear a set of constraints (called node constraints) involving vari- rear gears variables ables of the node and variables of its ancestors in the graph. constraints Gear constraints Each variable is endowed with a finite domain (typically, a finite set of integers or strings), i.e., the set of its possible val- Figure 2: Fragment of bicycle product model graph. ues. Constraints define compatibility relations between con- figurable characteristics of a node and of its ancestors. The graphical representation of a node (cf. Fig. 1) consists of a in ancestors of a node using meta-variables, i.e., triples of box with three sections, each containing one of the elements the form hV arN ame, AncestorN ame, M etaP athi. This constituting a node. writing denotes a variable V arN ame in an ancestor node AncestorN ame (e.g., F rameT ype in F rame). The third Node name Node name component of a meta-variable, M etaP ath, is a list of edge Node Edge label Node labels (see below) describing a path connecting the two nodes variables Card variables Node Cardinality Node in the graph (wildcards ‘ ’ and ‘?’ can be used to represent ar- constraints constraints constraints bitrary labels and a sequence of arbitrary labels respectively). M etaP aths are used to define constraints that will have ef- Figure 1: Graphical representation of nodes and edges. fect only on particular instances of a node. For example, the constraint (2) for the node W heel has to hold only for those In the description of a configured product, physical com- instances of node W heel which are connected to an instance ponents are represented as instances of nodes in the product of node F rame through an edge labeled rear wheel. In- model graph. An instance of a node N odeN ame consists tuitively, a node constraint for the node N has to hold for of the name N odeN ame, a unique id, and a set of variables each instance of N , such that it has ancestors connected with equals to the one of N odeN ame. Each variable has a value it through paths matching with the M etaP aths occurring in assigned. The root node will have only one instance, such the constraint. instance will be the root of the configured product tree. An edge e = hlabel, N, M, Card, CCi of the product Let us consider, for example, the node Frame of the (frag- model graph is characterized by: a name (label), two node ment of) product model graph for a bicycle, depicted in names denoting the parent (N ) and the child node (M ) in the Fig. 2.1 The section Frame variables may contain the fol- has-part relation, the cardinality (Card) of such relation (ex- lowing couples of variables and domains: pressed as either an integer number or an integer variable), and a set (CC) of constraints (called cardinality constraints). hF rameT ype, {Racing bike, Citybike}i, Such constraints may involve the cardinality variables (if any) hF rameM aterial, {Steel, Aluminum, Carbon}i. as well as variables of the parent node and of its ancestors (re- While in Frame constraints we may have the constraint ferred to by means of meta-variables). An edge is graphically represented by an arrow connecting the parent node to the F rameT ype = Racing ⇒ F rameM aterial 6= Steel. child node (cf. Fig. 1). Such an arrow is labeled with the This constraint states that a frame of type racing can not be edge name and cardinality, and may have attached an ellipse made of steel. An example of instance of F rame is the triple containing cardinality constraints. hF rame, 1, {F rameT ype = Racing, F rameM aterial = An instance of an edge labeled label connecting a node N Carbon}i. Note that values assigned to node instance vari- with a node M , is an edge connecting an instance of N and ables have to satisfy all the node constraints. For the node an instance of M . It is labeled label too. Wheel (that also appears in Fig. 2) we may have the variables Let us consider the edges front wheel and rear gear de- picted in Fig. 2. The former is the edge relating the frame hW heelT ype, {Racing bike, City bike}i, with the front wheel, its cardinality is imposed to be 1, and hSpokeN umber, [18, 28]i, there is no cardinality constraint. Hence, there must be (only) and the constraints one instance of the node Wheel connected to an instance of the node Frame through an edge labeled front wheel. The W heelT ype = hF rameT ype, F rame, [ ]i, (1) latter edge, rear gears, represents the has-part relation over hF rameT ype, F rame, [rear wheel]i = Racing bike ⇒ the frame and the rear gears of a bicycle. Its cardinality is ⇒ SpokeN umber > 20. a variable named Card, taking values in the domain {0, 1}. (2) Hence, we may have an instance of the node Gears connected These constraints involve features belonging to an ancestor of to an instance of the node Frame through an edge labeled rear the node Wheel, i.e., the node Frame. We refer to variables gears. Among the cardinality constraints of the edge rear 1 gears we may have the following one: The depicted product model graph is one of the possible graphs F rameT ype = Racing ⇒ Card = 1. we can define with our framework. We chose this one for presenta- tion purposes only. Intuitively, a cardinality constraint for and edge e has to hold for each instance of the parent node N in e, such that N Activity name has ancestors connected with it through paths matching with Activity name Activity name Activity Activity M etaP aths occurring in the constraint. Activity duration inst duration duration constraints As mentioned, we model a product as a graph and a set constraints constraints of constraints. Such constraints, called model constraints, (a) (b) (c) involve variables of nodes not necessary related by has- part relations (node model constraints), as well as cardi- Figure 3: Graphical representation of activities. nalities of different edges exiting from a node (cardinal- ity model constraints). Moreover, global constraints like alldifferent [van Hoeve, 2001] can be used to define usual parameters (and possibly the process model), a multi- node model constraints. In node model constraints, variables ple instance activity has associated an integer decision vari- are referred to by means meta-variables. A M etaP ath in a able (named inst) representing the number of times the ac- node model constraint represents a path connecting a node to tivity can be executed. Note that the execution/non-execution one of its ancestors in the graph. M etaP aths are used to of activities determines different instances of a configurable limit the effect of a node model constraint to particular tuples process. Figures 3a, 3b, and 3c, show the graphical represen- of node instances. An example of node model constraint for tation of atomic activities, composite activities, and multiple the bicycle is the following one: instance activities, respectively. Temporal constraints between activities are inductively de- hGearT ype, Gears, [rear gears]i = Special ⇒ (3) fined starting from atomic temporal constraints. We consider ⇒ hSpokeN umber, W heel, [rear wheel]i = 26. as atomic temporal constraints all the thirteen mutually exclu- This constraint states that if the type of rear gears chosen is sive relations on time intervals introduced by Allen in [Allen, “Special”, then the rear wheel must have 26 spokes. Intu- 1983] (they capture all the possible ways in which two in- itively, a node model constraint has to hold for all the tuples tervals might overlap or not), and some other constraints in- of node variables of node instances reached by paths match- spired by constraint templates of the language ConDec [Pesic ing with the M etaP aths occurring in the constraint. et al., 2007]. Some examples of atomic temporal constraints are listed as follows (for lack of space we avoid listing all 2.2 Process Modeling Features of them), where A and B are two activities. Fig. 4 shows Processes can be modeled in P ROD P ROC in terms of activi- their graphical representations (we used a slightly different ties and temporal relations between them. More precisely, a graphical notation for activities, i.e., we omitted the activity process is characterized by: a set of activities, a set of vari- duration constraint sections). ables (as before, endowed with a finite domain of strings or of 1. A bef ore B to express that A is executed before B (cf. integers) representing process characteristics and involved re- Fig. 4a); sources; a set of temporal constraints between activities; a set of resource constraints; a set of constraints involving product 2. A during B to express that A is executed during the elements; a set of constraints on activity durations. A process execution of B (cf. Fig. 4b); model does not represent a single production process. In- 3. A is−absent to express that A can never be executed stead, it represents a configurable production process, whose (cf. Fig. 4c); configuration can lead to the definition of different executable processes. 4. A must−be−executed to express that A must be exe- P ROD P ROC defines three kinds of activities: atomic activi- cuted (cf. Fig. 4d); ties, composite activities, and multiple instance activities. An 5. A not−co−existent−with B to express that it is not atomic activity A is an event occurring in a time interval. It possible to executed both A and B (cf. Fig. 4e); has associated a name and the following parameters. 6. A succeeded−by B to express that when A is executed • Two integer decision variables, tstart and tend , denoting then B has to be executed after A (cf. Fig. 4f). the start and end time of the activity. They define the tine interval [tstart , tend ], and are subject to the implicit The constraints 1 and 2 are two of the relations presented condition tend ≥ tstart ≥ 0. in [Allen, 1983]. The constraints 3-6 have been inspired by the templates used in ConDec [Pesic et al., 2007]. A temporal • A decision variables d = tend − tstart denoting the du- constraint is inductively defined as follows. ration of the activity. • An atomic temporal constraint is a constraint. • A flag exec ∈ {0, 1}. • If ϕ and ϑ are temporal constraint, then ϕ and ϑ and We say that A is an instantaneous activity if d = 0. A is ϕ or ϑ are temporal constraints. executed if exec = 1 holds, otherwise (i.e., if exec = 0) A is not executed. A composite activity is an event described • If ϕ is a temporal constraint and c is a constraint on pro- in terms of a process. It has associated the same parameters cess variables, then c → ϕ is an if-conditional temporal of an atomic activity, and a model of the process it repre- constraint, stating that ϕ has to hold whenever c holds. sents. A multiple instance (atomic or composite) activity is Also, c ↔ ϕ is an iff-conditional temporal constraint, an event that may occur multiple times. Together with the stating that ϕ has to hold if and only if c holds. A before B Resource constraints [Laborie, 2003] are quadruple hA, R, q, T Ei, where A is an activity; R is a variable en- (a) dowed with a finite integer domain; q is an integer or a variable endowed with a finite integer domain, defining during A B the quantity of resource R consumed (if q < 0) or pro- c duced (if q > 0) by executing A; T E is a time ex- (b) tent that defines the time interval where the availability of resource R is affected by A. The possible values for A A T E are: F romStartT oEnd, Af terStart, Af terEnd, c Bef oreStart, Bef oreEnd, Always, with the obvious (c) (d) meaning. Another form of resource constraint defines initial level constraints, i.e., expressions determining the quantity of A B a resource available at the time origin of a process. The ba- (e) sic form is initialLevel(R, iv), where R is a resource and iv ∈ N. Examples of resource constraints for the bicycle pro- A B duction process are: hWheel construction, Aluminum, −4, Af terStarti, (f) hFrame construction, W orkers, qW ∈ [−1, −2], F romStartT oEndi. before A B The first constraint states that activity “Wheel construction” during consumes 4 unit of aluminum once its execution starts. The (g) second constraints states that activity “Frame construction” needs 1 or 2 workers during its execution. As for tem- Figure 4: Graphical representation of temporal constraints. poral constraint, we can define if-conditional (i.e., c → hA, R, q, T Ei) and iff-conditional (i.e., c ↔ hA, R, q, T Ei) resource constraints. Their meaning are similar to the ones A conjunction of atomic constraints between two activities defined above for temporal constraints. can be depicted by representing each constraint of the con- An activity duration constraint for an activity A, is a con- junction. Fig. 4g shows the graphical representation for a straint involving the duration of A, process variables, and disjunction of atomic temporal constraints between two ac- quantity variables for resources related to A. The following tivities (i.e., for the constraint A bef ore B or A during B). is an example of an activity duration constraint for the ac- An if-conditional and an iff-conditional temporal constraint tivity “Frame construction” in the bicycle production process with condition c are depicted in Fig. 4b and 4c, respectively. (where F rameM ult is a process variable) Finally, a non-atomic temporal constraint can be depicted as d = 2·F rameM ult |qW | an hyper-edge connecting the activities involved in it, and la- beled with the constraint itself. P ROD P ROC also allows one to mix elements for model- ing a process with elements for modeling a product, through The truth of atomic temporal constraints is related with constraints involving process variables and product variables. the execution of the activities they involve. For instance, This is an example for the bicycle model whenever for two activities A and B it holds that execA = 1 ∧ execB = 1, then the atomic formulas of the forms 1 and hF rameT ype, F rame, []i = Racing ⇒ F rameM ult = 4. 2 must hold. A temporal constraint network CN is a pair It relates the variable F rameT ype of the node F rame with hA, Ci, where A is a set of activities and C is a set of tem- the process variable F rameM ult. Another example is the poral constraints on A. Fig. 5 shows the temporal constraint following: network of the bicycle production process. hrear gears, F rame, Gears, Cardi = Gears. This constraint relates the process variable Gears with the Construction of before before cardinality of the edge rear gears of the bicycle product bicycle Bicycle assembly Delivery components model graph. The cardinality is represented by the quadru- ple hrear gears, F rame, Gears, Cardi, where the first ele- ment is an edge label, the second one is the name of the parent before before Frame Partial assembly Handlebar node of the edge, the third one is the name of the child node construction construction of the edge, and the last one is the name of the cardinality. Gears = 0 Product related constraints are another type of constraints during Construction of coupling product elements with process elements. They make Gears Wheels construction construction other components it possible to define resource constraints where resources are product components. More precisely, a product related con- straint is a constraint on activities and product nodes that im- Figure 5: Temporal constraint network of the bicycle produc- plicitly defines resource constraints, and constrains on pro- tion process. cess and product variables. A product related constraint has the form A produces n N f or B, where A and B are ac- Frame, ID=1 Variables tivities, n ∈ N+ , and N is the name of a node in the prod- rear uct model graph, having (at least) one incoming edge having front wheel wheel rear gears associated a cardinality variable. Such a product related con- Wheel, ID=1 Whee, ID=2 Gears, ID=1 straint corresponds to the following P ROD P ROC constraints: Variables Variables Variables hA, RN , qA ∈ DRN , Af terEndi, hB, RN , −n, Af terStarti, initialLevel(RN , 0), aggConstraint(sum, CEN , =, RN ), Figure 6: Instance tree for a bicycle. where RN is a resource  variable  DRN is whose domain • A set E = {execA | A is an activity ∧ execA 6= 1}. P defined as DRN = 0, C∈CEN max(DC ) (DC de- notes the domain of C, and CEN is the list of cardi- • A set AProc of assignments for all model variables and nality variables of edges entering in N ). The constraint activity parameters (i.e., time instant variables, duration aggConstraint(sum, P CEN , =, RN ) is a global constraint variables, execution flags, quantity resource variables, stating that C∈CEN = RN has to hold. An example of instance number variables), that is, expressions of the product related constraint for the bicycle is form P = value where P is a model variable or an Wheel construction produces activity parameter, and value ∈ Z or value belongs to 2 W heel f or Bicycle assembly. the set of values for P . In general, constraints involving both product and process Fig. 6 depicts a fragment of the instance tree for a bicycle. variables may allow one to detect/avoid planning impossibil- The tree consists of an instance of node F rame, an instance ities due to product configuration, and configuration impossi- of the node Gears, and two instances of node W heel. bilities due to production planning, during the configuration A P ROD P ROC instance is a candidate instance such that the of a product and its production process. assignments in ANodes ∪ ACards ∪ AP roc satisfy all the con- straints in the P ROD P ROC model (node constraints, temporal 2.3 P ROD P ROC Instances constraints, etc.), instantiated with variables of node instances A P ROD P ROC model represents the collection of single (pro- and activity instances in the candidate instance. ducible) variants of a configurable product and the processes The constraint instantiation mechanism, given a (partial) to produce them. A P ROD P ROC instance represents one of candidate instance (a candidate instance is partial when there such variants and its production process. To precisely define are variables with no value assigned to), produces a set of this notion we need to introduce first the notion of candidate constraints on candidate instance variables from each con- instance. A P ROD P ROC candidate instance consists of the straint in the corresponding P ROD P ROC model. A candidate following components: instance has to satisfy all these constraints to qualify as an instance. We give here an intuitive description of how the • A set N I of node instances, i.e., tuples of the form instantiation mechanism works on different constraint types. NiI = hN, i, VNiI i where N is a node in the product Let us begin with node and cardinality constraints. Let c be a model graph, i ∈ N is an index (different for each in- constraint belonging to the node N , or a constraint for an edge stance of a node), VNiI = VN (VN is the set of variables e between nodes N and M . Let us suppose that N1 , . . . , Nk of node N ). are ancestors of N whose variables are involved in c, and let • a set ANodes of assignments for all the node instance p1 , . . . , pk be M etaP aths such that, for i = 1, . . . , k, pi is variables, i.e., expressions of the form V = value where a M etaP ath from Ni to N . We define Ln as the set of k- V is a variable of a node instance and value belongs to tuple of node instances hNjI , (N1 )Ij1 , . . . , (Nk )Ijk i where: NjI the set of values for V . is an instance of N ; for i = 1, . . . , k (Ni )Iji is an instance of • A tree, called instance tree, that specifies the pairs of Ni , connected with NjI through a path pIi in the instance tree node instances in the relation has-part. Such a tree is that matches with pi . For each k-tuple t ∈ Ln , we obtain defined as IT = hN I , E I i, where E I is a set of tuples a constraint on instance variables appropriately substituting eI = hlabel, NiI , MjI i such that there is an edge e = variables in c with variables of node instances in t. For ex- hlabel, N, M, Card, CCi in the product model graph, ample, the constraints (1) and (2) for the node W heel, lead and NiI , MjI are instances of N and M , respectively. to the following constraints on variables of node instances in I Fig. 6 (hV, NID i denotes the variable V of the instance with • A set ACards of assignments for all the instance cardinal- id ID of node N ). e ity variables, i.e., expressions of the form ICN I = n i where NiI is an instance of a node N , e is an edge hW heelT ype,W heel1I i=hF rameT ype,F rameI1 i, (4) e hlabel, N, M, Card, CCi, ICN I = Card, and n is the hW heelT ype,W heel2I i=hF rameT ype,F rameI1 i, (5) i number of the edges hlabel, NiI , CjI i in the instance tree, hF rameT ype,F rameI1 i=Racing bike⇒ such that MjI is an instance of M . ⇒hSpokeN umber,W heel2I i>20. (6) • A set AI of activity instances, i.e., pairs AIi = hA, ii The instantiation of (1) leads to the constraints (4) and where A is the name of an activity with execA = 1, and (5), since it can be instantiated on both the couples of i ∈ N is a unique index for instances of A. node instances appearing in Fig. 6 hW heel1I , F rameI1 i and hW heel2I , F rameI1 i. Instead, the instantiation of (2) leads to engine (i.e., the piece of software that maintains a represen- only one constraint, i.e. (6), because it can be instantiated tation of the product/process under configuration, and checks only on the couple hW heel2I , F rameI1 i. the validity and consistency of user’s choices) each data varia- Node model constraints are instantiated in a slightly differ- tion specified by the user (3). The system engine updates the ent way. Let c be a node model constraint. Let us suppose that current partial configuration accordingly. Whenever an up- N1 , . . . , Nk are the nodes whose variables are involved in c, date of the partial configuration takes place, the user, through let p1 , . . . , pk be M etaP aths such that, for i = 1, . . . , k, pi the system interface, can activate the engine inference pro- is a M etaP ath that ends in Ni . We define Lnmc as the set cess (4). The engine instantiates P ROD P ROC constraints (cf. of ordered k-tuples of node instances h(N1 )Ij1 , . . . , (Nk )Ijk i, Sect. 2.3) on the current (partial) candidate instance defined where for i = 1, . . . , k (Ni )Iji is an instance of Ni connected by user choices, and encodes the product/process configura- by a path pIi with one of its ancestors in the instance tree, tion problem in a CLP program (encoding a Constraint Satis- faction Problem, abbreviated to CSP). Then, the engine uses a such that pIi matches with pi . For each k-tuple t ∈ Lnmc , we finite domain solver to propagate the logical effects of user’s obtain a constraint on instance variables appropriately substi- choices (5). Once the inference process ends (6), the engine tuting variables in c with variables of node instances in t. If c returns to the interface the results of its computation (7). In its is an alldifferent constraint, then we define an equiva- turns, the system interface communicates to the user the con- lent constraint on the list consisting of all the node instances sequences of her/his choices on the (partial) configuration (8). of N1 , . . . , Nk , connected with one of their ancestors by a From a P ROD P ROC model and a user defined (partial) can- path matching with the corresponding M etaP ath. As an ex- didate instance corresponding to it, it is possible to obtain a ample, let us consider the constraint (3) for the bicycle, it can CSP hV, D, Ci where: V is the set of all the variables appear- be instantiated on the couple hW heel2I , GearsI1 i and leads to ing in the (partial) candidate instance; D is the set of domains hGearT ype, GearsI1 i = Special ⇒ for variables in V; C is the set of constraints in the P ROD P ROC ⇒ hSpokeN umber, W heel2I i = 26. model instantiated on variables of the (partial) candidate in- The instantiation of cardinality model constraints is very stance. Such a CSP can be easily encoded in a CLP program simple. Let c be a cardinality model constraint for the car- like the following one. dinalities of the edges with labels e1 , . . . , ek exiting from csp_prodProc(Vars) :- DOMS, CONSTRS. a node N . Let N1I , . . . , NhI be instances of N . For all In it, Vars is the list of variables in V, DOMS is the conjunc- i ∈ {1, . . . , h}, we instantiate c appropriately substituting the tion of domain constraints for domains in D, and CONSTRS is cardinality variables occurring in it, with the instance cardi- the conjunction of constraints in C. Given a program with the e1 ek nality variables ICN I , . . . , ICN I . above-described characteristics, a finite domain solver can be i i Let us now consider process constraints. Let A be an ac- used to reduce the domains associated with variables, pre- tivity, let AI1 , . . . , AIk be instances of A. Let r be the resource serving satisfiability, or to detect the inconsistency of the en- constraint hA, R, q, T Ei, we instantiate it on each instance coded CSP (due to user’s assignments that violate the set of A, i.e., we obtain a constraint hAIi , R, qi , T Ei for each of constraints or to inconsistencies of the original product i = 1, . . . , k, where qi = q is a fresh variable or an inte- model). Moreover, it can be used to determine that further ger. Let c be an activity duration constraint for A, for each node instances are needed, or that there are too many nodes i = 1, . . . , k we obtain a constraint substituting in c dA with in the instance tree. dAIi , and each quantity variable q with the corresponding vari- able qi . Finally, let B an activity, let B1I , . . . , BhI be instances 4 Comparison with Related Work of B. If c is a temporal constraint involving A and B, we In order to point out strengths and limitations of the P ROD - obtain a constraint on activity instances for each ordered cou- P ROC framework, we present in this section a brief compar- ple hi, ji, with i ∈ {1, . . . , k}, j ∈ {1, . . . , h}, substituting ison with some of the most important product configuration in c each occurrence of A with AIi , and of B with BjI . This systems and process modeling tools. mechanism can be easily extended to non-binary constraints. Answer Set Programming (ASP) [Gelfond and Lifschitz, 1988] has been used to implement product configuration sys- 3 CLP-based Product/Process Configuration tems that are specifically tailored to the modeling of software Constraint Logic Programming (CLP) [Jaffar and Maher, product families, e.g., Kumbang Configurator [Myllärniemi 1994] can be exploited to implement a configuration system et al., 2005]. Even if these systems result to be appealing for that, given a P ROD P ROC model (cf. Sect. 2), guide a user a relevant range of application domains, they lack of general- through the configuration process to obtain a P ROD P ROC in- ity. In particular, they do not support global constraints, and stance (cf. Sect. 2.3). In this section, we first present a possi- the so called grounding stage may cause problems in the man- ble structure for such a system. Then, we briefly explain how agement of arithmetic constraints [Myllärniemi et al., 2005]. a configuration problem can be encoded in a CLP program. Product configuration systems based on binary decision A CLP-based system can support a configuration process diagrams (BDDs), e.g., Configit Product Modeler [Configit as follows. First, the user initializes the system (1) select- A/S, 2009], trade the complexity of the construction of the ing the model to be configured. After such an initialization BDD, for the simplicity and efficiency of the configuration phase, the user starts to make her/his choices by using the sys- process. Despite their various attracting features, BDD- tem interface (2). The interface communicates to the system based systems suffer from some significant limitations. First, they basically support flat models only, even though some ities have to be entered into their models by specifying their work has been done on the introduction of modules (see, control-flows. BPMN has been developed under the coordi- e.g., [van der Meer and Andersen, 2004]). Second, they nation of the Object Management Group. P ROD P ROC has find it difficult to cope with global constraints. In [Nørgaard in common with BPMN the notion of atomic activity, sub- et al., 2009] the authors combine BDD and CSP to tackle process, and multiple instance activity. The effect of BPMN alldifferent constraints. However, they consider flat joins and splits on the process flow can be obtained using tem- models only. We are not aware of any BDD system that deals poral constraints. In P ROD P ROC there are no notions such as with global constraints in a general and satisfactory way. BPMN events, exception flows, and message flows. How- Unlike ASP-based and BDD-based systems, CSP-based ever, events can be modeled as instantaneous activities and product configuration systems are (usually) capable of deal- data flowing between activities can be modeled with model ing with non-flat models and global constraints. Unfor- variables. YAWL is a process modeling language whose in- tunately, the modeling expressiveness of CSP-based sys- tent is to directly supported all control flow patterns. P ROD - tems has a cost, i.e., backtrack-free configuration algo- P ROC has in common with YAWL the notion of task, multi- rithms for CSP-based systems are often inefficient, while ple instance task, and composite task. YAWL join and split non backtrack-free ones need to explicitly deal with dead constructs are not present in P ROD P ROC, but using temporal ends. Moreover, most CSP-based systems do not offer constraints it is possible to obtain the same expressivity. The high-level modeling languages (product models must be notion of cancellation region is not present in P ROD P ROC, specified at the CSP level). Some well-known CSP-based but our framework could be extended to implement it. configuration systems, such as ILOG Configurator [Junker, As opposed to traditional imperative approaches to process 2003], which features various interesting modeling facili- modeling, DECLARE uses a constraint-based declarative ap- ties, and Lava [Fleischanderl et al., 1998], which is based proach. Its models rely on constraints to implicitly determine on Generative-CSP, seem to be no longer supported. A re- the possible ordering of activities (any order that does not cent CSP-based configuration system is Morphos Configura- violate constraints is allowed). With respect to DECLARE, tion Engine (MCE) [Campagna et al., 2010]. As other CSP- P ROD P ROC has in common the notion of activity and the use based systems, it makes it possible to define non-flat models. of temporal constraints to define the control flow of a pro- Its configuration algorithm is not backtrack-free, but it ex- cess. The set of atomic temporal constraints is not as big as ploits back-jumping capabilities, to cope with dead ends, and the set of template constraints available in DECLARE, how- branch-and-prune capabilities, to improve domain reduction. ever it is possible to easily the available ones so as to define all From the point of view of process modeling, P ROD P ROC can complex constraints of practical interest. Moreover, in P ROD - be viewed as an extension of MCE modeling language. In P ROC it is possible to define multiple instance and composite particular, it extends MCE modeling language with the fol- activities, features that are not available in DECLARE. lowing features: (1) cardinality variables, i.e., has-part/is- From the point of view of process modeling, P ROD P ROC part-of relations can have non-fixed cardinalities; (2) product combines modeling features of languages like BPMN and model graph, i.e., nodes and relations can define a graph, not YAWL, with a declarative approach for control flow defini- only a tree; (3) cardinality constraints and cardinality model tion. Moreover, it presents features that, to the best of our constraints, i.e., constraints can involve cardinalities of rela- knowledge, are not presents in other existing process mod- tions; (4) M etaP aths, i.e., a mechanism to refer to particular eling languages. These are: resource variables and resource node instance variables in constraints. constraints, activity duration constraints, and product related P ROD P ROC can be viewed as the source code representa- constraints. Thanks to these features, P ROD P ROC is suit- tion of a configuration system with respect to the MDA ab- able for modeling production processes and, in particular, straction levels presented in [Felfernig, 2007]. P ROD P ROC to model mixed scheduling and planning problems related product modeling elements can be mapped to UML/OCL in to production processes. Furthermore, a P ROD P ROC model order to obtain platform specific (PSM) and platform inde- does not only represent a process ready to be executed as pendent (PIM) models. The mapping to OCL of M etaP aths a YAWL (or DECLARE) model does, it also allows one to containing ‘?’ wildcards and of model constraints requires describe a configurable process. Existing works on process some attention. For example, the latter do not have explicit configuration, e.g., [Rosa, 2009], define process models with contexts as OCL constraints must have. Since P ROD P ROC variation points, and aim at deriving different process model does not support the definition of taxonomies of product com- variants from a given model. Instead, we are interested in ponents, there will not be generalization hierarchies in PMSs obtaining process instances, i.e., solutions to the schedul- and PIMs corresponding to P ROD P ROC models. ing/planning problem described by a P ROD P ROC model. In the past years, different formalism have been proposed With respect to the works of Mayer et al. on service pro- for process modeling. Among them we have: the Busi- cess composition (e.g. [Mayer et al., 2009]), P ROD P ROC is ness Process Modeling Notation (BPMN) [White and Miers, more geared toward production process modeling and con- 2008]; Yet Another Workflow Language (YAWL) [ter Hofst- figuration. However, certain aspects of service composition ede et al., 2010]; DECLARE [Pesic et al., 2007]. problems can be modeled using P ROD P ROC too. Languages like BPMN and YAWL model a process as a The P ROD P ROC framework allows one to model products, detailed specification of step-by-step procedures that should their production processes, and to couple products with pro- be followed during the execution. BPMN and YAWL adopt cesses using constraints. The only works on the coupling of an imperative approach in process modeling, i.e., all possibil- product and process modeling and configuration we are aware of are the ones by Aldanondo et al. (see, e.g., [Aldanondo [Gelfond and Lifschitz, 1988] M. Gelfond and V. Lifschitz. and Vareilles, 2008]). They propose to consider simultane- The stable model semantics for logic programming. In ously product configuration and process planning problems ICLP/SLP, pages 1070–1080, 1988. as two constraint satisfaction problems. In order to propa- [Jaffar and Maher, 1994] J. Jaffar and M. J. Maher. Con- gate decision consequences between the two problems, they straint logic programming: A survey. J. Log. Program., suggest to link the two constraint based models using cou- 19/20:503–581, 1994. pling constraints. The development of P ROD P ROC has been inspired by the papers of Aldanondo et al., in fact, we also [Junker, 2003] U. Junker. The Logic of ILOG have separated models for products and processes and, con- (J)Configurator: Combining Constraint Programming straints for coupling them. However, our modeling languages with a Description Logic. In Proc. of the IJCAI’03 are far more complex and expressive than the one presented Workshop on Configuration, pages 13–20. 2003. in [Aldanondo and Vareilles, 2008]. [Laborie, 2003] P. Laborie. Algorithms for propagating re- source constraints in AI planning and scheduling: existing 5 Conclusions approaches and new results. Artif. Intell., 143:151–188, In this paper, we considered the problem of product and pro- 2003. cess modeling and configuration, and pointed out the the lack [Mayer et al., 2009] W. Mayer, R. Thiagarajan, and of a tool covering both physical and production aspects of M. Stumptner. Service composition as generative con- configurable products. To cope with this absence, we pre- straint satisfaction. In Proc. of the 2009 IEEE Int. Conf. sented a graphical framework called P ROD P ROC. Further- on Web Services, pages 888–895, 2009. more, we shown how it is possible to build a CLP-based con- [Myllärniemi et al., 2005] V. Myllärniemi, T. Asikainen, figuration systems on top of it, and presented a comparison T. Männistö, and T. Soininen. Kumbang configurator - with some of the existing product configuration systems and a configurator tool for software product families. In Proc. process modeling tools. of the IJCAI’05 Workshop on Configuration, pages 51–56. We already implemented a first prototype of a CLP-based 2005. configuration system that uses P ROD P ROC. It covers only product modeling and configuration, but we are working to [Nørgaard et al., 2009] A. H. Nørgaard, M. R. Boysen, R. M. add to it process modeling and configuration capabilities. We Jensen, and P. Tiedemann. Combining Binary Deci- also plan to experiment our configuration system on differ- sion Diagrams and Backtracking Search for Scalable ent real-world application domains, and to compare it with Backtrack-Free Interactive Product Configuration. In Porc. commercial products, e.g., [Blumöhr et al., 2009]. of the IJCAI’09 Workshop on Configuration, 2009. [Pesic et al., 2007] M. Pesic, H. Schonenberg, and W.M.P. References van der Aalst. DECLARE: Full support for loosely- [Aldanondo and Vareilles, 2008] M. Aldanondo and structured processes. In Proc. of EDOC’07, pages 287– E. Vareilles. Configuration for mass customization: 287, 2007. how to extend product configuration towards requirements [Rosa, 2009] M. La Rosa. Managing Variability in Process- and process configuration. J. of Intelligent Manufacturing, Aware Information Systems. PhD thesis, Queensland Uni- 19(5):521–535, 2008. versity of Technology, Brisbane, Australia, 2009. [Allen, 1983] J. F. Allen. Maintaining knowledge about tem- [Sabin and Weigel, 1998] D. Sabin and R. Weigel. Product poral intervals. Commun. ACM, 26:832–843, 1983. configuration frameworks-a survey. IEEE Intelligent Sys- [Blumöhr et al., 2009] U. Blumöhr, M. Münch, and tems, 13:42–49, July 1998. M. Ukalovic. Variant Configuration with SAP. SAP Press, [ter Hofstede et al., 2010] A. H. M. ter Hofstede, W.M.P. 2009. van der Aalst, M. Adams, and N. Russell. Modern Busi- [Campagna et al., 2010] D. Campagna, C. De Rosa, ness Process Automation - YAWL and its Support Environ- A. Dovier, A. Montanari, and C. Piazza. Morphos Config- ment. Springer, 2010. uration Engine: the Core of a Commercial Configuration [van der Meer and Andersen, 2004] E. R. van der Meer and System in CLP(FD). Fundam. Inform., 105(1-2):105–133, 2010. H. R. Andersen. BDD-based Recursive and Conditional Modular Interactive Product Configuration. In Proc. of [Configit A/S, 2009] Configit A/S. Configit Product Mod- Workshop on CSP Techniques with Immediate Application eler. http://www.configit.com, 2009. (CP’04), pages 112–126, 2004. [Felfernig, 2007] A. Felfernig. Standardized Configuration [van Hoeve, 2001] W. J. van Hoeve. The alldifferent Con- Knowledge Representations as Technological Foundation straint: A Survey, 2001. for Mass Customization. IEEE Trans. on Engineering Management, 54(1):41–56, 2007. [White and Miers, 2008] S. A. White and D. Miers. BPMN [Fleischanderl et al., 1998] G. Fleischanderl, G. Friedrich, modeling and reference guide: understanding and using BPMN. Lighthouse Point, 2008. A. Haselböck, H. Schreiner, and M. Stumptner. Config- uring Large Systems Using Generative Constraint Satis- faction. IEEE Intelligent Systems, 13(4):59–68, 1998.