ISSN : 2234-6473 (Online)

**Industrial Engineering & Management Systems Vol.11 No.2 pp.155-164**

DOI : https://doi.org/10.7232/iems.2012.11.2.155

# An Improved Genetic Approach to Optimal Supplier Selection and Order Allocation with Customer Flexibility for Multi-Product Manufacturing

### Abstract

- 11-2-05.pdf385.9KB

### 1. INTRODUCTION

It has been observed in marketing research that cu-stomers are often indifferent to certain product specifications and are willing to accept products with less desirable product attributes in exchange of price discounts. Intuitively, this extra degree of flexibility in meeting customers’ product specifications (customer flexibility) provides a way for manufacturers to improve profit by making better utilization of manufacturing and supply resources. It is, therefore, important for manufacturers to exploit the advantages of customer flexibility to the full in performing production planning, supplier selection and order allocation among the selected suppliers, in order to maximize profit.

Despite its significance, the challenging problem of developing suitable methodologies for assisting manufacturers to make optimal decisions concerning supplier selection and order allocation incorporating customer fle-xibility has received very little attention in the research community. Kim *et al*. (2002) have considered the supply network of a manufacturer which produces different types of products by using a common set of inputs (e.g., raw materials and component parts). A mathematical mo-del and an iterative algorithm have been developed to solve the configuration problem faced by the manufacturer. Lamothe *et al*. (2006) have studied the design for supply chain problem and proposed an approach to assist designers of a product family to define simultaneously their design choices and the layout of the supply chain for delivering the products. However, these studies have not considered customer flexibility. Che and Wang (2008) have developed an optimization model for integrated supplier selection and quantity allocation of common and non-common parts among the selected suppliers under a multiple products manufacturing environment. The model assumes that each product has a unique bill-of-materials (BOM) structure. However, it cannot solve the complex problems with multiple product families, and also ignores the impact of customer flexibility.

In this paper, each product family consists of a range of products of the same nature (e.g., shirt, hat or bag). Each product (e.g., white collar shirt) in a product family (e.g., shirt) has a specified combination of product attributes (e.g., color, size), and is called a product variant. The product variants in a product family are governed by a generic bill-of-materials (GBOM) product structure (Jiao, 2000), and may share the common usage of raw materials and component modules. When customer flexibility exists, GBOM can be used to calculate the amount of raw materials, component modules and production resources required for satisfying customers’ demands for different product variants. To fully integrate customer flexibility into the supplier selection and order allocation problem, it must be effectively characterized and evaluated. This is a complex problem since customer flexibility is a relatively new concept which involves many uncertain and subjective factors. In this paper, a fuzzy multi-attribute utility approach is adopted to evalu-ate customer flexibility, which is characterized through the customer flexibility range and the customer flexibility response.

A mathematical model is developed in this paper to assist the manufacturer to solve the integrated supplier selection and order allocation problem optimally. The objective is to: 1) determine which product variants are produced and their corresponding production quantities; 2) select appropriate suppliers based on the four most frequently used criteria i.e., price, quality, on-time delivery (Weber and Current, 1993), and trust (Smeltzer, 1997); 3) assign the orders among the selected suppliers; and 4) maximize the manufacturer’s total profit. As the problem is non-deterministic polynomial-time (NP)-hard, an improved genetic approach is also developed in this paper to determine the optimal solution. Genetic algorithms are search and optimization algorithms that derive their computational mechanisms from natural selection and natural adaptation (Holland, 1975; Goldberg, 1989). The algorithms mimic the Darwinian evolutionary process by implementing the “survival of the fittest” strategy. Unlike many other optimization techniques, genetic algorithms do not require strong assumptions in the form of objective function and system constraints (Michalewicz, 1996). Indeed, the application of genetic algorithms as a decision aid has spread across a wide range of disciplines. Such applications include notable works in engineering (Hodge *et al*., 2006; Gosselin *et al*., 2009), computer-aided process planning (Salehi and Ta-vakkoli-Moghaddam, 2009), design of supply chain dis-tribution systems (Jawahar and Balaji, 2009), facility layout planning (Mak *et al*., 1998; Singh and Sharma, 2006), and manufacturing cell formation (Mak *et al*., 2000), etc. The improved genetic approach developed in this paper consists of two heuristics to ensure solution feasibility and a new selection method to prevent the optimization search process from converging prematu-rely to local optimal solutions. Extensive computational experiments are also conducted using a set of randomly generated test problems to evaluate the effectiveness of the proposed approach.

