=Paper=
{{Paper
|id=None
|storemode=property
|title=ProdProc - Product and Production Process Modeling and Configuration
|pdfUrl=https://ceur-ws.org/Vol-810/paper-l16.pdf
|volume=Vol-810
|dblpUrl=https://dblp.org/rec/conf/cilc/CampagnaF11
}}
==ProdProc - Product and Production Process Modeling and Configuration==
https://ceur-ws.org/Vol-810/paper-l16.pdf
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.