PDF
OA 학술지
Solving Facility Rearrangement Problem Using a Genetic Algorithm and a Heuristic Local Search
ABSTRACT

In this paper, a procedure using a genetic algorithm (GA) and a heuristic local search (HLS) is proposed for solving facility rearrangement problem (FRP). FRP is a decision problem for stopping/running of facilities and integration of stopped facilities to running facilities to maximize the production capacity of running facilities under the cost constraint. FRP is formulated as an integer programming model for maximizing the total production capacity under the constraint of the total facility operating cost. In the cases of 90 percent of cost constraint and more than 20 facilities, the previous solving method was not effective. To find effective alternatives, this solving procedure using a GA and a HLS is developed. Stopping/running of facilities are searched by GA. The shifting the production operation of stopped facilities into running facilities is searched by HLS, and this local search is executed for one individual in this GA procedure. The effectiveness of the proposed procedure using a GA and HLS is demonstrated by numerical experiment.

KEYWORD
Facility Rearrangement Problem , Facility Planning , Genetic Algorithm , Local Search
본문
• ### 1. INTRODUCTION

With changes in the economic and social environment, the volume of production is decreased adapting to the decreasing of demands. If the decrease is a temporary phenomenon, it will be adapted to decrease the production volume by modifying production scheduling and/or human resource assignment. If the modification cannot satisfy the cost constraint, some facilities are stopped and costs for those facilities are reduced. In this study, this problem is represented as a facility rearrangement problem (FRP).

In the area of the facility layout research, dynamic facility layout problems (DFLPs) were formulated and many solving methods have been proposed (Urban, 1993; Conway and Venkataramanan, 1994). In this approach, the number of operating facilities is given, and the material flow values between facilities are changed in each period. Those approaches could not consider operating or stopping of facilities and shifting of operations at stopped facilities.

To consider these matters, the facility rearrangement problem model was built and evolutionary solving methods have been proposed by Suzuki et al. (2006, 2009). FRP is a problem for decision of stopped facilities to maximize production capacity of running facilities under the decreased cost constraint in order to adapt decreasing of the demand of products. FRP can be formulated into an Integer Programming model for maximizing of the total production capacity under the constraint of the total facility operating cost.

FRP can be divided into two sub-problems: the decision problem of stopped/running facilities and the integration problem of production operations in stopped facilities to running facilities. The integration problem can be dealt as a sub problem of the decision problem. In a previous study (Suzuki et al., 2009), this integration problem was solved by enumeration and the decision problem is solved by using an evolutionary procedure. In the cases of 90% of cost constraint and more than 20 facilities, the previous solving method was not effective. To solve such a problem, a two-step genetic algorithm (GA) was proposed (Suzuki and Yamamoto, 2010).

This paper proposes a solving procedure using a GA and a heuristic local search (HLS). Stopping/running of facilities is searched by GA. The shifting of production operation of stopped facilities into running facilities is searched by HLS, and this search is executed for one individual in this GA procedure. This procedure using GA and HLS can find more effective alternatives than the two-step GA (Suzuki and Yamamoto, 2010). The effectiveness of the proposed procedure using GA and HLS is demonstrated in a numerical experiment.

### 2.1 Problem Assumption

In this study, the following problem is considered. In this period, a product is being manufactured by using n facilities. For the next period, the facility operating cost is reduced from managerial estimation. The cost constraint cannot be satisfied by modifying the operating scheduling and human resource assignment, and stopping of some facilities is considered. For the case of recovering of demands, production capacity should be maximized under the total cost constraint, as the maximum value of cost Cmax.

When a facility is stopped, the production operation in the facility is shifted into other running facility, and this shifting is called integration in this study. In the case of integration of facility i to facility j( i ≠ j ), the production efficiency decreases to r(i, j) (0 ≤ r(i, j) ≤ 1) . It means that the production process at facility i is optimized to the facility and the same efficiency will be not put out at other facility (facility j). Naturally, if facility j is similar to facility i in specifications and operation conditions, it may become r(i, j) = 1.

Under the assumption mentioned above, the conditions of running or stopping of facility should be decided to maximize the total production capacity.

### 2.2 Formulation

The objective function is an equation of total capacity of operating facilities and this should be maximized.

subject to

For i = 1, …, n , j = 1, …, n,

cf(j): fixed cost of facility j,

cv(j): variable cost of facility j,