The remainder of the paper is organized as follows. Section 2 presents the problem under investigation and introduces the method for evaluating customer flexibility. The detailed formulation of the mathematical model is also presented. Section 3 elaborates the development of the new genetic algorithm. In section 4, computational experiments are conducted using a set of randomly generated test problems to validate the efficiency of the de-veloped genetic algorithm. Finally, conclusions are given in section 5.

### 2. PROBLEM STATEMENT AND MODEL FORMULATION

#### 2.1 Problem Statement

Figure 1 illustrates the supply chain network under consideration. A manufacturer aims to satisfy the various customer requirements by producing multiple families of products, with multiple product variants in each product family. These product families may share common and non-common raw materials and component modules. Since suppliers usually have limited raw materials and component modules capacities, it is important to determine the supply quotas to be allocated to each supplier to support the production of the product variants in the various product families.

**Figure 1.**Supply chain network.

#### 2.2 Customer Flexibility Evaluation

In this study, a multi-level GBOM modular product structure (Jiao, 2000) is used to calculate the amount of raw materials, component modules and production resources required to manufacture the products, in order to satisfy the various customers’ demands. Figure 2 shows an example of the product structure of a set of product variants belonging to a simple product family. A three-level GBOM product structure is used. Two OR modules and one AND module is placed at level 3. The intermediate parts are located in level 2 and the final product is located in level 1. K11 and K21 represent the desired OR module options which constitute the desired product variant. There are up to six product variants in this family. The number six is the maximum number of different combinations of the OR module options.

**Figure 2.**Generic-bill-of-material for a product family.

In addition, customer flexibility is characterized by both the range of the customer’s indifference to a product attribute (e.g., a specification), and his/her response to changes in this attribute. To facilitate the characterization of customer flexibility through range and response, the following notations are given:

##### 2.2.1 Customer flexibility range

Customer flexibility centers on product attributes, with its customer flexibility range represented as: A= [ *a _{1 }*, L ,

*a*] and its element

_{h }*a*= [

_{h }*g*|

_{h }*g*∈

_{h}*G*]. Here

_{h }*A*is a supper set that contains

*H*elements indicating

*H*different product attributes

**.**

*G*

_{H}*is the set which specifies a feasible range of attribute levels (options) for product attribute*

_{ }*h*.

##### 2.2.2 Customer flexibility response

It is very difficult to represent customer flexibility response since a product specification involves multiple product attributes and requires the modeling of customer satisfaction. The problem could be solved by formulating customer preference functions for the product attributes based on utility theory. However, the utility based preference measure is ambiguous by nature. A fuzzy variable (Liu, 2002) is, therefore, used to denote the subjective assessment of the level of each product attribute. The credibility density function of this fuzzy variable is, then, utilized to denote customer preference functions which measure the utility value corresponding to a particular product attribute level.

Figure 3 illustrates an example of a preference function denoted by a credibility density function of a triangle fuzzy variable characterizing different diameter values of a screw. It indicates that the desired diameter value is 1 cm, with its utility value equal to 1.0. The diameter values falling inside the range (0.25-1.75 cm) are acceptable but they have different utility values (less than 1.0).

**Figure 3.**Illustrative example of a preference function.

##### 2.2.3 Customer flexibility evaluation

With the utility values measuring the various levels of each product attribute, product attributes can be evaluated and integrated. A general utility value called customer satisfaction can, therefore, be obtained for a particular product variant by aggregating the utility values of all involved product attributes into a single, overall utility measure. Since customer preferences are often subjective and imprecise by nature, this paper proposes a fuzzy multi-attribute utility approach to evaluate customer flexibility. To facilitate the presentation of this method, the following notations are used:

Since additive utility functions are widely used in marketing research, the aggregated utility value *U _{ni }*for product variant

