Optimization based framework for transforming automotive configurations for production planning Tilak Raj Singh 1 and Narayan Rangaraj 2 Abstract. A product (e.g. automobile, computer) can be config- restrictions imposed on configuration problem and by fulfilling all ured using different combinations of its available attributes (fea- rules configuration will be considered feasible for production. tures). However, selection of attributes may not be independent of In order to provide short lead time for complex engineering the selection of other attributes. In practice, each attribute implies a products (e.g. Automobiles, Computers) often hybrid manufactur- selection rule (dependency) for other sets of attributes in order to gen- ing philosophies like assemble-to-order is used. The production is erate a valid configuration. Due to dynamic changes in the product setup based on forecast demand and final assembly is done for the design, miniaturization, legislation etc., product attributes and their real customer orders. The effectiveness of this method depends upon selection rules get changed. This implies that variants produced in the quality of the forecasted demand. Most manufacturers use data the past may not be valid for future product design. Nevertheless, about product variants produced in the past to get suitable estimates customer history contains important information related to customer for the future customer demand [10]. Continuous changes in prod- buying behaviour which is an essential input for future planning ac- uct design and market conditions imply that product variants which tivities. In order to achieve efficient adaption of past customer orders have been produced in the past may not be valid according to the to a changed product design, we propose a fully automated optimiza- changed product. However, changes are incremental in nature which tion based framework. The methodology is demonstrated using an means that past variants can be upgraded (by dropping and/or adding industry size example. some features) to new changed model once the required changes are incorporated [4]. In this paper our aim is to develop methods to up- grade base configuration (configuration produced in the past) in such 1 Introduction a way that 1) new configuration satisfies required product configu- Manufacturing companies are currently focusing on mass customiza- ration rules 2) new configuration should be as similar as possible to tion. In this environment customer mix and match different available the base configuration. The similarity measure can be monitored by product attributes to get desired configurations. Selection of any at- using some distance (e.g. Hamming distance) or cost function. tribute implies certain conditions on other set of attributes. For exam- In contrast to the above problem, another requirement to trans- ple, if driving assistance system is selected in a car then the customer form existing configuration to the new configuration arises from the may only be able to select steering types which have required control Reconfiguration problem [11]. In this case the previously selected options. These engineering dependencies are available in the prod- base configuration is still valid with respect to configuration model uct’s technical documentation (e.g. Bill-Of-Material) and each valid however the customer may want to make some explicit changes with configuration must satisfy these restrictions in order to be producible respect to the earlier choice - for example, adding or dropping some [13]. Manufacturers enable their customers to select and order con- of product’s features. Most of these reconfiguration problems are structible product variants by offering sales manuals and web-based motivated by the customer’s request to change the previously se- product configurators. The product configurator guarantees that at- lected variants. This is not an uncommon situation in premium cus- tributes selected by the customer must satisfy all dependency rules tomizable products. However, the reconfiguration problem can also at the time configuration is created. If any combination of attributes be driven from the manufacturer point of view. For example due to violates the product configuration rules (constraints), then, this will capacity limitations, production of customer orders may be shifted be an invalid configuration and cannot be produced [5]. We will use from one country/plant to another. Then the production feasibility the term configurations rule (or rules in short) in the meaning of all need to be checked as configuration rules may vary between produc- tion plants and counties. 1 IT-Production Tools, Mercedes-Benz R & D India, Bangalore, Email: In this paper we propose an integrated solution framework where: tilak.singh@daimler.com 2 Indian Institute of Technology, Bombay, Powai Mumbai, India, email: 1) user can update any given configuration by changing configura- narayan.rangaraj@iitb.ac.in tion variables (adding or removing product attributes) 2) Feasibility of desired configuration can be checked at any point of time 3) In case PlanninghDate TargethProductionhDate of conflicts with underlying configuration rules, the solution is com- puted through solving an optimization model which ensures that the modification to the base configuration is done with minimal change Ct-2 Ct-1 Ct T cost. In section 2 and section 3 we will discuss characteristics of the Ot-2 Ot-1 Ot Ct( Ct(+1 t-2 t-1 t t(=t+T t(+1 TimehLine problem and the available data. Section 4 will focus on the develop- { ProductionhHistory -hProduction ment of an optimization based configuration transformation model. Transformationhofhproducth hhhPlanning In section 5 the solution procedure will be discussed with initial com- varianthproducedhinhthehpast -hCapacityh hhw.r.t.hnewhconfigurationhdatahCt( hhhPlanning putational results. th:hTimehinhmonth -hLogistics Th:hPlanninghperiodhinhmonth -hMaterialh Cth:hProducthconfigurationhdatahathtimeht Ot:hOrderhhistoryhathtimehth)producthconfigurationsh hhhPlanninghetc. 2 The planning problem hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhproducedhinhpast) Figure 1: Product variant produced in the past need to be transformed A product can be configured using different combinations of its at- w.r.t. new product design for use in future planning tributes (features). In case of automobiles, attributes could be: body style, transmission type, sunroof, parking assistance etc. If we de- scribe a product as an exhaustive list of attributes then the product capacity planning, material requirement, supplier selection. At time configuration can be expressed as a 0-1 vector over the attribute set, t the manufacturer has information about its current and past product where 0 (zero) represents the absence of any attribute and 1 (one) configurations data (Ct , Ct−1 , ..., capturing list of attributes/features represents its presence in the configuration. A feasible configuration (X) and its dependencies/rules (F )) and order history Ot , which is an can be achieve by satisfying predefined set of rules (Boolean formu- 0-1 assignment of attributes. At any time t the validity of the product las) monitoring interdependencies among attributes. configurations will be checked according to rules written in Ct = Let us define our product configuration problem as per [7, Defi- {Xt , Ft }. As the product changes with respect to time, for every nition 1]: the configuration problem C can be expressed through a time instance we will have a corresponding product configuration triple (X, D, F ), where: problem instance. In practice, process of engineering change starts • X is a set of product attributes (configuration variables) lets say much before (typically 5-7 years) the start of production. This gives {1, ...n}. Where n is the total number of attributes. possibility to know the product configuration data for future time i.e. • D is the set of attributes finite domains d1 , d2 , ..., dn . Ct+T = {Xt+T , Ft+T } at given time t. • F = {f1 , f2 , ..., fm } is set of propositional formulas (rules or Now, for given set of configurations (Ot , will also be called base restrictions) over attribute set X. configuration) which are derived from configuration model Ct = (Xt , Ft ) we are required to validate their feasibility with respect In this paper the configuration variables X are boolean, hence do- to Ct+T = (Xt+T , Ft+T ). In case of infeasible configurations we main di ∈ {0, 1}, ∀i ∈ X. A configuration is said to be feasible if are required to find the new configuration in the solution space of an assignment for all attributes (i ∈ X) is found which fulfils each S(Ct+T ) with the minimal change to its base configuration. As the and every propositions in F . For configuration problem C a solution configurations variables are Boolean in nature, change in the config- space S(C) can be built by finding all assignment of configuration uration can be performed either by adding new attributes, or remov- variable X which satisfy rules F . The problem we have in hand, the ing old attributes. The distance between two configurations (base and size of solution space S(C) could be in the ranges of thousands of transformed) can be expressed through sum of the changes in the at- billion [6]. tribute assignment, which can be expressed through the Hamming For a customizable product which changes with respect to time distance. However, changing any arbitrary attribute in the base con- (due to introduction of new attributes, discontinuation of existing at- figuration in order to make them feasible may not be practically de- tributes or change in attributes dependencies) the configuration prob- sired. For example, some of the product attributes may have high lem at any given time t can be expressed as Ct = (Xt , Dt , Ft ), cost of change such as engine, special body style or sophisticated op- where Xt ,Dt and Ft are configuration variable, its domain and un- tional equipment, and changing these attributes may be difficult to derlying propositional formulas respectively at time t. In this pa- handle as compared to changes in some simple options such as cup per the domain Dt is fixed (boolean for all variables/attributes) so holder or some alarm features. Thus, a change cost can be associated changes in configuration problem are possible by changing configu- with each attribute and transformation of base configuration to new ration variables X, changing rule set F or both. configuration can be sought to be achieved by minimizing the total In the scenario shown in Figure 1, let us assume that at time t the change cost. Change cost will only be associated to configuration if manufacturer wants to make some planning estimate for time t + certain attribute is either added or removed in the configuration. One T (mid to long term planning, typically T = 6 months - 3 years) may consider two different quantities of change cost for an attribute to support various planning activities such as production planning, such as attribute addition cost and attribute removal cost. In case of Reconfiguration problem, some attributes are fixed by Attribute Name Rule Description customer (attributes on which modification is asked) or may have 1 Automatic (2) ∧ (3 ∨ 4) attribute 1 only when at- very high change cost as they may be customer’s most preferred at- climate tribute 2 is present and control either attribute 3 or 4 is tributes. Then the solution is sought only by changing the remain- present ing set of attributes. The reconfiguration problem can be defined as 2 Air condition TRUE must be present in every a special case of configuration problem where certain configuration variant variables are set to predefined values (true or false). The aim is to 3 Comfort ¬(4) attribute 3 is not with at- fix certain attributes in base configuration (either by replacing some package tribute 4 4 Performance ¬(3) attribute 4 is not with at- previously selected attribute or adding new) and then look for a new package tribute 3 configuration which has minimal changes with respect to the base configuration. Table 1: Example: Rule based configuration data In our case, the changes in the configuration can only be made The value of the attribute will be set to TRUE, if particular attribute is either by adding new attributes or removing previously selected at- selected by the customer. The selection of the attribute is controlled tributes from the configuration. As configuration changes are associ- by the logical rule system as shown in rule column of table 1. The ated with change in attributes thus a change cost can be associated logical rule system is built from usual Boolean operators ∨(OR), with each attribute to measure the impact of change. ∧(AND), ¬(NOT) and an attribute serving as a proportional vari- In our work we propose an optimization model for transforming able. The customer order processing is controlled by evaluating the invalid configurations to valid ones as well as transforming configu- rule’s formulae under the variable assignment induced by the cus- rations with predefined settings over attributes (Reconfiguration). We tomer order and executing suitable actions based on whether the for- develop a framework which can incorporate information from differ- mula evaluates to TRUE or FALSE. ent data sources such as configuration rules, sales program (cost as- As discussed in section 2 configuration problem (C) can be de- sociated with attributes) and planning expert’s knowledge (to change fined by triple (X, D, F ). For configuration data shown in table 1. configuration in some guided way). As most of the information is X = {1, 2, 3, 4},D ∈ {0, 1}∀X, and F = {f1 , f2 , f3 , f4 } where available or can be converted in the form of logical propositional for- mulas, we develop an optimization based framework after a required f1 = {1 → (2) ∧ (3 ∨ 4)} transformation of the logical propositions. In the next section we dis- f2 = {2} cuss various input data for the planning problem. f3 = {3 → ¬(4)} f4 = {4 → ¬(3)} 3 Input Data and its characteristics where a → b means attribute a implies attribute b, if a is se- 3.1 The configuration data lected (or set to true) then b has to be selected in the configura- tion. Propositional formulas in F can also be expressed as F = A variant rich customizable product can be defined on the basis of {((2) ∧ (3 ∨ 4)) ∨ ¬(1), 2, ¬(4) ∨ ¬(3), ¬(3) ∨ ¬(4)}. In the given attributes (features) in order to facilitate aggregate level of planning example, associated rule with f3 and f4 have the same boolean ex- for components and modules [14]. Customer configurations can be pression so only one can be evaluated and also f2 = {2} says that created by combining different attributes that are permitted by the attribute 2 will be the part of every configuration. As all rules written corresponding configuration data. It is important that while combin- in the configuration rule set F has to be satisfied. All element of F ing different attributes, we must fulfil the interdependencies between can be combined with AND operator, ϕ = ∧f ∈F f . Thus ϕ will be attributes, so that a feasible product configuration can be generated the boolean formula whose Truth value will represent an configura- [13]. For instance, if in the USA some engines require special trans- tion. ϕ is also called as product overview formula [9]. Our config- mission types, this condition must hold while configuring a car of uration variable set X contains all possible attributes which can be that type. A product document captures the technical, market and the part of the product configuration either from customer point of legal restrictions and provides an important data source for the con- view of manufacturer. For example, some plant and production re- figuration feasibility check. lated attribute may not be relevant to the customer but is required to Interdependencies among attributes are documented and main- handle feasibility of production at certain planning stage. In the next tained in the configuration data by a rule system. These rules are section we discuss different changes in the configuration data which basically Boolean expressions imposed against each attribute. Selec- may result in modification or upgradation of configurations. tion of attributes in a configuration is done through evaluating the respective Boolean expression. Table 1 shows an example of such a 3.2 Changes in the configurations data. A customer configuration consists of a list of attributes. Each at- As a customizable product can be defined based on different features tribute is represented as a Boolean variable in the configuration data. offered by the manufacturer, product changes can be studied based on the change in the offered product attributes. In this section we will ings. For example, due to market changes, the demand for a certain outline various changes in product attributes which can make certain engine type may decrease in comparison to other available engines. product variants to invalid. The changes in the product attributes can In this case the changes in the engine distribution across all trans- be cause by one or more of reasons described below: formed historic orders have to be considered in the transformation process. This information is not documented in the configuration 1. Deletion of old attributes: All past configurations containing at- rules but can be accessible through planning experts or through some tributes which are discontinued will become invalid according to sales forecast. During the development of the automatic configura- changed product. If discontinued attributes have no dependencies tion transformation system we try to accommodate these kinds of with remaining attributes we can simply remove these attributes to requests. restore the validity (feasibility) of the product variant. For a com- plex engineering product this is very unlikely. In general, product 3.3 Customer history attributes have complex dependencies among each other and mod- ification of one attribute needs to be validated with the remaining Let a product be defined by a set of 4 attributes {1, 2, 3, 4}. Accord- set of attributes. ing to Table 1, the configuration can be listed as described in Table 2 2. Change in rule: The technical rules pertaining to an attribute and 3. As shown in Table 3, customer configuration can be presented that are expressed in configuration data may get changed due to as a 0/1 vector over attributes, any change in the configuration can various reasons such as design modification, legal changes. For be made by changing attributes from 0 to 1 and vice-versa. While some practical product instances, a single attribute may depend transforming the configuration, one objective will be to be as close on hundreds of other attributes by a complex Boolean expression. as possible to the old configuration. This can be done by minimizing Change in some part of a rule may affect feasibility of certain at- the Hamming distance between the old and new configurations. tribute combinations. No. Configurations No. 1 2 3 4 3. Inclusion of new attributes: As a product evolves, some new fea- i 1,2,3 i 1 1 1 0 tures get added. These may not have been present in the past, but a ii 1,2,4 ii 1 1 0 1 customer may select them in the future. As newly introduced fea- iii 2,3 iii 0 1 1 0 tures may have some dependencies with other available attributes, iv 2,4 iv 0 1 0 1 variants produced in the past have to be modified in such a way, Table 2: Configuration based Table 3: Configuration as 0/1 that transformed configurations also contain new features (accord- on attributes set matrix over attributes ing the estimate of new feature). 4. Attribute fragmentation/atomization: In some cases an attribute is split into more attributes. For example, let us assume that a car was produced with the option off-road package which includes fea- 4 Formulation of the optimization model tures as high battery capacity, heavy duty suspension, hi-fi music During the transformation of product configurations, we need to eval- system and a sunroof. Customers were not allowed to select above uate each rule written in the corresponding configuration data. At the features individually but selection can be made through package. same time, we also need to ensure, that the changes in the given prod- Now, due to some change, the manufacturer has decided to divide uct variant are done with minimal cost. Cost can vary based on de- the off-road package into two new packages. The first package viation from the base configuration and the type of changes done. In includes the features high battery capacity and heavy duty sus- this section we explore an optimization based framework to find a so- pension, the second package includes the hi-fi music system and lution for the above problem. To create an optimization based trans- sunroof. Both new packages can be selected individually, which formation procedure, all information included in the product config- means that the customer has more choice than before which may uration process need to be considered in the model. To do this, in the effect the distribution of packages from the past. Some input form following section we first transform rules from the configuration data sales in-terms of demand estimates of new package may help here to the corresponding 0-1 discrete programming equivalent forms. to adapt past configurations according to new product offerings. 5. Replacement of attributes: Most often due to technology and other 4.1 Transformation of logical rules to linear changes, some old attributes are replaced by new attributes. For inequalities example, some old telematic features are replaced by the new Constraint programming approach is a well-used methodology inside generation touchscreen based systems. Therefore historic product the many product configuration systems [2]. Restrictions on product variants should also be upgraded to the new generation to use them configurations are modelled as constraints and a solution is a total for planning of a future production system. assignment satisfying each of the constraints. Most of the proposed Apart from the above changes there also exists some desire to change framework rely of the transformation of boolean formulas to special attributes of a past product variant according to new product offer- structure such as conjunctive normal form (CNF) before writing the final constraint set [3]. We developed an alternate method to avoid Attribute Name Selection Rule the initial conversion of the input to CNF. Our formulas are so large 1 Rear-view camera 1 → ¬(4 ∨ 5) ∧ (¬6) that naive CNF conversion by applying the distributive law failed 2 Parking assistant system 2 → (1) ∧ (¬(4 ∨ 5)) 3 Cruise control 3 ← (1 ∨ (4 ∧ 5)) for lack of memory and time. Also, CNF conversion steps involves introduction of large number of new variables which increases the Table 4: Example: attributes and their selection rule complexity of the problem. problem. In this example attribute 1, 2 and 3 imposes a selection rule criteria while attribute 4 and 5 do not have explicit dependencies. 4.1.1 Data structure for configuration rules Our approach, in principle, involves identification of precise com- Using the normal precedence operators and the conventional evalua- pound attribute rules of the problem and then processing it with iden- tion of expressions, the logical rule from configuration data (F ) can tified equations. The logical rule is represented by a tree graph (as per be presented in form of a tree structure. For example, let’s say selec- Section 4.1.1), where attributes are associated with their common op- tion of an attribute 1 is controlled by following Boolean expression: erator node. We traverse through the tree and prune it in such a way, that the standard transformation equation can be applied [12]. Figure f1 = (2) ∧ (3 ∨ 4) (1) 4 shows the final expression tree for configurations rule written in Table 4. The tree representation of above expression can be shown as Figure 2. We used Stack for storing binary tree for implementation of algo- ∧ ∧ ∨ rithm for transforming logical rules to algebraic inequalities [12]. 1 − x6 ∧ x1 ∧ x1 ∧ 1 − x4 1 − x5 1 − x4 1 − x5 x4 x5 ∧ index Elements (a) (b) (c) 2 ∨ 0 ∧ 1 2 Figure 4: Example: Final expression tree for (a) Attribute 1 (b) At- 3 4 2 ∨ tribute 2 (c) Attribute 3 3 3 Figure 2: Representation of 4 4   attribute selection rule in a x1 Figure 3: Rule in a stack     binary tree 3 0 0 1 1 2 0  x2    4 −1 1 0 1 1 0 0   x3   2         1 0 −2 0 0 0 1  ×  x4  ≤  0               0 0 0 −1 −1 0 2   x5   0  4.1.2 Transforming propositional formula’s to 0-1 LP   0 0 0 0 1 1 −1  x6  1 x7 In this section we describe the transformation of logical propositions to its equivalent linear integer constraint through an example. The B × [x] ≤ b (3) procedure to obtained required transformation is discussed in [12] and [1]. Linear inequalities over Boolean variables are a widely used Where: B = Coefficient matrix over attributes and b is the right-hand modelling technique. The main task during transformation of an at- side values. In order to transform the given Boolean expressions to tribute selection rule into a system of linear constraints is to maintain liner constraints we introduced new variable x7 corresponding to at- the logical equivalence of the transformed expressions. The resulting tribute 3. Attribute x7 controls boolean expression 4 ∨ 5. Resulting system of constraints must have the same truth table as the original constraint system is shown in Eq. 3. statement. For every attribute we introduce a binary decision vari- able, denoted by xi . The connection of these variables to the propo- sitions is defined by the following relations: 4.2 The configuration transformation model  In this section we present a mathematical model for the transfor- 1 iff attribute i is TRUE xi = (2) mation of a base configuration (configuration produced in past) 0 otherwise to the new configuration. The new configuration should satisfy Imposition of logical conditions linking the different actions in a all restrictions imposed by product document and should have model is achieved by expressing these conditions in the form of lin- maximum correlation with its base configuration. ear constraints connecting the associated decision variables. Let us assume that a product is defined by five different attributes Let as shown in table 4. Our task is to write a set of linear constraints i be ith attribute, i ⊆ {1...n}, where n is the total number of which represents same information as described for configuration attributes Data present collective information/rules specified by engineers/product  managers or the user of the our application. For the reconfiguration 1 if ith attribute is present in base configuration problem, change information can be described by the customer and ai = 0 otherwise same can be applied during updating the base configuration. The ex- ci = Change cost associated with attribute i. We assume that ci pert database will collect the changes of attributes from one stage of is given as input either from user or derived from sales product to another. Table 5 shows an excerpt of such a knowledge planning data (e.g. cost of attribute) database. In the expert database we want to maintain an explicit set Decision variables of rules which can be applied in a guided way to base configura- tion. For example, in the past, a car was produced only with one type  1 if ith attribute is in transformed configuration of entertainment system. Due to some enhancement in the product, xi = 0 otherwise the manufacturer now provides three different entertainment systems. The challenge will be to distribute new entertainment systems over Objective Function configurations produced in the past. In this case, the knowledge of X the planning expert plays an important role in achieving a realistic Z = Minimize ci × |ai − xi | (4) transformation of past products. i Subject to Situation in Past in Future An old attribute is replaced i j B[x] ≤ b (5) by new attribute (one to The Hamming distance between base and new configuration for one mapping) An attribute has been re- i i = j for 70% config- attribute i calculated by |ai −xi |. Constraints in Eq. 5 is the set of lin- placed by number of new urations produced in ear inequalities derived from configurations rules (restrictions). Ob- attributes (one to many past; i = k for 30% jective function Z is used to minimize the mismatch cost associated mapping) configurations with each attribute so that the transformed configuration will match Group of individual at- i, j, k p = [i, j, k] add the base (old) configuration as close as possible. Change cost asso- tribute replaced by new package p if at least Package (many to one two attribute from ciated with each attribute is assumed here as an input data provided mapping) {i, j, k} is present either by planning experts (sales) or by user. Usually for automobile An old package is divided p = [i, j, k, l] p1 = [i, j], p2 = change cost for complex attributes such as power train, production in more than one packages [k, l] country is high compare to other attributes. In this case user can spec- Table 5: An excerpt of expert’s knowledge database ify relative cost (such as weight factor or priorities) among attributes. Constraint 5 is a set of linear constraints originating by transforming logical conditions written in the product document to linear inequal- Knowledge from the expert database is applied to every configu- ities using the procedure described in Section 4.1. Any new config- ration that we want to transform. It may happen that the modifica- uration [x] from the above optimization model will guarantee that tions from the expert database do not suffice to meet all the config- the configuration is feasible according to the product document and uration rules. In that case, we use the configuration transformation the objective function will ensure its minimum cost deviation from model presented in section 4.2. A solution is sought automatically the base configuration. As the configuration transformation model that is valid under the new model, but which differs minimally (in transforms one configuration at a time, for every transformation of the ”Hamming distance”) from the ”old” configuration. The flow di- non-feasible (according to given product document) configuration, agram in Figure 5 shows the solution framework. this model needs to be run. A typical practical instance of this prob- The configuration transformation process starts with analyzing the lem contains around 500-1000 decision variables and some tens of product configuration rules. In this step, we can get the list of all thousands of constrains. available attributes and attribute dependencies in terms of logical rules. These rules can be converted into a set of linear inequalities as discussed in Section 4.1. Once the configuration rules are mod- 5 Solution framework elled as constraints, we will look into the expert database and apply Our aim is to provide an automated system which can interpret in- all possible attribute mappings described in the expert database. All formation from configuration data and planning experts. The system discontinued attributes will be removed from the base configuration should consider given information in the best possible way while because they will not be valid for the new model. At this stage, we transforming the base (given) product variants to new (upgraded) will check if this configuration is feasible according to given config- variants. For this, we will create a knowledge database, where in- uration rules. If the answer is YES, we proceed with transforming formation from planning experts can be stored and used during the the next configuration. If the answer is NO, we call the configuration configuration transformation. The term planning experts is used to transformation model as defined in Section 4.2. We repeat the above procedure till all configurations are transformed. Productxconfigurationxrules 0.08 Time (sec) 0.05 Transformxlogicalxrules toxlinearxinequalitiesxas 0.02 discussedxinx inxSectionx4.1 0 5 10 15 Exp. 1: Hamming distance from base−configuration Readxbasexconfiguration Figure 6: Experiment1 Transforming base configurations as per new configuration rules Updatexthexoptimization modelxforxconfiguration updatexbasexconfiguration transformation asxperxexpertsxknowledgex as discontinuation of some old attributes. Removing of barred at- 1Sectionx4.2Y basex Solvexthexmodel tributes and application of information from expert’s knowledge as Removexall discussed in section 5, we found that a large number of configu- discontinuedxattributes rations become feasible (Hamming distance zero in figure 6) . For fromxbasexconfiguration Storextransformed order other configurations, solutions are found by solving the optimization model as discussed in section 4. Yes Feasibility Nextxorder? Notxfeasible check? No Stop 0.10 Time (sec) Figure 5: Flow diagram for transformation of product variants from 0.08 past to given document information 0.06 4 5 6 7 8 9 10 Exp. 2: Hamming distance after upgrading engine type 5.1 Computational Experiments Figure 7: Experiment2 Hamming distance vs time plot of engine We have tested our solution approach with various industry size prob- upgradation problem lems. In this section, we will present two different experiments cre- ated out of practical scenarios in the automotive industry. In experiment 2, we solved the reconfiguration problem by up- Sr Scenario total at- total base grading the engine type. Given 1000 configurations were upgraded to tributes configura- tions a new engine type. First, attributes related to the old engine type were Exp1 Transforming past config- 695 2200 replaced with the new engine and some related attribute replacements urations as per changes in were done through expert’s knowledge base. For example, associat- configuration rules ing the right gear box for the new engine. After user’s modification, Exp2 Upgrading base configura- 705 1000 we transformed the given configurations as per the model shown in tions with new Engine Figure 7. A large number of given configurations are transformed Table 6: Excerpt of computational scenarios with minimal changes (4-8 attributes) to its original values. The op- timization model out of configuration rules has a few thousand deci- Table 6 shows the computational set up for two experiments. In sion variables and thousands of linear constraints. the first experiment (Exp1 ) our aim is to utilize customer orders pro- We used the optimization solver IBM Ilog Cplex 12.2 to solve the duced in the past for future production planning. For this, 2200 past order transformation model. For simplicity, the following assump- configurations are taken which are 6 months old from new produc- tions were made: 1) the attribute change cost is assumed to be one tion date. As the product has undergone engineering changes, our in Experiment1 . 2) In Experiment2 we used a relatively high aim is to upgrade the given configurations as per the new configu- change cost for new engine and in all transformed configurations, the ration rules. The new configurations are defined with 695 different attributes related to new engine remained unchanged. On applying attributes. expert knowledge and the mathematical model that we have devel- Figure 6 shows the plot of time versus Hamming distance oped, the initial computational results shows that the given configu- for transformed configurations. The transformation is done after rations can be transformed as per the desired objective in reasonable analysing new configurations rules which results in information such computation time (a few seconds). 6 Related work REFERENCES [1] Egon Balas, ‘Logical constraints as cardinality rules: Tight representa- tion’, Journal of Combinatorial Optimization, 8(2), 115–128, (2004). Product configuration systems have been a key enabler for mass cus- [2] Caroline Becker and Hélène Fargier, ‘Maintaining alternative values tomization. One main contribution of configurations system is to sup- in constraint-based configuration’, in IJCAI, ed., Francesca Rossi. IJ- port mass customization at various key processes such as product CAI/AAAI, (2013). configuration, product data management (PDM) and customer rela- [3] Hachemi Bennaceur, ‘A comparison between sat and csp techniques’, tionship management (CRM) for effective product and process vari- Constraints, 9(2), 123–138, (2004). [4] Michael Fichter, Michael Klein, and Andreas Schmidt, ‘Transforma- ety management [5]. The effect of configuration process can be seen tion of product between various version of the rule world of a product on the customization responsiveness when information from sources configurator’, IEA/AIE, Springer-Verlag Berliun Heidelberg, 5579(1), such as customer requirements, product characteristics, production 721 – 730, (2009). process and logistics network are considered in the configuration sys- [5] C. Forza and F. Salvador, ‘Application support to product variety man- agement’, International Journal of Production Research, 46(3), 817– tems [8]. 836, (2008). In a variant rich customizable product, finding customer focused [6] H. Graf, ‘Innovative logistics is a vital part of transformable facto- configurations out of enormous choices is a challenging task [16]. ries in the automotive industry’, in Reconfigurable Manufacturing Sys- Failing to access market needs has an adverse effect in product qual- tems and Transformable Factories, ed., AnatoliI. Dashchenko, 423– ity of product configurators [15]. Enabling production planning with 457, Springer Berlin Heidelberg, (2006). [7] T. Hadzic, S. Sathiamoorthy, R. M. Jensen, H. R. Andersen, J. Møller, customer historical demand (configurations produced in the past) and H. Hulgaard, ‘Fast backtrack free product configuration using pre- may help to retain aspects of customer buying behaviour. However, compiled solution space representations’, in Proceedings of the Interna- to use past configurations for future production planning, an upgra- tional Conference on Economic, Technical and Organisational aspects dation is required. Fichter et. al. [4] considered some of the product of Product Configuration Systems, (2004). [8] P.T. Helo, Q.L. Xu, S.J. Kyllnen, and R.J. Jiao, ‘Integrated vehicle con- change conditions in their work of transforming configurations be- figuration systemconnecting the domains of mass customization’, Com- tween two different product document rules. They proposed a knowl- puters in Industry, 61(1), 44 – 52, (2010). edge based framework to transform invalid product variants accord- [9] Wolfgang Küchlin and Carsten Sinz, ‘Proving consistency assertions ing to change of rules in a configurator. However, in their heuristic for automotive product data management’, Journal of Automated Rea- approach it is not clear whether the transformed configuration has soning, 24(1-2), 145–163, (2000). [10] Andrew Kusiak, M. R. Smith, and Zhe Song, ‘Planning product config- small deviation (minimal cost/distance) from original configuration. urations based on sales data’, IEEE Transactions on Systems, Man, and Walter et. al. [17] have discussed MaxSAT based approach for recon- Cybernetics, Part C, 37(4), 602–609, (2007). figuration problem. In our paper we translated configurations propo- [11] Peter Manhart, ‘Reconfiguration - A problem in search of solutions’, in sitional rules to set of linear constraints and the configuration trans- IJCAI’05 Configuration Workshop, eds., Dietmar Jannach and Alexan- der Felfernig, pp. 64–67, (2005). formation problem. An optimization based model has some advan- [12] Tilak Raj Singh and Narayan Rangaraj, ‘Generation of predictive con- tages and the results of this formulation can be extended to support figurations for production planning’, in 15 th International Configura- the generation or the transformation of sets of configurations [12]. tion Workshop, p. 79, (2013). [13] C. Sinz, A. Kaiser, and W. Küchlin, ‘Formal methods for the valida- tion of automotive product configuration data’, Artificial Intelligence for Engineering Design, Analysis and Manufacturing, 17(1), 75–97, 7 Conclusion (JAN 2003). Special issue on configuration. [14] R. Srinivasan and J. M. Swaminathan, ‘Managing configurable prod- ucts in the computer industry: Planning and coordination issues’, vol- In order to adapt the customer configurations produced in the past ume 22, pp. 33–43. Sadhna:Academy Proceedings in Engineering Sci- to the latest engineering design and market conditions we have dis- ences, (February 1997). cussed an optimization based framework. Design related changes [15] Alessio Trentin, Elisa Perin, and Cipriano Forza, ‘Product configurator impact on product quality’, International Journal of Production Eco- are captured in our optimization model by transforming the prod- nomics, 135(2), 850 – 859, (2012). Green Manufacturing and Distribu- uct configuration rules to a set of linear inequalities. Market and tion in the Fashion and Apparel Industries. expert knowledge during configuration transformation are captured [16] Alessio Trentin, Elisa Perin, and Cipriano Forza, ‘Sales configurator ca- by maintaining a knowledge database to transform configurations pabilities to avoid the product variety paradox: Construct development and validation’, Computers in Industry, 64(4), 436 – 447, (2013). according to the best available information. The method will facil- [17] Rouven Walter, Christoph Zengler, and Wolfgang Küchlin, ‘Applica- itate future planning activities based on consistent and constructible tions of maxsat in automotive configuration’, in 15 th International configuration sets (order sets), which will have maximum correla- Configuration Workshop, volume 1, p. 21, (2013). tion with the past customer demand. For a complex product which changes dynamically with respect to time, production planning ac- tivities will improve gradually with the effective adaption of design and market changes.