p(j): volume of production in facility j (after integration),

q(i): volume of production in facility i (before integration),

qmax(j) : maximum value of capacity of facility j,

r(i, j): decreasing ratio by integration from facility i to facility j.

For example, if facility i is integrated into facility j, the new production of facility j can be expressed in the following Eq.:

In this model, the condition of facility i (running or stopping) and shifting of production operation from facility i to facility j must be decided. For representation of condition of facility and integration of facilities, Eqs. (10) and (11) are used:

If x(i) = 1, facility i is not integrated, and if x(i) = 0, facility i must be integrated to any one of other facilities, as the following Eq.:

The cost reducing ratio Rc can be given by Cmax and current cost as Eqs. (13) and (14):

The coat of rearranged facilities is estimated by Eq. (15):

In the cases of n < 20 and Rc ≥ 0.90, excellent alternatives can be found by using evolutionary improvement procedure (Suzuki et al., 2009). However, in the cases of n ≥ 20 and Rc < 0.90, the improvement procedure cannot find feasible alternatives because the search area is expanded and the combination of integration alternatives are increased. To find excellent alternatives, new search methods are necessary. In this paper, a procedure using a GA and a HLS is proposed.

### 3.1 Search Strategy

In section 2.2 of this paper, FRP can be represented as a 0-1 (binary) programming model. In this manner, simultaneous searching of x(i) and y(i, j) is not effective because searching of infeasible area is often happened.

In this study, this problem is dealt as searching of x(i) and searching of y(i, j) is dealt as sub problem under the one set of x(i) (Figure 1).

In the proposed procedure, x(i) ( i =1,…, n ) are searched by GA and y(i, j) ( i, j =1, …, n ) are searched by HLS. The flowchart of GA procedure is shown in Figure 2.

At the initialize step, n_pop (population size) individuals are generated. Each value of x(i) is given by probability of x(i) =1 based on Rc value. Then values of y(i, j) for each individual are generated based on x(i) values of the individual to be a feasible integration alternative. Each individual is evaluated by objective function and cost values.

### 3.2 GA Procedure

For searching of x(i), a simple GA is used in this paper. The GA procedure for searching x(i) is shown in Figure 2 and the setting for this GA procedure is shown Table 1.

In the step of selection, two individuals are selected from current population with roulette selection based on the selection probability value of the individual. The fitness of Individual h is calculated by Eq. (16):

The selection probability of Individual h, Pselect(h) is estimated as Eq. (17):

Setting for genetic algorithm procedure

In the step of crossover, a simple (single point) crossover is operated into two selected individuals as exchanging of two vectors of x(i) cut at random point of i =1, …, n ？ 1 .

The mutation is performed as inversing 1 to 0 at any x(i) on mutation probability. If all x(i) = 0 then any x(i) = 1. If all x(i) = 1 then x(i) = 0. As other operation, if

then any x(i) = 1.

Selection, crossover and mutation are repeated until the number of the generated new individuals (as children) = n_pop (population size).

The current population is replaced by new individuals. If elitism preservation is operated, the best individual( s) is adopted as the top of population of the next generation. In this paper, the best one individual is kept at next as the elitism preservation. The individuals of new population are evaluated for objective function value (OFV), cost, fitness and selection probability. This procedure is repeated until termination condition.

### 3.3 HLS Procedure

The HLS procedure is executed for searching of integration alternatives from the stopped facilities into any running facilities under restriction based on the values of x(i). When 5 < n0 < n ? 3 HLS is carried out

in other cases enumeration is executed as Figure 3.

In the first step of the HLS procedure (Figure 4), one alternative of integration, y(i, j) ( i, j =1,..., n ) is randomly generated as Ycurrent (a current alternative). In the next step, the neighbor Ynb is generated. For example, values of x(i) ( i =1, , 6 ) are given as follows:

( x1 x2 x3 x4 x5 x6 ) = (1 0 1 1 0 1)

These values means that facilities 2 and 5 are stopped and other facilities are running. It is assumed that the following one integration alternative is generated from this individual as a current alternative:

This Ycurrent means that the production operations in facilities 2 and 5 are shifted into facilities 1 and 4, respectively. As one example of neighbor, the following Ynb can be generated:

If this Ynb improves Ycurrent, Ycurrent is replaced by Ynb and this operation is iterated. When it is not improved, the searching is restarted, and a new current alternative is generated; and such operation is iterated until termination condition. In this study, this iteration is performed as the maximum time until 1/100 of all calculation time.

