Solving Facility Rearrangement Problem Using a Genetic Algorithm and a Heuristic Local Search
 Author: Suzuki Atsushi, Yamamoto Hisashi
 Organization: Suzuki Atsushi; Yamamoto Hisashi
 Publish: Industrial Engineering and Management Systems Volume 11, Issue2, p170~175, 30 June 2012

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 subproblems: 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 twostep 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 twostep GA (Suzuki and Yamamoto, 2010). The effectiveness of the proposed procedure using GA and HLS is demonstrated in a numerical experiment.
2. PROBLEM DEFINITION
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 costC _{max}.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 tor(i, j) (0 ≤r(i, j) ≤ 1) . It means that the production process at facilityi is optimized to the facility and the same efficiency will be not put out at other facility (facilityj ). Naturally, if facilityj is similar to facilityi in specifications and operation conditions, it may becomer(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 facilityj , the new production of facilityj can be expressed in the following Eq.:In this model, the condition of facility
i (running or stopping) and shifting of production operation from facilityi to facilityj must be decided. For representation of condition of facility and integration of facilities, Eqs. (10) and (11) are used:If
x(i) = 1, facilityi is not integrated, and ifx(i) = 0, facilityi must be integrated to any one of other facilities, as the following Eq.:The cost reducing ratio
Rc can be given byC _{max} and current cost as Eqs. (13) and (14):The coat of rearranged facilities is estimated by Eq. (15):
In the cases of
n < 20 andRc ≥ 0.90, excellent alternatives can be found by using evolutionary improvement procedure (Suzukiet al ., 2009). However, in the cases ofn ≥ 20 andRc < 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. SOLVING PROCEDURE
3.1 Search Strategy
In section 2.2 of this paper, FRP can be represented as a 01 (binary) programming model. In this manner, simultaneous searching of
x(i) andy(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 ofy(i, j) is dealt as sub problem under the one set ofx(i) (Figure 1).In the proposed procedure,
x(i) (i =1,…,n ) are searched by GA andy(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 ofx(i) is given by probability ofx(i) =1 based onRc value. Then values ofy(i, j) for each individual are generated based onx(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 searchingx(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 ,P_{select}( is estimated as Eq. (17):h )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 ofi =1, …,n ？ 1 .The mutation is performed as inversing 1 to 0 at any
x(i) on mutation probability. If allx(i) = 0 then anyx(i) = 1. If allx(i) = 1 thenx(i) = 0. As other operation, ifthen 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 <n_{0} <n ? 3 HLS is carried outin 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 Y_{current} (a current alternative). In the next step, the neighbor Y_{nb} is generated. For example, values ofx(i) (i =1, ^{…}, 6 ) are given as follows:(
x _{1}x _{2}x _{3}x _{4}x _{5}x _{6} ) = (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 Y_{current} 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 Y_{nb} can be generated:
If this Y_{nb} improves Y_{current}, Y_{current} is replaced by Y_{nb} 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. NUMERICAL EXPERIMENT
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 / C_{init} ) , were solved by GA HLS and the twostep 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 probabilityPc = 1.00, mutation probabilityPm = 0.1, population sizen_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 2step GA. In the cases of
Rc = 0.95 and 0.90, OFV and cost are similar values. In the cases ofRc = 0.50, 0.60, and 0.70, OFVs by GA+HLS are very excellent than 2step GA. It is demonstrated that the proposed method, GA+HLS, is superior to 2 step GA of the previous method.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.

[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 2step GA (mean of OFVs and cost values)