Hybrid Genetic Algorithm and Variable Neighborhood Search for Dynamic Facility Layout Problem

Md Sanuwar Uddin

Department of Mechanical Engineering, Bangladesh University of Engineering and Technology (BUET), Dhaka, Bangladesh.

DOI: 10.4236/ojop.2015.44015                

Abstract

This paper presents a novel hybrid metaheuristic GA-VNS matching genetic algorithm (GA) and variable neighborhood search (VNS) to the dynamic facility layout problem (DFLP). The DFLP is a well-known NP hard problem which aims at assigning a set of facilities to a set of locations over a time planning horizon so that the total cost including material handling cost and re-arrangement cost is minimized. The proposed hybrid approach in this paper elegantly integrates the exploitation ability of VNS and exploration ability of GA. To examine the performance of the proposed hybrid approach, a set of instance problems have been used from the literature. As demonstrated in the results, the GA-VNS is mighty of attaining high quality solution. Compared with some state-of-the-art algorithms, our proposed hybrid approach is competitive.

Keywords

Dynamic Facility Layout, Genetic Algorithm, Material Handling

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	McKendall Jr., A.R., Shang, J. and Kuppusamy, S. (2006) Simulated Annealing Heuristics for the Dynamic Facility Layout Problem. Computer and Operations Research, 33, 2431-2444. http://dx.doi.org/10.1016/j.cor.2005.02.021
[2]	Rosenblatt, M.J. (1986) The Dynamic of Plant Layout. Management Science, 32, 76-86. http://dx.doi.org/10.1287/mnsc.32.1.76
[3]	Lacksonen, T.A. and Enscore, E.E. (1993) Quadratic Assignment Algorithms for the Dynamic Layout Problem. International Journal of Production Research, 31, 503-517. http://dx.doi.org/10.1080/00207549308956741
[4]	Baykasoglu, A. and Gindy, N.N.Z. (2001) A Simulated Annealing Algorithm for Dynamic Facility Layout Problem. Computers & Operations Research, 28, 1403-1426. http://dx.doi.org/10.1016/S0305-0548(00)00049-6
[5]	Balakrishnan, J., Cheng, C.H., Conway, D.G. and Lau, C.M. (2003) A Hybrid Genetic Algorithm for the Dynamic Plant Layout Problem. International Journal of Production Economics, 86, 107-120. http://dx.doi.org/10.1016/S0925-5273(03)00027-6
[6]	Dunker, T., Radons, G. and Westkamper, E. (2005) Combining Evolutionary and Dynamic Programming for Solving a Dynamic Facility Layout Problem. European Journal of Operational Research, 165, 55-69. http://dx.doi.org/10.1016/j.ejor.2003.01.002
[7]	Dunker, T., Radons, G. and Westkamper, E. (2003) A Coevolutionary Algorithm for a Facility Layout Problem. International Journal of Production Research, 41, 3479-5300. http://dx.doi.org/10.1080/0020754031000118125
[8]	McKendall Jr., A.R. and Shang, J. (2006) Hybrid Ant Systems for the Dynamic Facility Layout Problem. Computers and Operations Research, 33, 790-803. http://dx.doi.org/10.1016/j.cor.2004.08.008
[9]	McKendall Jr., A.R. and Hakobyan, A. (2010) Heuristics for the Dynamic Facility Layout Problem with Unequal-Area Departments. European Journal of Operational Research, 201, 171-182. http://dx.doi.org/10.1016/j.ejor.2009.02.028
[10]	Chen, G.Y.-H. (2013) A New Data Structure of Solution Representation in Hybrid Ant Colony Optimization for Large Dynamic Facility Layout Problems. International Journal of Production Economics, 142, 362-371. http://dx.doi.org/10.1016/j.ijpe.2012.12.012
[11]	Guan, J. and Lin, G. (2016) Hybridizing Variable Neighborhood Search with Ant Colony Optimization for Solving the Single Row Facility Layout Problem. European Journal of Operational Research, 248, 899-909. http://dx.doi.org/10.1016/j.ejor.2015.08.014
[12]	Baykasoglu, A., Dereli, T. and Sabuncu, I. (2006) An Ant Colony Algorithm for Solving Budget Constrained and Unconstrained Dynamic Facility Layout Problems. Omega, 34, 385-396. http://dx.doi.org/10.1016/j.omega.2004.12.001
[13]	Sahin, R., Ertogral, K. and Turkbey, O. (2010) A Simulated Annealing for the Dynamic Layout Problem with Budget Constraint. Computers and Industrial Engineering, 59, 308-313. http://dx.doi.org/10.1016/j.cie.2010.04.013
[14]	Ulutas, B.H. and Kulturel-Konak, S. (2012) An Artificial Immune System Based Algorithm to Solve Unequal Area Facility Layout Problem. Expert Systems with Applications, 39, 5384-5395. http://dx.doi.org/10.1016/j.eswa.2011.11.046
[15]	Komarudin and Wong, K.W. (2010) Applying Ant System for Solving Unequal Area Facility Layout Problems. European Journal of Operational Research, 202, 730-746. http://dx.doi.org/10.1016/j.ejor.2009.06.016
[16]	Ripon, K.S.N., Glette, K., Khan, K.N., Hovin, M. and Torresen, J. (2013) Adaptive Variable Neighborhood Search for Solving Multi-Objective Facility Layout Problems with Unequal Area Facilities. Swarm and Evolutionary Computation, 8, 1-12. http://dx.doi.org/10.1016/j.swevo.2012.07.003
[17]	Kulturel-Konak, S. (2012) A Linear Programming Embedded Probabilistic Tabu Search for the Unequal-Area Facility Problem with Flexible Bays. European Journal of Operational Research, 223, 614-625. http://dx.doi.org/10.1016/j.ejor.2012.07.019
[18]	Hosseini, S., Al Khaled, A. and Vadlamani, S. (2014) Hybrid Imperialist Competitive Algorithm, Variables Neighborhood Search, and Simulated Annealing for Dynamic Facility Layout Problem. Neural Computing and Applications, 25, 1871-1885. http://dx.doi.org/10.1007/s00521-014-1678-x
[19]	Hosseini, S. and Al Khaled, A. (2014) A Survey on the Imperialist Competitive Algorithm Metaheuristic: Implementation in Engineering Domain and Directions for Future Research. Applied Soft Computing, 24, 1078-1094. http://dx.doi.org/10.1016/j.asoc.2014.08.024
[20]	Vadlamani, S. and Hosseini, S. (2014) A Novel Heuristic Approach for Solving Aircraft Landing Problem with Single Runway. Journal of Air Transport Management, 40, 144-148. http://dx.doi.org/10.1016/j.jairtraman.2014.06.009
[21]	Al Khaled, A. and Hosseini, S. (2015) Fuzzy Adaptive Imperialist Competitive Algorithm for Global Optimization. Neural Computing and Applications, 26, 813-825. http://dx.doi.org/10.1007/s00521-014-1752-4
[22]	Hosseini, S., Barker, K. and Ramirez-Marquez, J.E. (2016) A Review of Definitions and Measures of System Resilience. Reliability Engineering and System Safety, 145, 47-61. http://dx.doi.org/10.1016/j.ress.2015.08.006
[23]	Hosseini, S., Khaled, A. and Jin, M. (2012) Solving Euclidean Minimal Spanning Tree Problem Using a New Meta-Heuristic Competitive Algorithm (ICA). 2012 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), Hong Kong, 10-13 December 2012, 176-181. http://dx.doi.org/10.1109/ieem.2012.6837725
[24]	Khaled, A., Jin, M., Clarke, D.B. and Hoque, M.A. (2015) Train Design and Routing Optimization for Evaluating Criticality of Freight Railroad Infrastructures. Transportation Research Part B: Methodological, 71, 71-84. http://dx.doi.org/10.1016/j.trb.2014.10.002
[25]	Mamun, A.A., Khaled, A.A., Ali, S.M. and Chowdhury, M.M. (2012) A Heuristic Approach for Balancing Mixed-Model Assembly Line of Type I Using Genetic Algorithm. International Journal of Production Research, 50, 5106-5116. http://dx.doi.org/10.1080/00207543.2011.643830
[26]	Khaled, A.A., Kumar Paul, S., Kumar Chakraborty, R.K. and Ayuby, S. (2011) Selection of Supplier through Different Multi-Criteria Decision Making Techniques. Global Journal of Management and Business Research, 11, 1-13.
[27]	Masud, A.K.M., Khaled, A.A., Jannat, S., Khan, A.K.M.S.A. and Islam, K.J. (2007) Total Productive Maintenance in RMG Sector A Case Study: Burlington Limited, Bangladesh. Journal of Mechanical Engineering, 37, 62-65.
[28]	Khaled, A.A., Jin, M., Clarke, D.B. and Hoque, M.A. (2013) Determination of Criticality of Freight Railroad Infrastructure Based on Flow Optimization under Heavy Congestion. Transportation Research Board 92nd Annual Meeting, Washington DC, 13-17 January 2013, Paper No. 13-1679.
[29]	Khaled, A.A., Masud, A.K.M., Chowdhury, S.C., Jannat, S. and Obayedullah, M. (2010) Effect of Fiber Diameter Waviness and Wavelength Ratio on the Effective Tensile Elastic Modulus of Carbon Nanotube-Based Polymer Composites. Advanced Material Research, 83, 473-480.
[30]	Burun, E., Erfidan, T. and Ugrum, S. (2006) Improved Power Factor in a Low-Cost PWM Single Phase Inverter Using Genetic Algorithms. Energy Conversion and Management, 47, 1597-1609. http://dx.doi.org/10.1016/j.enconman.2005.08.010
[31]	Mladenovic, M. and Hansen, P. (1997) Variable Neighborhood Search. Computers and Operations Research, 24, 1097-1100. http://dx.doi.org/10.1016/S0305-0548(97)00031-2
[32]	Coelho, I.M., Munhoz, P.L.A., haddad, M.N., Souza, M.J.F. and Ochi, L.S. (2012) A Hybrid Heuristic Based on General Variable Neighborhood Search for the Single Vehicle Routing Problem with Deliveries and Selective Pickups. Electronic Notes in Discrete Mathematics, 39, 99-106. http://dx.doi.org/10.1016/j.endm.2012.10.014
[33]	Ultas, B. and Islier, A.A. (2015) Dynamic Facility Layout Problem in Footwear Industry. Journal of Manufacturing Systems, 36, 55-61. http://dx.doi.org/10.1016/j.jmsy.2015.03.004
[34]	Selvi, S. and Manimegalai, D. (2015) Multiobjective Variable Neighborhood Search Algorithm for Scheduling Independent Jobs on Computational Grid. Egyptian Informatics Journal, 16, 199-212. http://dx.doi.org/10.1016/j.eij.2015.06.001