=Paper=
{{Paper
|id=None
|storemode=property
|title=A Graphical Framework for Supporting Mass Customization
|pdfUrl=https://ceur-ws.org/Vol-755/paper01.pdf
|volume=Vol-755
|dblpUrl=https://dblp.org/rec/conf/confws/Campagna11
}}
==A Graphical Framework for Supporting Mass Customization==
https://ceur-ws.org/Vol-755/paper01.pdf
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.