Hybrid Genetic Algorithm and Variable Neighborhood Search for Dynamic Facility Layout Problem ()
Received 6 November 2015; accepted 22 December 2015; published 25 December 2015
1. Introduction
The DFLP is the determination of the most efficient arrangement of a number of facilities on the plant floor over multiple periods so that the sum of material handling cost and re-arrangement cost is minimized. The DFLP is an extension of static facility layout problem (SFLP) by considering changes in material flow between facilities over time planning periods. The main issue with DFLP is the existence of time period that makes it more complex than SFLP. Historically, most of the research conducted on facility layout problem has been focused on SFLP type; however nowadays there is a necessity of considering dynamic condition due to demand of flexibility and rapid changes on manufacturing systems. For instance, high tech industries such as electronics and software developments need to be designed under a dynamic environment rather than static due to changes on their product design and functionalities. Therefore the static layout is unreliable and economically inefficient for such industries.
In the DFLP, time period can be expressed in terms of week, month or even year. Solution of SFLP consists of a single layout while it is a series of layout (layout map) with each layout is associated with a particular period for the DFLP [1] . It is important to notice that the DFLP can be converted to SFLP if and only if one of circumstances given below occurs:
・ If material handling costs are extremely larger than re-arrangement costs, then DFLP can be solved as a series of SFLP. In fact, the optimum layout associated with first period can be attained by solving the SFLP using data for the first period and the optimum solution for the second period can be similarly attained by solving the SFLP using data for the second time period and so on.
・ If re-arrangement cost is extremely larger than handling costs, so the handling cost can be simply ignored and the problem can be solved as a series of SFLP.
So the DFLP deals with selecting a set of layout for each period and then deciding whether a facility needs to be re-arranged in the next period or remains fixed. It is clear that the layout configuration tends to be fixed if the re-arrangement cost is high while there are more tendencies toward changing layout plan over the time horizon if the re-arrangement cost is low. The assumptions of DFLP are defined as follows: the flow between facilities is dynamic and deterministic; facilities and locations are all equal size; the distances between facilities are predetermined [1] .
2. Literature Review
The DFLP was initially addressed by Rosenblatt [2] in 1986. He applied dynamic programing (DP) as an exact approach to solve the DFLP. As pointed out previously, DFLP is an extension of SFLP. SFLP with n facilities has (n!) possible layouts (solutions) while the DFLP with n facilities and T time period has (n!)T possible layout maps. It is easy to see that the complexity of DFLP is much larger than SFLP and hence, is computationally intractable. Therefore the results achieved by decent exact methods such as branch and bound are modest. This is the reason there is intense motivation to implement heuristics to solve DFLP. Thereby the major portion of the literature is dedicated to review heuristics approaches.
Lacksonen and Enscore [3] developed a heuristic based on a dynamic programming (DP) approach presented by Rosenblatt [2] . Baykasoglu and Gindy [4] proposed a simulated annealing (SA) for solving the DFLP. Balakrishnan et al. [5] applied a hybrid genetic algorithm. The role of crossover operator is taken by DP and CRAFT is used for the mutation purpose. Dunker et al. [6] extended the GA proposed by Dunker et al. [7] for solving the DFLP with unequal area facilities. The approach is based on integrating dynamic programming and genetic algorithm. Dynamic programming is used for the purpose of evaluating the fitness of layouts. McKendall et al. [1] proposed two simulated annealing SAI, and SAII. SA I is an adaption of SA to the DFLP while the SA II is the same as SAI with extra feature of look-ahead/look-back strategy. McKendall and Shang [8] presented hybrid ant systems (HAS) for the DFLP. Their hybrid consists of two heuristics HAS I and HAS II. HAS I is a simple ant colony algorithm with random decent exchange heuristic while the concept of local search using SA is incorporated with HAS II. McKendall and Hakobyan [9] developed a boundary search technique to place unequal size facilities. The Tabu search (TS) is used to improve the solution. Chen [10] proposed a new data structure to code solution representation. The new data structure improves the solution swapping and sorting activities and also remarkably reduces the computational cost. Guan and Lin. [11] presented a hybrid variable neighborhood search with ant colony optimization for solving the single row facility layout problem. Baykasoglu et al. [12] applied ant colony optimization (ACO) to solve DFLP with budget constraints consideration. Their work considers budget constraint limitation for re-arrangements over planning horizon. Sahin et al. [13] implemented SA for solving the DFLP with budget constraint. Ulutas and Kulturel-Konak [14] presented an artificial immune system (AIS) to solve unequal area facility layout with flexible bay structure. In order to fill the empty space between facilities, the used a new encoding scheme. Komarudin and Wong [15] applied ACO to tackle with DFLP with unequal area facility. The authors used slicing tree representation which prevents restricting too much solution space. Ripon et al. [16] applied an adaptive variable neighborhood search for solving multi-ob- jective facility layout problems with unequal area facilities. Their proposed approach is based on extending conventional local search which determines whether the VNS is used in a GA loop or not. Kulturel-Konak [17] presented a probabilistic TS approach for solving facility layout problem with unequal departments with flexible bay structures. A brief review of developed approach in the related literature is presented in Table 1. Hosseini et al. [18] developed a hybrid imperialist competitive algorithm (ICA), variable neighborhood search (VNS), and simulated annealing (SA) to deal with complexity of DFLP. More applications of meta-heuristic algorithm for facility layout design can be found in [19] -[29] .
The mathematical model of DFLP presented by McKendall et al. [1] is given below:
(1)
s.t.
(2)
(3)
(4)
(5)
(6)
Notations which are used to describe the DFLP model are defined below:
![]()
Table 1. A brief review of the research papers in the related literature.
2.1. Indexes
where T is the number of periods
where N is the number of facilities
2.2. Parameters
cost of material flow between facility i from location j to l in period t
cost of re-arranging facility i from location j to location l at time period t
2.3. Decision Variables
The first term in objective function (1) represents the material handling costs, and the second term is used to obtain the re-arrangement costs. Constraint set (2) guarantees that each location is assigned to only one facility at each time period. Constraint set (3) guarantees that exactly one facility is selected and assigned to each location at each time period. Constraint set (4) adds the re-arrangement cost if a facility re-arranges from its location to a new location within two consecutive time periods. Finally, binary restrictions on the decision variables are presented in (5) and (6).
3. Encoding Scheme
Let’s consider a DFLP instance with 6 facilities and 3 time periods (T = 1, 2, 3) as depicted in Figure 1. Those numbers highlighted with bold fonts represent the facilities, and the numbers with red fonts denote the locations. For instance, in first time period, facilities 3, 4, 6, 5, 2, 1 are assigned to locations 1, 2, 3, 4, 5, and 6 respectively. By considering two consecutive time periods 1 and 2, we can see that the locations of facilities 4 and 6 are changed. In fact, the facility 4 from location 2 at time period 1 is moved to location 3 at time period 2, and facility 6 from location 3 at time period 1 is moved to location 2 at time period 2. So the re-arrangement cost needs to be considered due to those re-arrangements.
The solution to this specific instance can be represented by a vector with size of (1 × 18) as represented in Figure 2.
In general, the solution of DFLP problem with N facilities and T time periods can be represented as in Figure 3.
![]()
Figure 1. A DFLP instance with six facilities and three time periods.
![]()
Figure 2. A solution representation of a DFLP instance with six facilities and three time periods.
![]()
Figure 3. Solution representation for DFLP problem with N departments and ![]()
time periods.
4. Principles of GA
GA is a stochastic optimization technique which is inspired from the biology and evolution process. GA starts with a set of solutions, generated either randomly or using a given heuristicis referred to as the population, and each individual in the population is called a chromosome. The size of the initial population depends on the complexity of problem. A GA with a smaller population is faster but the same time the risk of premature convergence increases. Once the initial population has been generated, the chromosomes are then evaluated by means of fitness function. Parent chromosomes are then selected based on their fitness values to generate new chromosome (child). There are different techniques for selecting parent chromosomes such as roulette wheel selection, tournament selection, and reward-based selection; however the roulette wheel selection is the most commonly used technique. In roulette wheel selection technique [30] , a proportion of the wheel is assigned to each chromosome based on its fitness value. The chromosomes with larger proportion are more likely to be selected. The parent chromosomes are combined using crossover operator to create new chromosomes. New chromosomes are then subjected to random mutation. The purpose of mutation operation is to expand the search directions and prevent the premature convergence. After completing the mutation process, the fitness of new chromosomes is evaluated and crossover and mutation operations start all over. Elitist selection is used to carry better chromosomes from the current generation over to the next generation. Elitist selection may improve the performance of GA but at the same time may results in premature convergence. The evaluation process is repeated until a predetermined condition has been satisfied. The genetic operators used in this context are described as follows:
・ Single point crossover
The proposed single point crossover shame applied in this paper works with single parent instead of two parents. This way of crossover produces feasible offspring and there is no need of checking for solution feasibility. It is also easier to implement. Following are the steps of the proposed single crossover point.
1) Select a parent ![]()
from the population size.
2) Select a time period randomly t, such that![]()
.
3) Select a random number n, such that![]()
.
4) If ![]()
then nth facility will be located at first location in the offspring![]()
.
5) Facilities from n to N in parent ![]()
will be the facilities for offspring ![]()
located at locations from 1 to![]()
.
6) Similarly, facilities from 1 to (![]()
) of parent ![]()
will be the facilities for offspring ![]()
from locations (![]()
) to N.
An illustrative example of single point crossover is depicted in Figure 4.
・ Two exchange (swap) mutation
A cyclic order mutation scheme applied in this paper to modify the locations of facilities in a cyclic order as represented in Figure 5. The following steps are given below:
1) Generate a random time period T such that![]()
, for a given chromosome.
2) Choose two facilities ![]()
within time period T.
3) Swap facilities ![]()
and![]()
.
5. Variable Neighborhood Search
Variable neighborhood search (VNS) is a recent stochastic local search algorithm proposed by Mladenovic and Hansen [31] . Then main idea behind the VNS is to sequentially explore a set of pre-defined neighborhoods to promote a better solution. The VNS benefits from two important aspects; 1) a local optimal of a neighborhood is not essentially the same as a local optimal of another neighborhood structure, 2) A global optimal is the local optimal of all neighborhood structures. The VNS consists of three major steps; shaking, local search and move.
![]()
Figure 4. Illustration of single point crossover operator.
To begin with the VNS, we need to define a set of neighborhood structure ![]()
(![]()
). At each iteration, a random solution is generated by the current neighborhood structure![]()
. Let ![]()
be a random solution generated by first neighborhood of x. Then, a local search is applied to ![]()
to generate a new solution called![]()
. The solution ![]()
is replaced by ![]()
if![]()
. The same search procedure is repeated for ![]()
in the first neighborhood search to improve the solution. If there is no improvement found, then algorithm moves to the next neighborhoods. The template of VNS is illustrated in Figure 6.
Local Searches
Different types of neighborhood structure can be used for the VNS. However, we used three neighborhoods; two exchanges![]()
, three exchanges![]()
, and insertion, ![]()
to avoid increasing computational cost. Therefore, these three neighborhoods are defined as below:
・ Two exchanges ![]()
The two exchange neighborhood structure used in the VNS is functionally same as two exchange (swap) mutation addressed in Section 4.
・ Insertion ![]()
Step 1: Generate a random time period t such that![]()
.
Step 2: For the selected time period t, choose two facilities ![]()
randomly. Let’s denote a and b to be the position of facilities n1 and ![]()
respectively.
Step 3: If a < b, then insert facility ![]()
right after facility![]()
, otherwise insert facility ![]()
right after![]()
.
Example 3: Considering the same instance, the first time period is randomly selected. According to Figure 7(a), the first randomly selected facility is 4 and its corresponding position is 2 (a = 2), and the second randomly selected facility is 5 and its corresponding position is 5 (b = 5). Since ![]()
the facility 4 is inserted right after facility 5.
Insertion operation is depicted in Figure 7(b) when![]()
.
・ Three exchanges ![]()
Step 1: Generate a random time period t such that![]()
.
Step 2: For the selected time period t, choose three facilities ![]()
randomly.
Step 3: Exchange facility ![]()
with facility![]()
, facility ![]()
with facility ![]()
and finally facility ![]()
with facility![]()
.
Example 2: Consider example above, three facilities 4, 2 and 6 are randomly selected, then exchange facility
![]()
Figure 6. Template pseudo code of VNS algorithm.
4 with facility 2, facility 2 with facility 6 and finally facility 6 with facility 2, as shown in Figure 8.
Note that the size of neighborhood ![]()
is![]()
, neighborhood ![]()
is ![]()
and for neighborhood ![]()
is![]()
.
A variety of stopping criteria can be used to terminate the running of VNS, such as maximum allowed elapsed time, maximum number of iterations, etc. In this paper, the VNS continues for the number of iterations since the last improvement reaches at the given maximum of![]()
. Notice that the order of implementing neighborhoods is determined based on their complexity sizes, i.e., the two exchanges and insertion neighborhoods with same size of complexity are considered to be the first and second neighborhoods and three exchanges is considered to be the third neighborhood, because of its larger neighborhood size.
6. Proposed Hybrid Approach
With study of recent works on hybrid metaheurisitcs, it has found that hybrid VNS has dramatically effect on balancing between exploitation and exploration in combinatorial optimization problems [32] -[34] . The proposed hybrid GA-VNS consists in strong cooperation of GA and VNS for the entire course of the algorithm. In each iteration, we split the population into two parts. The splitted parts are evolved using GA and VNS and are then merged together in the updated population and form a new population. Finally, elitism is applied to keep the highest scoring of strings for the next iteration. Similarly, this procedure continues for the next iterations until a stopping criterion is met. The developed flowchart of proposed GA-VNS is exhibited in Figure 9.
The main properties of the hybrid GA-VNS are as follows:
Property 1: Generating the random initial solution.
The hybrid approach begins with a population produced randomly.
Property 2: Diversification using GA
![]()
Figure 9. The developed flowchart of proposed GA-VNS.
It is proven that GA is high capable of shuffling the solution space to prevent search stagnation, but the same time fails to intensify the search toward promising regions of the search space. Nevertheless, hybridization of GA with some suitable local search techniques may overcome the shortcoming feature of each individual algorithm.
Property 3: Intensification using VNS local search.
The concept borrowed by the GA-VNS is that utilizing different neighborhood structures could prevent of getting trapped into local optimal and could also promotes expanding the search scope.
7. Parameters Setting
The driving parameter of proposed hybrid GA-VNS is hybridizing coefficient (HC). HC parameter addresses the percentage of population that is assigned to GA. The proposed hybrid with HC = 1 will be converted to pure GA. It means that the whole population will be evolved with GA, while HC = 0 will be resulted in pure VNS. To take the advantages of features of both GA-VNS, it is clear that HC must be set to some value between 0 and 1 (![]()
). A large value of HC encourages the utilization of GA, resulting in exploration while a small value of HC facilitates the utilization of VNS, resulting exploitation through the course of run. To do balancing between exploration and exploitation strategies, we employed a decreasing linear model to adjust the HC parameter as shown in the following equation:
![]()
(7)
where ![]()
is the hybridizing coefficient at kth iteration, ![]()
and ![]()
are the maximum and minimum values of hybridizing coefficient respectively. Through extensive experiments over different settings, the following set of parameters was found to be effective in terms of goodness of solution.![]()
, ![]()
, maximum number of iterations, population size, crossover rate, and mutation rate were set to be 0.8, 0.2, 600, 300, 0.5, and 0.3 respectively.
8. Experimental Results
To compare the efficiency of the proposed algorithm against some existing algorithms; SAI, SAII [1] , and hybrid ACO [8] , we implemented it in MATLAB 7.8.0.347 (R2009a) and run on a PC with six-core processor 3.30 GHz and 6 GB of RAM. Due to stochastic characteristics of hybrid GA-VNS, five independent replications were run over each problem.
As it can be seen from Table 2, the GA-VNS algorithm obtained the same solution as SAI, SAII, and hybrid ACO for![]()
. It also can be seen that GA-VNS can reaches to a better solution for problems P20 and P23. The relative percentage deviation (RPD) as shown by Equation (8) is used to measure the extent of deviation of each individual algorithm from the best solution found among them.
![]()
(8)
where ![]()
is the best solution found by an algorithm and ![]()
is the best solution found among those three algorithms. The mean plot and the least significant difference (LSD) intervals with 95% confidence interval for the RPD is worked out and presented in Figure 10.
It is necessary to analyze the computational costs of GA-VNS against the other algorithms but it is hard to have a fair comparison due to utilizing different operating systems, programming procedure, and etc. However, the average CPU time for problem P02 with six facilities, 5 time periods and problem P17 with 15 facilities and 5 time periods were 876 s and 1795 s respectively.
![]()
Table 2. Comparison of computational results.
9. Conclusion
In this paper, a new hybrid GA-VNS was introduced to deal with the DFLP. In the proposed hybrid algorithm, the population was splitted into two parts; one part was assigned into the GA and the other part was assigned to the VNS. The percentage of splitting population was adjusted by a parameter called hybridizing coefficient (HC) through the course of run. Extensive computational experiments were performed to identify the most suitable parameters setting. The performance of the GA-VNS was compared against SAI, SAII, and hybrid ACO in terms of the quality of solutions. The results reveal that the hybrid GA-VNS gives good or even better solutions in most of the cases.