*ni*can be computed by using a fuzzy additive multi-utility function according to the equation

#### 2.3 Model Formulation

A new mixed integer programming (MIP) model describing the characteristics of the supplier selection and order allocation problem is developed. The manufacturer aims to provide *n *products by utilizing resources provided by *m *capacity-constrained suppliers in a multi-period planning horizon. These suppliers differ in their price, quality, on-time delivery, and trust levels. Since the resources for producing the customers’ desired product variants may be insufficient, the customers are willing to accept the less desirable productvariants given the price discounts offered by the manufacturer.

##### 2.3.1 Notations

The notations used in the mathematical model are presented below:

*n* = Product family index*N* = Number of product families*i* = Product variant index in each family*I **n *= Number of product variants in product family *nk* = OR module index

*K*= Number of OR modules

*s*= Option index of each OR module

*Sk*= Number of options of OR module

*k*

*l*= AND module index

*L*= Number of AND modules

*m*= Supplier index

*M*= Number of suppliers

*t*= Time period index

Τ = Number of time periods in the planning horizon

*ni*= Product variant

*i*in family

*n*

*k*

*s*= Option level

*s*of OR module

*k*, for simplicity, name it OR module option

*ks*

##### 2.3.2 Parameters

The parameters of the proposed model are listed below:

= Capacity of supplier *m *for OR module option *k**s *in period *t*

*m*for AND module

*l*in period

*t*

= Supplier

*m*’s selling price for OR module option

*ks*in period

*t*

= Supplier

*m*’s selling price for AND module

*l*in period

*t*

= Expected market demand for product family

*n*in period

*t*

= Number of units of OR module

*k*needed to product one unit of product variant

*ni*

= Number of units of OR module option

*ks*needed to product one unit of product variant

*ni*

= Number of units of the AND module

*l*needed to product one unit of final product variant

*I*in product family

*n*

= Fixed cost of marking down less desirable product variant

*ni*

*ni*

= Setup cost of product variant

*ni*

= Supplier

*m*’s minimum budget in period

*t*

*m*’s trust level in time period

*t*

= Transaction cost of supplier

*m*in time period

*t*

= Retail price for the product variant

*ni*in period

= Inventory holding cost for OR module option

*ks*

= Inventory holding cost for AND module

*l*

*ni*

= Late delivery days of supplier

*m*in period

*t*

*n*

*i*for one time unit

= Quality penalty for one unit of the modules per percent below 100%

= Supplier

*m*’s quality level for OR module option

*ks*in period

*t*

*m*’s quality for AND module

*l*in period

*t*

##### 2.3.3 Decision variables

The decision variables of the proposed model are listed as follows:

= Quantity of product variant *ni *produced in period *t*

= Quantity of product variant *ni *sold in period *t*= Order quantity of OR module option

*k*

*s*from supplier

*m*in period

*t*

= Order quantity of AND module *l *from supplier *m *in period *t*

= Inventory level of OR module option *ks *in period *t*= Inventory level of AND module

*l*in period

*t*

= Inventory level of product variant

*ni*in period

*t*

##### 2.3.4 Mathematical model

The mathematical model for the integrated supplier selection and order allocation problem is formulated as follows:

##### Objective:

Maximize total profit =

where

##### Subject to:

The objective is to maximize the manufacturer’s total profit which is equal to the total revenue generated by selling the product variants minus the total cost. The total cost is the sum of the cost for purchasing raw materials, the cost for production and production setup, the cost for transaction with suppliers, the cost for marking down less desirable product variants, the cost for quality penalty and tardiness penalty, and the cost for inventory holding for both raw materials and product variants. The constraints are comprised of suppliers’ capacity constra-ints and budget constraints, GBOM constraints, demand satisfaction constraints, and inventory balance constraints.

### 3. AN IMPROVED GENETIC ALGORITHM

The proposed supplier selection and order allocation problem is a very complex problem which is NP-hard by nature. This necessitates the development of an efficient and effective optimization algorithm to locate optimal solutions. Hence, this paper develops an impro-ved genetic algorithm equipped with two problem specific repair heuristics and a new selection method to solve the problem. The details of the genetic operators, the representation of the chromosomes and the repair heuristics are presented in the subsequent sections.

