Solutions for product configuration management: An empirical study

JINN-YI YEH; TAI-HSI WU

doi:10.1017/S0890060405050043

Solutions for product configuration management: An empirical study

Published online by Cambridge University Press: 22 July 2005

JINN-YI YEH and

TAI-HSI WU

Show author details

JINN-YI YEH: Affiliation:
Department of Industrial Engineering and Technology Management, Da-Yeh University, 112 Shan-Jiau Road, Da-Tsuen, Changhua, Taiwan 515, Republic of China
TAI-HSI WU: Affiliation:
Department of Industrial Engineering and Technology Management, Da-Yeh University, 112 Shan-Jiau Road, Da-Tsuen, Changhua, Taiwan 515, Republic of China

Article contents

Abstract
1. INTRODUCTION
2. A CASE STUDY: WEIGHING SCALES
3. GAs FOR CONFIGURATION PROBLEMS
4. COMPUTATIONAL RESULTS ANALYSIS
5. EXPERIENCES FROM REAL-WORLD APPLICATION
6. CONCLUSIONS
ACKNOWLEDGMENTS
References

Rights & Permissions

Abstract

Customers can directly express their preferences on many options when ordering products today. Mass customization manufacturing thus has emerged as a new trend for its aiming to satisfy the needs of individual customers. This process of offering a wide product variety often induces an exponential growth in the volume of information and redundancy for data storage. Thus, a technique for managing product configuration is necessary, on the one hand, to provide customers faster configured and lower priced products, and on the other hand, to translate customers' needs into the product information needed for tendering and manufacturing. This paper presents a decision-making scheme through constructing a product family model (PFM) first, in which the relationship between product, modules, and components are defined. The PFM is then transformed into a product configuration network. A product configuration problem assuming that customers would like to have a minimum-cost and customized product can be easily solved by finding the shortest path in the corresponding product configuration network. Genetic algorithms (GAs), mathematical programming, and tree-searching methods such as uniform-cost search and iterative deepening A* are applied to obtain solutions to this problem. An empirical case is studied in this work as an example. Computational results show that the solution quality of GAs retains 93.89% for a complicated configuration problem. However, the running time of GAs outperforms the running time of other methods with a minimum speed factor of 25. This feature is very useful for a real-time system.

Keywords

Configuration Genetic Algorithm Mathematical Programming Product Family Model Tree Searching

Information

Type: PRACTICUM PAPER
Information: AI EDAM , Volume 19 , Issue 1 , February 2005 , pp. 39 - 47

DOI: https://doi.org/10.1017/S0890060405050043 [Opens in a new window]
Copyright: 2005 Cambridge University Press

1. INTRODUCTION

The demand for individualized products has increased and the product configuration process has become more interesting in the recent decades. By the product configuration process, we refer to the process through which the customer's needs are translated into the product information needed for tendering and manufacturing the product such as product cost, bill of materials (BOM), product cycle, and so on. Therefore, mass customization manufacturing (MCM) has emerged as a new trend for it aims at satisfying the needs of an individual customer with the efficiency of near mass production. Compared with mass production, the number of product variants has increased drastically in MCM. That is, a large number of BOM structures will occur in MCM, in which a wide range of combinations of product features may result in millions of variants for a single product.

There have been several attempts to define and deal with configuration management. Knowledge-based systems are often discussed and developed. For example, Barker et al. (1989) developed the XCON system, which is a rule-based system developed by the Digital Corporation for configuring its products. Lowe et al. (1998) built intelligent knowledge-based systems with good maintainability to the configuration problems of computer and compressors. Chao and Chen (2001) proposed a set of modeling procedures to build up an assembly model through collecting assembly rules and constraints. Forza and Salvador (2002) developed a class of information systems that support the order acquisition and fulfillment process in high product variety environments. Chen and Lin (2002) developed a decision model for product concept selection in configuration design to minimize functional coupling and coupling of concepts with respect to constraints.