### 4.1 Numerical Example

For demonstration of the proposed algorithm, a numerical experiment is executed. Problem data sets are used in Suzuki and Yamamoto (2010).

As experiment, 42 data sets of example problem, that is 7 problems × 6 rates of cost decreasing max (Rc = C / Cinit ), were solved by GA HLS and the two-step GA (Suzuki and Yamamoto, 2010). The calculation by the first setting and the second setting was carried out by the same computation time for solving of one example problem at 3,600 seconds (n = 20), 3,960 seconds (n = 22), 4,320 seconds (n = 24), 4,680 seconds (n = 26), 5,040 seconds (n = 28). In an example problem, calculations are executed five times because the proposed procedure is one of probabilistic search. The parameters are set as crossover probability Pc = 1.00, mutation probability Pm = 0.1, population size n_pop = 20. These values are based on a previous study by Suzuki and Yamamoto (2010) and preliminary experiment. The termination condition is the computation time mentioned above.

### 4.2 Results of Experiment

The numerical experiment was executed in the following computational environment: Pentium4 CPU 3.60 GHz, 2.00 GB RAM, Microsoft Windows XP Pro SP2, BCC++ 5.5. The result of experiment is listed in Table 2.

In all cases, OFVs and cost values by GA+HLS are excellent to values by 2-step GA. In the cases of Rc = 0.95 and 0.90, OFV and cost are similar values. In the cases of Rc = 0.50, 0.60, and 0.70, OFVs by GA+HLS are very excellent than 2-step GA. It is demonstrated that the proposed method, GA+HLS, is superior to 2- step GA of the previous method.

Comparison of by GA HLS and 2-step GA (mean of OFVs and cost values)

### 5. CONCLUSION

This paper proposed a procedure using a genetic algorithm and a heuristic local search to solve the facilities rearrangement problem. The proposed procedure featured the generation method for initial population, a new estimation method of fitness, selection by roulette selection, simple crossover operation, and mutation by 0/1 inversing operation. For the search of integration of production operation in stopped facilities, the heuristic local search is used. The result of the numerical experiment demonstrated the effectiveness of this proposed procedure.

As a future study, use of the searching of y(i, j) other metaheuristics methods, for example, simulated annealing and tabu search method, should be studied. Furthermore, the relationship of problem data characteristics and the effectiveness of solving method should be also considered.

참고문헌
• 1. Urban T. L. (1993) A heuristic for the dynamic facility layout problem [IIE Transactions] Vol.25 P.57-63
• 2. Conway D. G., Venkataramanan M. A. (1994) Genetic search and the dynamic facility layout problem [Computers and Operations Research] Vol.21 P.955-960
• 3. Suzuki A., Yamamoto H., Kainuma Y. (2006) Facility integration problem for resource recycle [Proceedings of International Workshop on Institutional View of SCM] P.329-334
• 4. Suzuki A., Yamamoto H., Tsujimura Y. (2009) Facility rearrangement problem and evolutionary algorithms under variable demands [Proceedings of Meeting of Division C of the Institute of Electrical] P.1198-1203
• 5. Suzuki A., Yamamoto H. (2009) Evolutionary algorithms for solving facility rearrangement problem [Proceedings of 10th Asia Pacific Industrial Engineering and Management System Conference] P.1292-1296
• 6. Suzuki A., Yamamoto H. (2010) A two-step genetic algorithm for solving facility rearrangement problem [Proceedings of 11th Asia Pacific Industrial Engineering and Management System Conference]
이미지 / 테이블
• [ Figure 1. ]  Outline of search procedure. GA: genetic algorithm, HLS: heuristic local search.
• [ Figure 2. ]  Procedure for searching of x(i) by genetic algorithm. HLS: heuristic local search.
• [ Table 1. ]  Setting for genetic algorithm procedure
• [ Figure 3. ]  Procedure of searching of y(i, j). HLS: heuristic local search.
• [ Figure 4. ]  Heuristic local search (HLS) for y(i, j).
• [ Table 2. ]  Comparison of by GA HLS and 2-step GA (mean of OFVs and cost values)
(우)06579 서울시 서초구 반포대로 201(반포동)
Tel. 02-537-6389 ｜ Fax. 02-590-0571 ｜ 문의 : oak2014@korea.kr