Software product configurators are an emerging technology that supports companies in deploying mass customization strategies. Such strategies need to cover the management of the whole customizable product cycle. Adding process 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 capabilities. 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.
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, preserving 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 series 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 fullyspecified 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
companies struggle to resolve by using traditional software tools, designed for repetitive
productions. 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 [
Mass customization strategies need to cover the management of the whole
customization product cycle, from customer order to final manufacturing. Current
software 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
configuration techniques from products to processes, may avoid or reduce planning
impossibilities due to constraints introduced in the product configuration phase, as well
as configuration impossibilities due to production planning requirements. Existing
languages/tools for process modeling, such as BPMN [
In this section we present the PRODPROC 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 PRODPROC semantics in term of model instances (Sect. 2.3). See
[
A PRODPROC model consists of a description of a product, a description of a process, and a set of constraints coupling the two. In order to introduce the PRODPROC features let us consider a rectangular base prefabricated component multi-story building, together with its construction process. More specifically, a building is composed by the followings parts: story, roof, heating service, ventilation service, sanitary service, 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
development of the building site; building shell and building envelope works; building
services equipment; finishing works. (For a detailed description of such phases see [
A product is modeled as a multi-graph, called product model graph, and a set of constraints. 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 Building
1 Story
walls {0,1} Partition wall system heating
Heating service {0,1} {0,1} roof {0,1} floor {0,1}
Roof
Floor ventilation {0,1} 1 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 components 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, CBuildingi, where the involved variables and the set of constraint are as follows:
VBuilding = {hBuildingT ype, {Warehouse, Office building}i,
hStoryN um, [
CBuilding = {BuildingT ype = Warehouse ⇒ StoryN um = 1}.
Hence, a building is described by four features/variables, each one with a set of possible 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, CStoryi, where:
VStory = {hF loorN um, [
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 ancestors 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 instances 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
labeled label connecting a node N with a node M , will be an edge labeled label,
connecting 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
building 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
defined as hupper story, Story, Story, Card, CCi, where the variable Card is defined
as hCard, [
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 instance 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 [
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
PRODPROC allows one to model a process in terms of activities and temporal relations between them. Moreover, PRODPROC makes it possible to model process resource production 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 characteristics 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 [
Preparation and development of the building site
Building shell and building envelope works
Building services equipment 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 [
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 services equipment”. In the figures, atomic activities are depicted as rectangles, composite activities as nested rectangles, multiple instance activities as overlapped rectangles. Binary 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 conditional temporal constraints is depicted together with its activation condition.
PRODPROC allows one to specify constraints on resource amounts [
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 activities. 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 constraint 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 |
PRODPROC 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. A PRODPROC model represents the collection of single (producible) variants of a configurable product and the processes to produce them. A PRODPROC 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 PRODPROC 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 , E i, 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., expressions of the form ICne = k where n is an instance of a node N , e is a quintuple 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 PRODPROC instance is a candidate instance such that the assignments in ANodes ∪ ACards ∪ AP roc satisfy all the constraints in the PRODPROC model (node constraints, edges constraints, temporal constraints, resource constraints, etc.), appropriately instantiated 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 PRODPROC 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, . . . , nki 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, . . . , nki 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 involved 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, . . . , nki, 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 cardinality 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
On top of the framework we described in Sect. 2 it is possible to implement a
configuration system based on Constraint Logic Programming (CLP) [
User (2) Choice information (8) Choice consequences
System interface
CLP-based configuration system
(1) Initialization (3) Change information (4) Start inference
process (7) Inference process results
System engine (5) CLP program (6) Results
Finite domain solver
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) selecting 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 interface 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 PRODPROC 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 PRODPROC 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 PRODPROC model and a corresponding (partial) candidate instance defined by a user, we can easily obtain a CSP hV AR, DOM, CON S T Ri, where V AR is a set of variables, DOM is a set of finite domain for variables in V AR, and CON S T R is a set of constraints on variables in V AR. V AR will contain a variable for each node instance variable, cardinality variable, activity parameter, process characteristic, resource, and quantity resource variable. DOM will contain a domain, obtained form the PRODPROC model, for each variable in V . CON S T R will contain all the constraints that the (partial) candidate instance should satisfy. As we explained in Sect. 2.3, such constraints 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 constraints, 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:
μ(A, RCP , I) = Sa∈A α(a) ∪ Sc∈RCP γ(c, A).
The function α generates the set of default constraints on duration, start time, and finishing time for an activity instance a: α(a) = tComp(a) if a is a composite activity instance t(a) otherwise , tComp(a) = {tsatart = minb∈pInsts(a) tbstart, teand = maxb∈pInsts(a) tbend, ta end − tsatart, execA = 1}, end ≥ tsatart, da = ta t(a) = {tsatart ≥ 0, teand ≥ tsatart, da = ta end − tsatart, execA = 1}.
The function γ instantiate a constraint c on activity instances in A.
{ha, R, qa, T Ei|a ∈ A∧ ∧ a ↔Act A ∧ qa = qA} c γ(c, A)= {c[dA/da, qA/qa] | a ∈ A ∧ a ↔Act A} {c[A1/a1, . . . , Ak/ak] | [A1, . . . , Ak] = acts(c)∧ ∧ [a1, . . . , ak] ∈ Lact(c, [A1, . . . , Ak], A)} if c ∈ R∧ ∧ c ≡ hA, R, qA, T Ei if c ∈ R∧ ∧ c ≡ initialLevel(R, iv) if c ∈ D if c ∈ C The function Lact(c, [A1, . . . , Ak], A) generates all the k-tuple of activity instances that are instances of activities involved in a constraint c: k
Lact(c, [A1, . . . , Ak], A) = {[a1, . . . , ak] | Vj=1(aj ∈ A ∧ aj ↔Act Aj )}
From instantiated resource constraints and CSP variables for resources it is
possible to generate a cumulative constraint [
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 CS P 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
In this section, we briefly compare the PRODPROC framework with some of the most important product configuration systems and process modeling tools to put in evidence its strength and limitations.
Product configuration systems based on Answer Set Programming (ASP) [
Systems based on binary decision diagrams (BDDs) for product configuration, e.g.,
Configit Product Modeler [
Unlike ASP-based and BDD-based product configuration systems, CSP-based
systems allow the user to define non-flat models and to deal with global constraints.
Unfortunately, the modeling expressiveness of CSP-based systems has a cost, i.e.,
backtrackfree configuration algorithms for CSP-based systems are often inefficient, while non
backtrack-free ones need to explicitly deal with dead ends. Some well-known
CSPbased configuration systems, such as ILOG Configurator [
In [
PRODPROC can be viewed as the source code representation of a configuration
system with respect to the MDA abstraction levels presented in [
In the past years, different formalisms have been proposed for process modeling.
Among them we have: the Business Process Modeling Notation (BPMN) [
From the point of view of process modeling, PRODPROC combines modeling
features 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, PRODPROC is suitable for modeling production processes and,
in particular, to model mixed scheduling and planning problems related to production
processes. Furthermore, a PRODPROC 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., [
The PRODPROC framework allows one to model products, their production
processes, 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. [
In this paper we focused on the problem of product and process modeling and configuration. 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 PRODPROC, 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 PRODPROC. It covers only product modeling and configuration, but we are
working to add to it process modeling and configuration capabilities. PROPROC and
SysML [
In this section, exploiting the building model introduced in Sect. 2, we show an example of PRODPROC 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 particular the generation of a cumulative constraint from resources and instantiated resource constraints.
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.
Preparation and development of the building site, ID = 1
Building shell and building envelope works, ID = 1 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 = 0, hF loorN um, Story-1i = hStoryN um, Building-1i ⇒ ICSutpopreyr-s1tory = 1, hF loorN um, Story-1i < hStoryN um, Building-1i ⇒ ICStory-1 upper story = 0, hF loorN um, Story-2i = hStoryN um, Building-1i ⇒ ICSutpopreyr-s2tory = 1. hF loorN um, Story-2i < hStoryN um, Building-1i ⇒ ICStory-2 Finally, the instantiation of the cardinality model constraint showed in Sect. 2.1 leads to the constraint:
ICSutpopreyr-s2tory 6= ICSrotoorfy-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: tsFtianristhing works-1 = minb∈pInsts(Finishing works-1) tbstart, teFnindishing works-1 = maxb∈pInsts(Finishing works-1) tbend, teFnindishing works-1 ≥ tsFtianristhing works-1, dFinishing works-1 = teFnindishing works-1 − tsFtianristhing works-1.
While for the activity instance “Roof insulation” with id 1 we have: tsRtoaorft insulation-1 ≥ 0, tend
Roof insulation-1 ≥ 0, teRnodof insulation-1 ≥ tsRtoaorft insulation-1, dRoof insulation-1 = tend
Roof insulation-1 − tsRtoaorft insulation-1.
Instantiating the resource and duration constraints for the activity Roof insulation introduced 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:
ICBsauniildtainryg-1 = San , hStoryN um, Building-1i = instF inishing works.
From the PRODPROC partial candidate instance we just described and its instantiated 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; – A FD variable for each instance cardinality variable, e.g, for ICSrotoorfy-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 substituting 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 constraint maximum(T_end_Finishing_works_1,Te), where Ts, Te are respectively 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
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 interface, 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 PRODPROC. The interface presents (on the left, from top to bottom) controls for graphical element selection, 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. 2 We chose CLP instead of Constraint Programming for the advantages the former gives in terms of rapid software prototyping.