Constraint-based reasoning is also often used to represent and find solutions to the configuration problems. For instance, Frayman and Mittal (1987) proposed a frame-based expert system using constraint satisfaction problems (CSP) to solve the computer configuration problem. Fohn et al. (1995) used constraint-based modeling and interactive constraint satisfaction approaches to construct a personal computer configuration system to fulfill customer requirements. Fleischanderl et al. (1998) applied generative constraint satisfaction in Lava, which is used to configure large digital switching systems. Mailharro (1998) developed a new framework where a configuration problem was considered both as a classification problem and as a CSP. Hulubei et al. (2003) present a value ordering heuristic to solve real-life configuration problems that have a huge number of solutions, few of which are acceptable from a practical standpoint.

Hierarchies, templates, and modules are usually developed to describe the concept and the connection between product components. For example, Jiao and Tseng (2000) developed a product family architecture, which is an effective tools to support product variety with minimal data redundancy. Anderson (1997) pointed out the application of architecture and modularity to design results in modular product design so as to accommodate agile product development. Choi and Bae (2001) proposed an architecture for product configuration management in industrial virtual enterprises, which includes the common configuration objects and functions extracted from various configuration standards. Kusiak and Huang (1996) defined the modular product design as designing products, assemblies, and components that fulfill various functions through configuration of distinct building modules. Stonebraker (1996) found that modular structures are related to more dynamic and competitive products, and traditional structures are associated with less dynamism and competition.

Other frequently used techniques for product configuration include preference programming, artificial intelligence (AI) methods, and so forth. For instance, Junker and Mailharro (2003) proposed a preference programming system to provide a new paradigm for expressing user preferences and user wishes and provide search strategies to solve configuration problems. Fleischanderl et al. (1998) pointed out that configurator development is an excellent application area for AI methods. Turban (1992) has applied the AI techniques to build an expert telephone configuration system. Globerson (1997) discussed potential sources of discrepancies between customer expectation, designer understanding, and final product configuration, and gave a report on investigation of these issues. Svensson and Barfod (2002) described the evolution from crafting of customized products to the manufacturing of mass customized products. They indicated that industrialization is only a qualifying attribute.

Although the configuration problems have been solved by many techniques, the efficiency for finding solutions to them under real-time conditions is seldom discussed. In this paper, we present a decision-making scheme by constructing a product family model (PFM) first. We later transform the corresponding PFM into a product configuration network. The objective of finding the best solutions possible, given the time constraints, is formalized by mathematical programming (MP). The utility of a configuration returned by a search algorithm depends on the cost of this configuration as well as on the time required to find it. We apply genetic algorithms (GAs) as an approximation of a search algorithm, which is optimal in the sense that it minimizes the time of computation. The rest of this paper is organized as follows: the description of a weighing-scale case study is expressed in Section 2; the operation of GAs is explained in Section 3; computational results analysis is presented in Section 4; experiences learned from real-world applications is drawn in Section 5; the conclusion is given in Section 6.

2. A CASE STUDY: WEIGHING SCALES

A case study of the configuration problem is obtained from a small company, which produces weighing scales, located in Central Taiwan. This company operates in a market where survival is connected to the ability to create products that meet the specific needs of customers. For confidentiality reasons, only partial specification of the weighing scale is shown in Table 1. Table 2 is the weighing scale example for a generic variety representation in the structural view. Through this structure, the PFM for the weighing scales can be constructed.

Partial specifications of weighing scale

Structural view for weighing scale

Figure 1 shows a PFM that demonstrates a generic structure with four levels including product level, module level, component level, and instance level. Products consist of modules and modules consist of components. For each component, there are a number of varieties that result in a different number of instances. This model is applied to all product variants of a family that share a common structure.

A product family model.

Usually, there are some constraints between two consecutive instances in the geometric view such as size, type, color, and so forth. For example, V_{11-2_1} and V_{31-1_1} of Figure 1 are incompatible. That is, only one of them can be selected for a product variant. These are called type I constraints. There are type II constraints that deal mostly with configuration design knowledge. We assume that it is not necessary to change any design of the existent component and their instances in connection with sales and production of the product. To satisfy the customer, a product configuration system must be performed by selecting instances of components based on minimum configuration cost or manufacturing lead time.

