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