=Paper=
{{Paper
|id=Vol-1220/paper4
|storemode=property
|title=A Backtrack-free Process for Deriving Product Family Members
|pdfUrl=https://ceur-ws.org/Vol-1220/04_confws2014_submission_1.pdf
|volume=Vol-1220
|dblpUrl=https://dblp.org/rec/conf/confws/Schneider14
}}
==A Backtrack-free Process for Deriving Product Family Members==
https://ceur-ws.org/Vol-1220/04_confws2014_submission_1.pdf
A backtrack-free process for deriving product family
members
Homero M. Schneider1
Abstract.1 In this paper, we present a new approach for the generate the values for the variables to which they are attached
customisation of product families. It is based on a knowledge during the customisation process. However, design functions are
framework for representing product families that combines a also used to elicit the dependencies between the variables to form
generic product structure and an extension of the classical constrain dependency patterns.
network model by the attachment of design functions to the
In our approach, members of the product family are derived
variables. We also present a method for deriving family members
from this framework, which consists of a two-stage process. First, a from the knowledge framework as instantiations into two stages.
solution to the constraint network is found which is consistent with First, a solution to the CN-F model has to be found from the
the set of customer requirements. Second, the solution is used to customer requirements. This process is guided by dependency
transform the generic structure into a specific one corresponding to patterns. Then, the solution obtained is used to transform the GPS
a product family member that meets the customer requirements. into a specific physical model that corresponds to a product family
One major outcome of the design functions is the establishment of member, one that meets the customer requirements.
instantiation patterns that guide the problem-solving process. Although the instantiation patterns can restrict the design space
Moreover, if a few modelling conditions are satisfied, it can be to relatively few variables, they cannot avoid backtracking. Thus,
proved that finding solutions becomes a backtrack-free process. As another important contribution of this work is the setting up of
a practical example, this approach is used for the implementation
modelling conditions such that if the CN-F model satisfies them,
of a prototype configurator for a solar powered pumping system.
the instantiation process becomes backtrack-free. These conditions
eliminate the sources of inconsistencies during the execution of the
1 INTRODUCTION instantiation algorithm proposed for the CN-F model.
In contrast to other approaches that claim to be backtrack-free
Since the proposal made by Mittal and Frayman [1] to represent [5, 6], which typically resort to a pre-processing stage and to
product configuration as a CSP problem, many extensions have computational power, our approach resort to the structuration of
been put forward to cope with the specificities of configuration the customization process of product families. As a result, it is
problems [2]. Moreover, to improve the efficiency of the product possible to implement very efficient configurators based on the
configuration process, it is a practice to use knowledge about the data flow principle.
problem domain to guide the search process [3]. Following this As for the remaining of this work, in the next section we review
rationale, this paper presents an approach to derive members of a the related literature. In Section 3, we present the SPPS system,
product family that exploits the specificities intrinsic to this which will be used along the paper as our practical example, the
concept. solar powered pumping system. In Section 4, we introduce our
It is well known that the design of a product family is a knowledge framework, by defining the elements of the GPS and
“difficult and challenging task” [4], for it requires the development CN-F models. In Section 5, we introduce our method for deriving
of multiple products at the same time. However, after the product product family members. First, we present our instantiation
family is designed, it should not be a surprise that the process of algorithm. After that, we introduce the conditions for which this
deriving its members can be turned into a routine design task. This algorithm is backtrack-free. Then, we present the method for
claim follows from the fact that during the design process, transforming the GPS into a specific product model. In Section 6,
designers acquire a great amount of knowledge regarding the we present the implementation of our prototype configurator.
product family architecture, how the variable aspects depend on Finally, in Section 7, we make our concluding remarks.
each other and their range of variability.
The approach presented in this paper is based on a knowledge
framework which combines two general models. A generic product 2 RELATED WORK
structure (GPS) that represents the product family architecture, and
One early proposal to extend the CSP model was made by Mittal
a constraint network model extended with design functions (CN-F)
and Falkenhainer [7], who proposed a dynamic constraint
to complement the GPS in the definition of the product family
satisfaction problem (DCSP) to deal with the fact that the set of
members. The CN-F model is an extension of the classical
variables that are relevant for the solution of a configuration
constraint network (CN) model by the attachment of design
problem may change dynamically during the problem solving. To
functions to its variables. The primary role of these functions is to
deal with the structural aspect of configuration problems, Sabin
1 and Freuder [8] proposed a composite CSP. In their approach, the
Centre for Information Technology Renato Archer, Campinas, Brazil,
email: homero.schneider@cti.gov.br variables are allowed to represent an entire sub problem, such as
the constituent parts of the final product or the internal structure of to control the pump. A float switch (ST) is used to turn the pump
components. In [2], Veron et al. proposed to model the off when the water tank is full, and another switch (S W) is used to
configurable product as a tree with internal nodes representing sub- turn the pump off when the water level at the well is low, thus
configurable components and leaf nodes corresponding to avoiding that it runs dry. The components of an SPPS are
elementary configurable or standard components. The attributes of connected by wires to transmit power and control signals. The
the configurable components are represented as variables and each water is carried from the well to the tank through a piping system.
component is associated to a state variable. The configuration A battery bank may be added to the system if the customer requires
process works on two levels. First, the state variables are used to the system to have some autonomy, so that water may be pumped
manage the tree structure. Then, the CSP problem is addressed to at night or during heavily clouded days. A charge controller is used
define the attributes of the active components. The user expresses to manage the charging of the battery bank.
his choices by adding/retracting unary constraints. Although a typical SPPS is composed of a few components, the
The CSP approaches have been focused mostly on discrete product family may have a very large number of variants. For
variables and binary constraints. However, in the configuration of example, the water pump may have many options, each one
engineering products, it is quite common to have continuous operating optimally within a narrow window of water head and
variables and constraint on multiple variables. Thus, Gelle et al. [9] flux with a specified power, and the PV array can be configured in
introduced local consistency methods to handle discrete and many ways, based on the choice of the PV model and the
numerical variables and in the same framework to address arrangement of the components.
engineering products represented as a CSP. Hence, configuring an SPPS to meet the customer requirements
With a few exceptions, dependencies have been largely and optimizing its performance and cost is far from trivial,
neglected in product configuration approaches. In [10], Xie et al. demanding a lot of expertise. This precludes most of the potential
proposed the Dependent CSP. In this approach, the variables can customers of participating interactively on the decision making
be related by dependencies or constraints and are divided into along the configuration process, except for providing the
independent and dependent by means of the relation of application requirements at the beginning of the process.
dependency. The independent variables are assigned values from
their associated domains, while the values of the dependent
variables are assigned values from the values of the independent 4 THE PRODUCT FAMILY KNOWLEDGE
variables through the relations of dependency. A solution is an FRAMEWORK
assignment to the variables such that all dependencies and
constraints are satisfied. The search for solutions is made by a In the following subsections, we will present our knowledge
backtracking method of the type "backjunping". The updating of framework for representing product families. In this approach we
values and the verification of constraints is organized by a directed assume that the product family has already been developed.
acyclic graph. This graph is defined based on the dependencies However, with this framework we will abstract all the relevant
between variables and of constraints in relation to the independent knowledge about the product family for deriving its members.
variables. Heuristics are used to establish the order in which
variables are considered.
To avoid response delay and dead-ends associated to search- 4.1 The generic product structure
based methods, some recent works resorted to a two-stage process,
by precompiling all the solutions using some form of efficient The GPS is a modular architecture composed of component types,
representation. Although these methods still have to solve a hard which stands for classes of components with the same
problem to find all the solutions, this is done offline and only once. functionality. In our approach, component types belong to four
Then, the interactive part of the configuration process can be done possible categories: common/generic, optional/generic,
efficiently. For instance, Hadzic et al. [5] proposed a method to common/specific and optional/specific. Figure 1 illustrates
compile all the solutions of the problem using binary decision schematically the concept of component types and their
diagrams. Although they claim that the method has very good classification. A component type is specific if the corresponding
practical results, depending on the size of the configuration class has only one component. However, if the corresponding class
problem it may run out of space. A different pre-processing method has two or more components, then the component type is generic.
is proposed by Freuder et al. in [6]. Unlike other conventional
approaches that add constraints to the problem, thus making them
susceptible to space limitation, they remove values from the
domain of the variables to make their representation of the problem
backtrack-free. The disadvantage of this method is that solutions
are lost.
3 THE SOLAR POWERED PUMPING
PRODUCT FAMILY
At the core of a solar powered pumping system (SPPS) product
family, there is a water pump system and a photovoltaic (PV)
array, which provides power to the pump. To improve the pump
performance, a pump controller is used to condition the power and Figure 1. Classification of component types
subsets of , and is a set of design functions (which will be
abbreviated as d-function), such that, every variable in has at
least one d-function attached to it that can generate its values. In
what follows, we will define each of these elements and show how
they apply to the SPPS product family in complement to the GPS.
Variables – Variations between the members of the product family
are identified by variables in . Consequently, these variables can
be mapped on the GPS. Their scope of variation can vary widely,
since they may be related from a specific feature to a whole
component. For example, the configuration of the PV array is
completely specified by three variables: PV module model, PV
modules in series and PV module strings in parallel. The pump is
associated only to the variable Pump model. The range of values
that can be assigned to a variable is called its domain. For example,
the domain for the variable Pump model is composed by the set of
pumps {HR-03, HR-03H, HR-04, HR-04H, HR-07, HR-14, HR-
Figure 2..The GPS for the SPPS product family 20, C-SJ5-8, C-SJ8-7}.
Since all the variability of the product family is related to
If all members of the product family have a component in the optional and generic components, only these types of components
corresponding class, the component type is common. Otherwise, if are associated with variables. These variables will be referred to as
at least one member of the product family does not have a output variables because after their values are assigned, a product
corresponding component in the class, it is optional. Note that the family member is specified. A special type of output variable is the
component types form a partition on the set of components that is inclusion variable associated to optional component types (e.g.,
used to derive all the members of the product family. Battery inclusion). These are binary variables that define if the
In Figure 2, it is shown the GPS for the SPPS product family. component is included or not in the derived product.
The PV array, Pump system, Sensors, Wiring and Piping systems However, variations can also be related to the application
are common component types, i.e., they are present in every environment. For the SPPS example, the amount of Daily water
member of the SPPS product family. However, the Battery bank needed, the Well yield, the Tank capacity, the System autonomy,
and Charge controller are optional component types. The Well and etc., are variables that express the customer requirements and are
Tank sensors are assumed to be specific component types, i.e., they referred to as input variables. Input and output variables are not
do not vary among applications. All the other components are of necessarily disjoint subsets of . Besides these two classes, the set
the generic type, i.e., they can vary among applications and have may contain auxiliary variables, which are neither input nor
two or more variants. It should be noted that, according to our output variables. For example, the variable Total dynamic head is
classification, to be a common component type in the product defined in terms of input variables, and although it is an essential
family architecture does not imply that it is fixed. Actually, in our variable for the choice of the pump system, it is not used to specify
example, most of the product family variability happens on the directly any of the components in the GPS. Therefore, it is
common part of the GPS. Hence, although the optional components classified as an auxiliary variable. In the SPPS example, we have
in a product family are one main source of variability, another identified 32 mixed discrete and continuous variables. In Figure 3,
important source of diversity can be the common part of the they appear as nodes of the constraint network, numbered from 1 to
product family GPS. This is the case only if it is composed of
generic components types.
Formally, we say that a GPS represents the architecture of a
given product family if and only if the architecture of each member
of that family is isomorphic to a substructure of the GPS and
collectively the members of the product family are coherent to the
classification of the component types on the GPS.
Hence, given a sample of SPPS, the GPS can be used to decide
which of them belong to the product family. On the other hand, the
GPS is not enough to determine which configuration of
components can lead to a member of the product family, and let
alone, which specific configuration will meet the requirements of a
given application. To achieve this goal, we combine the GPS with
the CN-F model.
4.2 The Constraint Network Extend with
Design Functions
The CN-F model used in our approach can be regarded as an
extension of the traditional CN model. It is defined by the tuple
( ), where is a set of variables, is a set of constraints on Figure 3. Constraint network for the SPPS product family
32. Some of these variables have been named explicitly within the variables (for which the d-function is defined) and the value
text. As it will be discussed below, for convenience, variables can generated from them, satisfy that constraint. For example, from
be grouped to form a composite variable. The encircled nodes in lines 1, 2, 3 and 4, it can be verified that constraints C7 and C8 are
Figure 3 represent composite variables. incorporated by F4.
In general, not all the variables related (by constraints) to the
Constraints – Constraints define how subsets of variables in are
variable which a d-function is attached to will be involved in the
related to each other, thus restricting the possible combinations of
dependency. For example, the variables Daily water, Battery
values that can be assigned to them simultaneously. For example,
inclusion and Pump output flux are related to Total dynamic head
the following sample of constraints describes how the auxiliary
by the constraint C18 but are not required for the generation of its
variable Total dynamic head is related to some variables in :
values. Consequently, C18 is not incorporated by F4. If a
C7: Total dynamic head (22) is equal to the sum of the Water d-function does not incorporate a constraint involving the variable
level (1), Water drawdown (2), Tank elevation (6) and the to which it is attached, we say that the constraint is free regarding
friction loss of the piping system. that d-function. However, a free constraint may be incorporated by
C8: Total dynamic head (22) must be less or equal than the head another d-function attached to the same variable or to a related
of the pump system (defined by the combination of the pump variable.
and its controller). Input variables are attached with special d-functions that
C18: If there is a Battery inclusion (10), the Daily water (4) request the user to assign a value chosen from a delimited range of
requirement must be equal or less than 24 hours of pumping values, which may be generated dynamically as a function of
with the maximum available Pump output flux (32) at the values assigned to other variables. Hence, except possibly for the
required Total dynamic head (22). input variables, all variables in will necessarily depend on some
Note that while the constraint C8 is defined over one variable, other variable due to the d-function attached to them, forming a
network of dependencies on , as discussed in more detail below.
the other two relate four variables. Actually, in our approach,
The d-function F4 specified in Figure 4 is relatively simple. The
constraints can involve any subset of . To satisfy a constraint, the
values assigned to the variables in the expression defining it must CN-F model for the SPPS also contains much more complex ones.
For example, to define the values of the variables that specify the
render the expression true. However, if a constraint involves an
component type PV array (related above), the d-function F16 finds
inclusion variable and the corresponding optional component will
not be included in the custom product, it can be disregarded. the best module arrangement to cope with the power requirements
of the SPPS without violating the voltage and current restrictions
Figure 3 depicts the complete constraint network for the SPPS
imposed by the pump or battery controller. As another example,
product family. Note that, when nodes are the composition of
variables, they may involve more than one constraint, each one the d-function F12 selects the pump system from a performance
table which correlates the total dynamic head, the output flux and
relating a different subset of those variables.
the input power for the optimal performance of the pump systems.
If a set of variables is strongly coupled, i.e., the value of any
Design Functions – The d-functions have been introduced as an
one variable cannot be assigned independently of the others, as in
extension to the CN model to capture the necessary knowledge to
the two cases just discussed, they are be grouped together to form a
generate the values for the variables in . Generically, d-functions
composite variable and the same d-function will generate the
will be represented by ( ), where is the depended
values for all of them. Otherwise, attaching a single d-function to
variable to which the d-function is attached and are the
each of those variables would form dependency loops between
independent variables from which the value for is generated. As
them, a condition that is undesirable in our approach.
an example, Figure 4 shows the specification of d-function F4,
Since only values generated by the d-functions are taken into
which generates the values for Total dynamic head as a function of
account in the configuration process, in our approach the domain of
Water drawdown, Water level and Tank elevation.
a variable in can be defined as the set of all values that can be
As we shall see in more details below, an important
generated by the d-functions attached to it. An important
consequence of d-functions is the dependency relation between
consequence of this definition is that the domains need not to be
variables that they establish. However, if the value generated by a
defined explicitly. Moreover, they can be either discrete or
d-function is to be consistent with the values of the variables it
continuous without distinction.
depends on, it must incorporate all the constraints involving these
Before introducing the instantiation process for the CN-F
variables. We say that a d-function incorporates a constraint if and
model, we note that the dependency between variables in induces
only if every combination of the values of the independent
a dependency between d-functions in . For example, the
d-function F4 attached to Total dynamic head depends on the
d-functions that generate the values to variables Water drawdown
and Water level, Tank elevation.
5 DERIVING PRODUCT FAMILY
MEMBERS
Members of the product family are derived from the knowledge
framework. This process is divided into two stages. First, a solution
to the CN-F model is found from the values of the input variables.
Figure 4. The d-function F4 attached to Total dynamic head
Second, this solution is used to transform the GPS into a specific
model representing the desired product family member.
5.1 Finding solutions to the CN-F model
An assignment of values to all the variables in such that no
constraint in is violated is said to be a solution to the CN-F
model. The set of all solutions will be denoted by . As we will
argue below, solutions in S correspond to members of the product
family.
The instantiation process begins with the assignment of values
to the input variables and proceeds towards the output variables,
through the auxiliary variables. This process is guided by the
dependencies established over by the d-functions. In Figure 5,
we present an instantiation algorithm to carry out this process. In
that algorithm, a d-function is enabled if all the variables it depends
on have been assigned their values. The set represents the
variables for which the values have already been generated and
( ) represents the set of free variables in relation to . For this
algorithm to work properly, it is necessary to rule out loops
between d-functions. Thus, we assume that can
be order by the dependency relation induce over , that is to say, Figure 6. The instantiation graph for the SPPS product family
for the element is an input d-function or all
they also depend on other variables for checking the consistency of
d-functions it depends on precedes it in that order.
the values assigned by the customer.
Every time a d-function ( ) from is executed (line
Now, every instantiation graph can be associated to a subset of
2 of the instantiation algorithm), a value is assigned to variable
, composed of exactly those d-functions used to generate it. Since
from the values of the variables . If we represent this
the same set of d-functions can be elicited for a variety of inputs,
dependency by a directed graph, with arrows from the independent
we will call this set an instantiation pattern, represented by . More
variables toward the dependent one, the execution of the
specifically, every subset satisfying the ordering condition
instantiation algorithm can be represented by a dependency graph
and such that, for every , there is only one is an
as the one shown in Figure 6. The nodes represent variables (single
instantiation pattern. If a variable in is attached with more than
or composite), the same ones shown on the constraint network in
one d-function, the CN-F model will be associated to more than
Figure 3. Near to each node, it is indicated the d-function that was
one instantiation pattern. However, in general, one should not
used to set its dependency (the incoming arrows). The dependency
expect many instantiation patterns. In the modelling of the SPPS
graph can be organized into dependency levels. At level 0 are the
example, there is only one instantiation pattern composed of 17
input variables whose values have been assigned by the customer
d-functions, number from F1 to F17 in Figure 6.
and that do not depend on other variables. In general, a variable is
As indicated in Figure 5, there are only two points during the
localized at level if it depends on at least one variable at level
execution of the instantiation algorithm where it can terminate
. Note that the input variables Daily water and System
without finding a solution. Each one is associated to a different
autonomy, represented by nodes 4 and 5, appear at levels 2 and 3,
type of inconsistency. Type I arises when the d-functions attached
respectively. Although it is the customer who assigns their values,
to a variable cannot generate its value. The inconsistency of type II,
arises if there is a free constraint in ( ) that is violated by the
values assigned to the variables in . If the values assigned to the
input variables are not part of a solution in , then there is some
inconsistency embedded in the input and the algorithm will fail.
As it is well known, local consistency in a CN model does not
guarantee global consistency [11]. Therefore, although the values
generated by the d-functions are locally consistent, the instantiation
pattern does not guarantee that an input without an embedded
inconsistency will lead to a solution. Thus, in what follows we will
introduce two consistency conditions to the CN-F model such that
our instantiation algorithm will always be able to find a solution.
Consistency condition 1 – For every , there is at least one
which is defined for every instantiation of the variables it
depends on.
Consistency condition 2 – Let be an instantiation pattern.
Every constraint in is incorporated by some d-function belonging
Figure 5. The instantiation algorithm to find solutions to the CN-F model to .
It can be proved that, if the CN-F model satisfies the resulting physical model is isomorphic to the GPS of the product
Consistency conditions 1, no inconsistency of type I will arise family and is coherent to the component types by construction.
during the execution of the instantiation algorithm, and if all its Now, if every relevant design constraint has been elicited and
instantiation patterns satisfy the Consistency condition 2, no introduced in the CN-F model, we can conclude that every solution
inconsistencies of type II will arise. However, if the CN-F model in corresponds to a member of the product family.
satisfies the two conditions, lines 4-12 of the algorithm in Figure 5
can be eliminated, since the inconsistency testing is no longer
required. Therefore, the resulting instantiation algorithm becomes 6 IMPLEMENTATION OF THE
extremely simple. CONFIGURATOR
The CN-F model for the SPPS satisfies the second condition The SPPS configurator has been conceived as a tool to support the
state above; however, it fails the first one. The problem is with the sales force of a company that provides water pumping solutions to
d-function attached to Total dynamic head shown in Figure 4. the rural area. The configurator requires the sales force to have
According to its specification, only after all three inputs variables it only enough technical knowledge about SPPS to make some
depends on have being assigned their values is that the Total assessments at the customer site to input the customer
dynamic head is calculated and the result is compared to the head requirements. This process is interactive with the configurator
of the available pumps. If the condition on line 4 is not satisfies, requesting specific information. To avoid inconsistencies
there is no solution to the application and the configuration has to embedded in the input, the configurator makes a few checks,
be aborted. To satisfy the Consistency condition 1, an alternative suggesting appropriate corrections if necessary. But in case no
approach is to restrict the range of values for the input variable solution can be provided to the customer, the configurator notifies
Water level dynamically, so that the resulting total dynamic head of the impossibility as early as possible.
the application is always within the range of the available pump In Figure 7, it is shown the implementation of SPPS
systems. Nevertheless, this restriction is equivalent to the abort configurator using LabVIEW. At the centre, it can be seen the
condition in a disguised form. On the other hand, because the d-functions (numbered F1 to F17), each one representing a subVI
decision to abort is taken at the very start of the configuration (a kind of routine in LabVIEW), with the variables to which they
process, and we can give explanations for why the configuration are attached at the right of the diagram. The variables to which the
process cannot proceed, this modelling approach was preferred. d-functions depend on are indicated by the lines coming from
However, to cope with this abort condition, it was necessary to add below. Thus, this diagram arrangement clearly reveals the
a control mechanism in the implementation of the instantiation dependency between the d-functions. At the left of the diagram, it
algorithm, not present in its description in Figure 5. Note that the can be seen the control structure which operates in conjunction
risk of having to abort the configuration is reduced as the with the loop structure (the outer structure encompassing the whole
maximum head of the available pumps is increased. program). Initially, only the first four d-functions will be executed.
If the abort condition in the d-function F4 (specified in Figure 4) is
5.2 Transforming the GPS into physical models true there is no solution for the configuration problem and the
program ends. Otherwise, the abort variable is set to false and the
Once the solution to the CN-F model has been found, all the output other d-functions are executed. As the d-functions are executed, the
variables on the GPS have their values assigned, and its values for the correspondent variables are generated, and they are
transformation into a specific physical model can start. This set to inactive. The d-functions attached to variables (other than the
process is carried out in two steps. First, it is necessary to remove inclusion variable) on optional component types, which will not be
the optional components types from the GPS that are not required included in the custom product, can be set to inactive without
in view of the customer requirements. For example, if the customer generating values. When no abortion happens and all the functions
does not require any system autonomy, there is no need for are inactive (which is equivalent to F = in the control algorithm
batteries in the SPPS. To determine if an optional component type in Figure 5), a solution has been found and the program ends. This
have to be removed we refer to the value of the associated happens in exactly three iterations of this configurator program.
inclusion variables. In our example, if the value is 0, the It is interesting to note that, if the CN-F model satisfies the two
component is removed. Otherwise, if it is 1 the component is kept consistency conditions, the configurator can be implemented a data
in the structure. After the GPS has been stripped of the unnecessary flow program by the concatenation of d-functions. Moreover, if it
components, the second step of the transformation process is were not for the abort condition, the iteration structure in Figure 7
carried out with the substitution of the generic components by could have been dismissed.
specific ones from their correspondent class of components. The
definition of which component will be selected is made based on
the values of the output variables on the generic component type. 7 CONCLUSIONS
For example, besides the inclusion variable, the Charge controller In this paper, we have proposed a new approach to the
is associated to three other variables. One of these variables customisation of product families. It is based on a knowledge
specifies the model of the charger, and the other two the framework which combines a GPS and a CN-F model to represent
configuration of two switches to set the output voltage of the product families. Members of the product family are derived from
charger. After all the generic component types have been this knowledge framework by a two-stage process. First, a solution
substituted by specific ones, a physical model of the custom SPPS to the CN-F model is found from the customer requirements
will emerge from the GSP. through an instantiation process. Then, in the second stage, the
Based on the transformation process described above, every solution is used to transform the product family GPS into a specific
solution in leads to a specific physical model. Obviously, the model which represents the desired product family member.
A number of contributions to the area of product configuration Moreover, the d-functions provide a method to establish the
are introduced by this approach. It is provided a formal definition dependency between variables as part of the modelling of the
for the product family GPS and an extension to the classical CN customisation process. Dependency patterns can reduce the design
model by attaching d-functions to the variables to generate their space for finding solution considerably. However, despite their
values. Since the domains of the variables are defined through the local consistent, they do not avoid backtracking. To achieve this
d-functions, their values need not to be predefined explicitly. As a goal we have set up a few conditions for the CN-F model, such
consequence, we can deal with mixed discrete and continuous that, if satisfied, deriving product family members becomes a
variables. backtrack-free process. The remarkable aspect about this
Figure 7. A view of the SPPS configurator program implemented in LabVIEW
achievement is that it does not depend on pre-processing, but can specifications: an integrated approach to product family design,”
be obtained by the systematization of the knowledge about product Research in Engineering Design, vol. 23, no. 2, pp. 141–153, 2012.
families. [5] T. Hadzic, S. Subbarayan, R. M. Jensen, H. R. Andersen, H.
It is also interesting to note that through the d-functions it may Hulgaard and J. Moller, “Fast backtrack-free product configuration
using a precompiled solution space representation,” in International
be possible to design components during the customization
Conference on Economic, Technical and Organizational aspects of
process, thus providing great flexibility to the customization Product Configuration Systems, Technical University of Denmark,
process. However, this is a capability which requires further Lyngby, Denmark, June 28–29, 2004.
investigation, because making changes to components without the [6] E. C. Freuder, T. Carchrae and J. C. Beck, “Satisfaction Guaranteed,”
proper delimitation of the design space can compromise the in Workshop on Configuration, Eighteenth International Joint
manufacturability or performance of the product being derived. Conference on Artificial Intelligence, 2003.
Our approach is suited for the configuration of complex product [7] Mittal, S. and Falkenhainer, B., “Dynamic Constraint Satisfaction
families for which the customers do not have the necessary Problems,” in Proceedings of the 8th National Conference on
expertise to participate directly during all the configuration Artificial Intelligence, 1990, pp. 25-32.
process. It can deal with configuration problems for which the [8] D. Sabin and F. Freuder, “Configuration as Composite Constraint
Satisfaction,” in Technical Report FS-96-03, Workshop on
constraints between the variables are highly complex, since they
Configuration, Menlo Park: AAAI Press, 1996, pp. 28–36.
are incorporated by the d-functions and dealt with in the form of [9] E. Gelle, B. V. Faltings, D. E. Clement, and I. F. C. Smith,
procedures. The complexity of the configurator is not particularly “Constraint Satisfaction Methods for Applications in Engineering,”
affected by the number of variables, since this amounts to adding Engineering with Computers, vol. 16, no. 2, pp. 81–85, 2000.
new d-functions. In case some of the variables are attached with [10] H. Xie, P. Henderson, J. Neelankavil and J. Li, “A Systematic search
more than one d-function, this will generate multiple instantiation strategy for product Configuration,” in 17th International Conference
patterns. However, the proposed instantiation algorithm is enough on Industrial & Engineering Applications of Artificial Intelligence &
to deal with this condition, since at every moment only one Expert Systems Manufacturing (IEA), Ottawa, Ontario, January 1,
instantiation pattern is being followed. As for the verification of the 2004.
compliance to the consistency conditions, this is largely an analysis [11] R. Dechter, “Constraint Networks,” in Encyclopedia of Artificial
Intelligence, S. C. Shapiro, Ed. New York, Wiley, pp. 276–285,
of the d-function individually. (The same is true for maintenance,
1992.
because d-functions are high modular.) Now, if the CN-F model [12] C. Forza and F. Salvador, “Managing for variety in the order
satisfies our assumption on the ordering of the set of d-function and acquisition and fulfillment process: The contribution of product
the two consistency conditions, the configurators can be configuration systems,” International Journal of Production
implemented in the form of dataflow programs by the Economics, vol. 76, pp. 87–98, 2002.
concatenation of the d-functions. [13] A. Haug, L. Hvam and N. H. Mortensen, “A layout technique for
Despite the advantages related above, to exploit all the potential class diagrams to be used in product configuration projects,”
of our approach in practical applications, there are a number of Computers in Industry, vol. 61, pp. 409–418, 2010.
issues that must be further developed. For example, concerning the [14] H. M. Schneider, D. T. Kemmoku, P. Y. Moritomi, J. V. L. da Silva,
integration of our approach into a mass customisation system, it Y. Iano, “Matching the Capabilities of Additive Technologies with a
Flexible and Backtrack-free Product Family Customisation Process,”
will be necessary to have a more elaborate representation of the
in Proceedings of the Fraunhofer Direct Digital Manufacturing
GPS to support the generation of customer quotations and Conference 2014, Berlin, Germany, March 12-13, 2014.
production orders [13]. However, at least for a mass customization
systems based on 3D printing, we have shown that our approach
can be integrated with CAD tools, and that the generation of 3D
models for the custom products can be made automatically, in a
seamless way [14].
ACKNOWLEDGEMENTS
The author wish to gratefully acknowledge the financial support of
FINEP for the realization of this work.
REFERENCES
[1] S. Mittal and F. Frayman, “Towards a Generic Model of
Configuration Tasks,” in Proceedings of the 11th International Joint
Conference of Artificial Intelligence, San Francisco: Morgan
Kaufman, 1989, pp.1395–1401.
[2] M. Veron, H. Fargier and M. Aldanondo, “From CSP to
Configuration Problems,” in AAAI-99 Workshop on Configuration,
Orlando, Florida, July 18–19, 1999.
[3] B. Wielinga and G. Schreiber, “Configuration design problem
solving,” IEEE Expert, vol. 12, no. 2, pp. 49–56, 1997.
[4] T. W. Simpson, B. Aaron, L. A. Slingerland, S. Brennan, D. Logan
and K. Reichard, “From user requirements to commonality