The PFM can be conveniently transformed and modeled as a product configuration network. The network corresponding to Figure 1 is shown in Figure 2. Each component level of the PFM maps to a stage level on the multistage network. All its instances are then transformed to become nodes at this stage. For instance, V_12-1 and V_12-2 of Figure 1 are corresponding to the node V_12-1 and node V_12-2 of Figure 2, respectively. After all components are transformed, one node is added to the first stage to represent the starting point and another node is added to the last stage to represent ending point.

A product configuration network corresponding to Figure 1.

Recall the decision problem regarding product configuration management described in Section 1. It is not difficult to see that finding a product configuration that results in the minimum cost while satisfying customers' specifications on some components is actually equivalent to finding the shortest path in the corresponding product configuration network with some side constraints (configuration constraints). Note that some configuration constraints can be graphically depicted in the network, while some cannot, and are usually described as rules.

Finding the shortest path within a network with side constraints can be formulated as a minimum-cost flow problem. The formulation of the model is given below. Consider a capacitated network G = (N, A), where N is the set of nodes and A is the set of arcs, and define C_ij is the cost per unit flow through node i to node j, b_i is the net flow generated at node i, b_i > 0 if node i is a supply node, b_i < 0 if node i is a demand node, and b_i = 0 if node i is a transshipment node; x_ij = 1, if arc (i, j) is selected to be included in the shortest path, and x_ij = 0, otherwise.

The formulation of the model is the following:

The objective function minimizes the total flow cost/configuration cost, while Eq. (2) denotes the node constraints. Configuration constraints are placed in Eq. (3) to assure that incompatibility will not occur when customers specify their choices on some components. Some dependence relationships between certain components have to be realized and can be expressed in this equation as well. Equation (4) demands that all decision variables take on a value between 0 and 1. The best decision for this model can be obtained by applying algorithms such as simplex method (Bazaraa et al., 1990) or tree-searching methods (Russell & Norvig, 2003).

Theoretically, the user can get the optimal solution easily. However, the variety of options available for a common product usually allows for billions of feasible product configurations. This will make this problem difficult to solve consistently. Thus, it is necessary to find an approximation algorithm to decrease computational complexity. A GA is a good candidate.

3. GAs FOR CONFIGURATION PROBLEMS

The operation of GAs starts with a set of solutions (represented by chromosomes) called population. Solutions from one population are taken and used to form a new population. This is motivated by a hope that the new population will be better than the old one. Solutions that are selected to form new solutions (offspring) are selected according to their fitness: the more suitable they are, the more chances they have to reproduce (Goldberg, 1989; Mitchell, 1999). The description of the GAs for configuration problems is described as follows.

3.1. Chromosome encoding and evaluating

If a product consists of N_par components and each component has v_i candidate instances for 1 ≤ i ≤ N_par, then the chromosome is written as a vector with 1 × N_par elements such that

where g_i is an integer value to represent the selected instance for the ith component. Each gene has its upper bound to represent the maximum number of instances defined as V_1×Npar for the corresponding component. After chromosomes have been created, each chromosome has a cost found by evaluating the cost function:

where x_i,j = 1, if i = g_i and j = g_i+1, or x_i,j = 0, otherwise.

3.2. Crossover

This research uses the two-point quadratic-gene exchange for crossover operation. It is a combination of an extrapo-lation method with a crossover method (Haupt & Haupt, 1998). The crossover rate is assumed to be P_cr. Figure 3 illustrates the two-point crossover operation by considering two chromosomes from the selection operation known as parent₁ and parent₂. The crossover point is randomly designated by

Two-point crossover operation.

Assume that the parent chromosomes are

Then, the genes at the crossover point are combined to form new genes that will appear in the offspring as