#### 3.1 Chromosome Representation

A two-part chromosome structure is used for the illustrative example which consists of two product families with GBOMs as shown in Figure 4. The first part determines the production quantities of the product variants in each family. The second part represents the order allocation of the modules among the selected suppliers under the production plan indicated in the first part.

**Figure 4.**Generic bill-of-materials for two product families.

Figure 5 illustrates an example of a feasible chromosome for representing a production plan for these two product families with 4 and 2 product variants, respectively, and the order allocation of the 4 modules among 3 suppliers.

**Figure 5.**Chromosome structure.

#### 3.2 Repair Heuristics

Since it is not easy to randomly generate the first part of a feasible chromosome satisfying the demand requirements, the GBOM and supplier capacity constra-ints, two problem specific repair heuristics are developed to ensure the feasibility of the solutions represented by the chromosomes.

##### Heuristic I:

meeting** **customer demands

##### Step 1:

Calculate the sum of the production quantity of each product variant in each product family. If the demand is not satisfied, then use step 2, otherwise use step 3.

##### Step 2:

Randomly generate *I n *real numbers between 0 and 1 for each product family in each time pe- riod using *ran**d**i *(0, 1) and calculate their sum. Multiply the unmet demand of each product family denoted by ( *i *= 1, 2, L, *I **n *), and then obtain the modified production quantity for product variant *ni *by

##### Step 3:

Find min () and reduce the production quantity of the *n,i* corresponding product variant by min () where is the oversupply of the product demand. Repeat this process until = 0 .

##### Heuristic II:

meeting GBOM and capacity constraints

The determination of the respective production quantities of the product variants is also governed by the availability of the various OR module options, and the relationships between these OR module options and the product variants as indicated in their respective GBOMs. A repair heuristic is, therefore, developed and applied to the randomly generated chromosomes in Heuristic I to ensure solution feasibility. Details of the heuristic are described as follows:

##### Step1:

Calculate the deficient capacity for OR module option *ks *in period *t *(denoted by *) based on the production plan generated in Heuristic I using the equation*

If > 0, i.e., the amount of OR module option *ks *required in period *t *for the production of the various product variants exceeds its total capacity, which im- plies that the production quantities of certain product variants that utilize this module option need to be reduced. If < 0, there is surplus capacity for this OR module option, and the production quantities of certain product variants can be increased.

##### Step 2:

Reduce the production quantities of the low-pro-fit product variants

a) If find for all product variant *ni *that utilizes this OR module option, and reduce its production quantity by

b) If find for all product variants *ni *that utilize this OR module option, then reduce the production quantity of this product variant to zero.

c) Calculate and repeat (a) or (b) until all ≥ 0

However, the results obtained by using procedures (a), (b), and (c) may lead to violation of some custom- ers’ demand constraints. The following procedure is, therefore, adopted to increase the production quantities of the high-profit product variants.

##### Step 3:

However, the results obtained by using procedures (a), (b), and (c) may lead to violation of some customers’ demand constraints. The following procedure is, therefore, adopted to increase the production quantities of the high-profit product variants.

a) List all the OR modules options according to 11, 12, …, 1*S*1 , 21, 22, …, 2*S*2 , …, *K*1 , *K** *2 , …, *KSk *. Starting from the first one, for any > 0, find and increase the production quantity of the corresponding product variant by where is the unmet demand of the product family.

b) Calculate for all OR module options that can be used to produce the product variant *ni *in step 3(a), i.e., *B**niks *> 0. If < 0, find the product variant with the second highest profit, repeat (a) and (b), until otherwise, move to the next OR module option.

c) Repeat (a) and (b) until the demand is satisfied.

#### 3.3 Fitness Evaluation

In the evaluation process, the fitness value is calculated, which is the objective function for maximizing the manufacturer’s profit. The first part of the chromosome is determined by using heuristics I and II to ensure solution feasibility. The second part is related to the allocation of orders among the suppliers for raw materials and module options which can be formulated as the following integer programming problem:

