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
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.
Facility Rearrangement Problem , Facility Planning , Genetic Algorithm , Local Search
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.
In this study, the following problem is considered. In this period, a product is being manufactured by using
nfacilities. 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 iis optimized to the facility and the same efficiency will be not put out at other facility (facility j). Naturally, if facility jis similar to facility iin 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.
The objective function is an equation of total capacity of operating facilities and this should be maximized.
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
iis integrated into facility j, the new production of facility jcan be expressed in the following Eq.:
In this model, the condition of facility
i(running or stopping) and shifting of production operation from facility ito facility jmust be decided. For representation of condition of facility and integration of facilities, Eqs. (10) and (11) are used:
x(i)= 1, facility iis not integrated, and if x(i)= 0, facility imust be integrated to any one of other facilities, as the following Eq.:
The cost reducing ratio
Rccan 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.
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 Rcvalue. 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.
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
his calculated by Eq. (16):
The selection probability of Individual
h, Pselect(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 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
Selection, crossover and mutation are repeated until the number of the generated new individuals (as children) =
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.
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 Y current(a current alternative). In the next step, the neighbor Y nbis 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:
currentmeans 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 nbcan be generated:
If this Y
nbimproves Y current, Y currentis replaced by Y nband 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.
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.
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.
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 2-step GA (mean of OFVs and cost values)