where β is also a random value between 0 and 1. The next step is to complete the crossover with the rest of the genes based on the crossover point by exchanging genes with each other.

3.3. Mutation

In this paper, a one-point mutation operation is performed by changing one offspring gene randomly with probability P_mr defined as

where α is a random number between zero and 1 and δ is a mutation point computed similarly by Eq. (7). Figure 4 demonstrates an example for the one-point mutation operation.

One-point mutation operation.

3.4. Algorithm

The resulting GAs can be summarized as follows:

4. COMPUTATIONAL RESULTS ANALYSIS

To determine the parameters for the GAs and to filter out inefficient tree-searching methods, a real-world weighing scale case is collected for a preliminary test. There are 16 different components with a total of 116 different instances. We simply use Microsoft Excel to store the data in our study. The data storage for other cases could be some database systems. The maximum number of instances of components is [2, 12, 8, 22, 7, 4, 2, 10, 18, 4, 4, 4, 11, 4, 2, 2]. It results in more than 479 billion feasible configurations. All the implementations are carried on a PC that has an Intel Pentium III 700-MHz CPU and 256 MB of RAM. The GAs are run 10 times with independent and identical properties.

Table 3 lists the results of different combinations between crossover rate and mutation rate with 5000 generations. The combination of crossover rate with 1.0 and mutation rate with 0.05 forms the best result. The results of varied initial population size are indicated in Table 4. “Hits” is the number of optimal solutions obtained by GAs for which the optimal solutions are found by MP. We select 32 as the initial population size for the advanced experiments.

Results of different combinations between crossover rate and mutation rate

Results of different initial population sizes

A diagram of the best cost versus generations with 10 independent and identical implementations for one-point crossover approach is shown in Figure 5. Obviously, GA will converge at about 3000 generations. The same experiment is implemented for two-point crossover approach, and it results in 1500 generations. Therefore, the parameter settings for the genetic and chromosome operations of GA are then determined as shown in Table 5.

Parameters for GA operations

Preliminary result of GA with 5000 generations.

The preliminary results obtained from different methods are listed in Table 6. These include tree-searching methods such as breadth-first search (BFS), uniform-cost search (UCS), depth-first search (DFS), and iterative deepening A* (IDA*). The number of nodes expanded is recorded for these tree-searching methods. Obviously, both BFS and DFS are not suitable for further testing because they run out of memory after about 20 min. The number of best solutions obtained by GAs is 5 in 10. However, the CPU computational time of GAs is more competitive than others.

Preliminary results of tree-searching methods

To further evaluate the performance of GAs, the dependable cost matrices of 10 cases are generated randomly with the same problem size in the preliminary test. The computational results of GAs, MP, UCS, and IDA* are shown in Table 7. The minimum hits of GAs are greater than 3 in 10 runs. The solution quality of GAs is 98.56, which is defined as the average deviation from the optimal solution. Moreover, the running time of GAs (0.26 s) is faster than the running time of MP (20.3 s), UCS (19.62 s), and IDA* (4.22 s) by speed factors of 78, 75, and 16, respectively.

Computational results for original problem size

When most components double their instances (e.g., the maximum number of instances of components is [2, 23, 16, 44, 14, 8, 4, 20, 36, 8, 8, 8, 22, 8, 2, 2]), the problem complexity increases and results in more than 3.765 × 10¹⁵ feasible configurations. The computational results are shown in Table 8. The hits of GAs still remain more than three, and its solution quality is 93.89%. However, the CPU running time of MP and IDA* grows exponentially. Two cases of UCS are out of memory after 239 min. The running time of GAs (1.94 s) is faster than the running time of MP (147.6 s) and IDA* (48.91 s) by speed factors of 76 and 25, respectively.

Computational results for doubling problem size

5. EXPERIENCES FROM REAL-WORLD APPLICATION

The weighing scale is a typical product that can be customized. There are a lot of scale features that can be personalized such as resolution, precision, analog to digital converter technique, display format, and so forth. The experiences that we learned from this case study are:

About 70% of customers would like to express their preferences on some components of the weighing scale from their experiences or concerns. The weighing scales must be delivered to the customer at a quoted price and at an expected deadline.
Manufacturers are asked to configure weighing scales that can conform to customers' request in short time. Therefore, a real-time product configuration system is needed.
The configuration system that we developed is based on the assumptions (Brown, 1998) that one cannot design new components during the configuration tasks and each component is restricted in advance to only be able to connect to other certain components in fixed ways. However, more than 30% of the products are tailormade based on the specifications from customers in this company. It is a design task and is not discussed in this paper.
For a small case, like the one in Figure 2, the tree-searching methods such as UCS and IDA* are the best choices. However, they are not suitable for the configuration problems with a large problem size. An approximation algorithm is indeed required.
The proposed approach can be deployed to solve the travel configuration problems (Junker & Mailharro, 2003) and wireless access point configuration problems (Hu & Goodman, 2004) for future research.

6. CONCLUSIONS

One of the basic problems of companies that allow the customer to define many product attributes is the efficient handling of the large amount of information relating to the product variants being offered or already ordered. The variation of the product features induces an exponential growth in the volume of information exchanged between sales representative of the firm and its customers. Furthermore, this information has to be fed back in appropriate formats to manufacturing, with the risk of errors and delays due to the variability and complexity of the product information. Therefore, an efficient product configuration system is required for a company to handle information regarding the characteristics of many product variants.

This study presents a product configuration framework that transform product specification to a PFM, in which the relationship between product, modules, and components are defined. Several types of configuration constraints are considered and expressed in the PFM. By means of the PFM, a component configuration network is established. This becomes a shortest path problem where the objective is to have a minimum-cost and customized product from the corresponding network. Several searching algorithms including tree-searching methods, MP, and GAs are then used to search for an optimal or near-optimal configuration/solution. A real case of weighting scale is illustrated in this paper as an example for product configuration management.

Two data sets with different problem size are prepared to evaluate the performance of the GAs. Computational results show that all the solution quality obtained from GAs retains 98.56% for data set 1 and 93.89% for data set 2. Furthermore, the running time of GAs outperforms the running time of other methods. Therefore, GAs is efficient, especially for a real-time system in shortening response time, to find a near-optimal solution for a complicated product configuration problem.

ACKNOWLEDGMENTS

This research was conducted with the partial support of the National Science Council of Taiwan, ROC (NSC 92-2213-E-212-031). The authors express appreciation to Mr. Jim-Ming Chang, a graduate student at Yuan-Ze University, for the experimental setup and data analysis.

Jinn-Yi Yeh received his BS degree from Chung-Yuan Christian University, Taiwan, in 1987 and the MS and PhD degrees from the University of Texas at Arlington in 1993 and 1997, respectively. He is presently an Assistant Professor in the Department of Industrial Engineering, Da-Yeh University, Taiwan. Dr. Yeh's research interests focus on semiconductor manufacturing quality control, medical image processing, and heuristic algorithms.

Tai-Hsi Wu is a Professor in the Department of Industrial Engineering at Da-Yeh University. He received his MS and PhD degrees in industrial engineering from Texas A&M University in 1994. Dr. Wu's research and teaching interests include developing models and algorithms for production and transportation problems.

References

REFERENCES

Anderson, D.M. (1997). Agile Product Development for Mass Customization. Chicago: Irwin Professional Publications.

Barker, V.E., O'Connor, D.E., & Bachant, J. (1989). Expert systems for configuration at digital: XCON and beyond. Communications of the ACM 32(3), 298–318.CrossRef Google Scholar

Bazaraa, M.S., Jarvis, J.J., & Sherali, H.D. (1990). Linear Programming and Network Flows. New York: Wiley.

Brown, D.C. (1998). Defining configuring. Artificial Intelligence for Engineering Design, Analysis and Manufacturing 12, 301–305.CrossRef Google Scholar