Hence, it can be determined optimally by using the software package “LP_SOLVE.”

#### 3.4 New Selection Method

Genetic algorithms have been extensively used for solving complex problems. In a canonical genetic algorithm, the selection operator is the driving force that leads to chromosomes with higher fitness values and thus better chances to be selected. However, this selection method might also eliminate some “less fit” chromosomes which may carry some good characteristics and useful schema that could produce good offspring when mated with the right match. Motivated by this, a new selection method is developed to prevent the search process from converging prematurely to local optimal solutions.

Figure 6 lists the steps of the proposed new selection method. To form the parents, the procedure selects randomly one chromosome from a subgroup of chromosomes with better fitness values, and it compares the selected chromosome with the best chromosome obtain-ned so far. The chromosome with a better fitness value is, then, selected as a member of the parents. The other member of the parents is randomly selected from the chromosomes outside the subgroup. This method does not only allow interaction with the better chromosomes, but also allows the less fit chromosomes that might carry good schema to have a chance to mate. In so doing, both exploration and exploitation of the solution space are encouraged. The exploitation rate is controlled by selecting an appropriate size for the subgroup. Larger size results in more exploitation and smaller size indicates more exploration. Hence, balance of exploration and exploitation can be realized.

**Figure 6.**Steps of the new selection method.

#### 3.5 Reproduction

After selection, the crossover stimulates the generation of a new pair of child chromosomes. To create a new child chromosome, this paper adopts a uniform crossover operator with a crossover mask which has the same length as the first part of the chromosome. Then LP_SOLVE is used to generate the second part of the chromosome optimally. To avoid premature convergence, a mutation operator is adopted and applied to the first part of the chromosome. For each product variant, a random number ranging between 0 and 1 is generated. The production quantity of product variant

#### 3.6 Flowchart of the Improved Genetic Algorithm

The procedures of the improved genetic algorithm are presented in Figure 7.

**Figure 7.**Flow chart of the improved genetic algorithm.

### 4. COMPUTATIONAL RESULTS

Extensive computational experiments were carried out to evaluate the effectiveness of the proposed genetic algorithm (GA).

#### 4.1 Test Problems and Parameters

A set of 54 test problems was generated randomly based on real life characteristics. The number of product families considered ranges from 4 to 8, each has a unique product structure depicted in its GBOM. Multiple time periods ranging from 1 to 7, and multiple suppliers, ranging from 3 to 6 are considered. The number of OR modules and AND modules are generated randomly between 2 and 6. Each OR module has several options ranging from 1 to 6. The parameters of the proposed GA were determined experimentally using a small set of sample problems. The population size is 30 and the termination condition is 100 iterations. The crossover and mutation probabilities are fixed to 0.6 and 0.02, respectively. Visual C++ 6.0 programming language is used on a computer equipped with Inter Pentium 1.56 GHz CPU and 1024 MB RAM. The size of the subgroup, *Y*, formed by the better chromosomes remains unchanged in the test problems. To identify a suitable subgroup size, 20 test problems randomly selected from the 54 test problems have been solved with the subgroup size, *Y*, equals to 1, 2, 5, and 10. The results obtained indicate that, when

#### 4.2 Comparisons with ILOG OPL and Canonical Genetic Algorithm