Chao, P.Y. & Chen, T.T. (2001). Analysis of assembly through product configuration. Computers in Industry 44, 189–203.CrossRef Google Scholar

Chen, L. & Lin, L. (2002). Optimization of product configuration design using functional requirements and constraints. Research in Engineering Design 13, 167–182.CrossRef Google Scholar

Choi, I. & Bae, S. (2001). An architecture for active product configuration management in industrial virtual enterprises. The International Journal of Advanced Manufacturing Technology 18, 133–139.CrossRef Google Scholar

Fleischanderl, G., Friedrich, G.E., Haselbock, A., Schreiner, H., & Stumptner, M. (1998). Configuring large systems using generative constraint satisfaction. IEEE Intelligent Systems 13(4), 59–68.CrossRef Google Scholar

Fohn, S.M., Liau, J.S., Greef, A.R., Young, R.E., & O'Grady, P.J. (1995). Configuration computer systems through constraint-based modeling and interactive constraint satisfaction. Computers in Industry 27, 3–21.CrossRef Google Scholar

Forza, C. & Salvador, F. (2002). Managing for variety in the order acquisition and fulfillment process: The contribution of product configuration systems. International Journal of Production Economics 76, 87–98.CrossRef Google Scholar

Frayman, F. & Mittal, S. (1987). Cossack: A constraint-based expert system for configuration tasks. In Knowledge-Based Expert Systems in Engineering: Planning and Design (Sriram, D. & Adey, R.A., Eds.), pp. 143–146. Southampton: Computational Mechanics Publications.

Globerson, S. (1997). Discrepancies between customer expectations and product configuration. International Journal of Project Management 15(4), 199–203.CrossRef Google Scholar

Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison–Wesley.

Haupt, R.L. & Haupt, S.E. (1998). Practical Genetic Algorithms. New York: Wiley–Interscience.

Hu, J. & Goodman, E. (2004). Wireless access point configuration by genetic programming. Proc. 2004 IEEE Congress on Evolutionary Computation, pp. 1178–1184. Portland, OR: IEEE Press.

Hulubei, T., Freuder, E.C., & Wallace, R.J. (2003). The Goldilocks problem. Artificial Intelligence for Engineering Design, Analysis and Manufacturing 17, 3–11.CrossRef Google Scholar

Jiao, J. & Tseng, M.M. (2000). Fundamentals of product family architecture. Integrated Manufacturing Systems 11(7), 469–483.CrossRef Google Scholar

Junker, U. & Mailharro, D. (2003). Preference programming: Advanced problem solving for configuration. Artificial Intelligence for Engineering Design, Analysis and Manufacturing 17, 13–29.CrossRef Google Scholar

Kusiak, A. & Huang, C.C. (1996). Development of modular products. IEEE Transactions on Components, Packaging, and Manufacturing Technology, Part A 19, 523–538.CrossRef Google Scholar

Lowe, H., Pechoucek, M., & Bundy, A. (1998). Proof planning for maintainable configuration systems. Artificial Intelligence for Engineering Design, Analysis and Manufacturing 12, 345–356.CrossRef Google Scholar

Mailharro, D. (1998). A classification and constraint-based framework for configuration. Artificial Intelligence for Engineering Design, Analysis and Manufacturing 12, 387–397.Google Scholar

Mitchell, M. (1999). An Introduction to Genetic Algorithms. Cambridge, MA: MIT Press.

Russell, S. & Norvig, P. (2003). Artificial Intelligence: A Modern Approach. Englewood Cliffs, NJ: Prentice–Hall.

Stonebraker, P.W. (1996). Restructuring the bill of material for productivity: A strategic evaluation of product configuration. International Journal of Production Economics 45, 251–260.CrossRef Google Scholar

Svensson, C. & Barfod, A. (2002). Limits and opportunities in mass customization for “build to order” SMEs. Computers in Industry 49, 77–89.CrossRef Google Scholar

Turban, E. (1992). Expert Systems and Applied Artificial Intelligence. New York: Macmillan.