The proposed GA was applied to solve all 54 test problems generated in section 4.1. The results obtained are compared with those obtained by using ILOG OPL (IBM Co., New York, NY, USA), a commercial software for locating global optima for mixed integer programming problems, and by using canonical genetic algorithm (CGA). The size of the subgroup is fixed to 2 (*Y *= 2

**Table 1.**Results of ILOG and the proposed genetic algorithm

### 5. CONCLUSION

Nowadays, customers are often indifferent to certain product specifications and are willing to accept products with less desirable product attributes in exchange for price discounts. It is, therefore, essential for a manufacturer to exploit the advantages of customer flexibility to the full in order to maximize profit. This paper investigated an integrated supplier selection and order allocation problem for a supply chain manufacturing multi-products over a multi-period planning horizon when customer flexibility exists. A fuzzy multi-attribute utility approach was proposed to evaluate customer flexibility which is characterized through range and response. To facilitate mapping customer demand requirements into raw materials and component parts requirements, the structure of the products is described by GBOMs. A novel mathematical model in the form of a mixed integer programming model was developed to assist the manufacturer in selecting suppliers as well as allocating orders to the selected suppliers optimally. The objective is to satisfy the customers’ demand requirements and to maximize its profit subject to various operating constraints. Since the problem is very complex and is NP-hard in nature, an improved genetic algorithm was developed as an optimization tool to solve this challenging problem. Extensive numerical experiments were conducted on a set of randomly generated test problems based on real life characteristics. The results clearly indicated that the proposed genetic algorithm is superior to the canonical genetic algorithm in locating near-optimal solution for small and large scale problems, and that it has similar performance when compared with ILOG OPL, a commercial software, in finding high-quality solutions for small scale problems. When the scale of the problem is large, ILOG OPL cannot locate any solution even after running for a relatively long time.

### ACKNOWLEDGMENTS

The work described in this paper was supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region,

### Reference

2.Goldberg, D. E. (1989), Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-We-sley, Reading, MA.

3.Gosselin, L., Tye-Gingras, M., and Mathieu-Potvin, F. (2009), Review of utilization of genetic algorithms in heat transfer problems, International Journal of Heat and Mass Transfer, 52, 2169-2188.

4.Hodge, B.-M., Pettersson, F., and Chakraborti, N. (2006), Re-evaluation of the optimal operating conditions for the primary end of an integrated steel plant us-ing multi-objective genetic algorithms and Nash equilibrium, Steel Research International, 77, 459-461.

5.Holland, J. H. (1975), Adaptation in Natural and Artifi-cial System: An Introductory Analysis with Ap-plica-tions to Biology, Control, and Artificial Intelligence, University of Michigan Press, Ann Arbor, MI.

6.Jawahar, N. and Balaji, A. N. (2009), A genetic algo-rithm for the two-stage supply chain distribution problem associated with a fixed charge, European Journal of Operational Research, 194, 496-537.

7.Jiao, J., Tseng, M. M., Ma, Q., and Zou, Y. (2000), Ge-neric bill-of-materials-and-operations for high-va-riety production management, Concurrent Engi-nee-ring: Research and Applications, 8, 297-321.

8.Kim, B., Leung, J. M. Y., Park, K. T., Zang, G., and Lee, S. (2002), Configuring a manufacturing firm’s supply network with multiple suppliers, IIE Trans-actions, 34, 663-677.

9.Lamothe, J., Hadj-Hamou, K., and Aldanondo, M. (2006), An optimization model for selecting a product family and designing its supply chain, European Journal of Operation Research, 169, 1030-1047.

10.Liu, B. (2002), Theory and Practice of Uncertain Pro-gramming, Physica-Verlag, Heidelberg, Germany.

11.Mak, K. L., Wong, Y. S., and Wang, X. X. (2000), An adaptive genetic algorithm for manufacturing cell formation, The International Journal of Advanced Manufacturing Technology, 16, 491-497.

12.Mark, K. L., Wong, Y. S., and Chan, F. T. S. (1998), A genetic algorithm for facility layout problems, Com-puter Integrated Manufacturing Systems, 11, 113-127.

13.Michalewicz, Z. (1996), Genetic Algorithms+Data Stru-ctures = Evolution Programs, Springer-Verlag, New York, NY.

14.Salehi, M. and Tavakkoli-Moghaddam, R. (2009), Ap-pli-cation of genetic algorithm to computer-aided pro-cess planning in preliminary and detailed plan-ning, Engineering Applications of Artificial Intelli-gence, 22, 1179-1187.

15.Singh, S. P. and Sharma, R. R. K. (2006), A review of different approaches to the facility layout problems, The International Journal of Advanced Manufacturing Technology, 30, 425-433.

16.Smeltzer, L. R. (1997), The meaning and origin of trust in buyer-supplier relationships, Journal of Supply Chain Management, 33, 40-48.

17.Weber, C. A. and Current, J. R. (1993), A multiobjective approach to vendor selection, European Journal of Operational Research, 68, 173-184.