Abstract

The dynamic facility layout problem (DFLP) is one of the most complex combinatorial optimization challenges. Given that obtaining optimal solutions using exact methods requires substantial time and computational power, researchers often turn to nonconventional optimization techniques to achieve near-optimal solutions. This paper presents a genetic algorithm (GA) enhanced with a local search (LS) procedure for solving DFLPs. The algorithm employs roulette wheel selection (RWS), single-point crossover (SPC), and swap mutation (SM) as its genetic operators, with the 2opt neighborhood search serving as the LS operator. The termination criterion (TC) used in the proposed algorithm is the maximum number of generations. An extensive evaluation of the algorithm's performance was conducted in this research. It was tested on a diverse set of 48 problem instances, representing various problem sizes. To assess the effectiveness of the algorithm, the results produced were compared with those documented in existing literature and benchmarked against the best-known solutions previously reported. This rigorous comparison allows for an evaluation of the algorithm's performance relative to other established methods and state-of-the-art solutions available in the field. Through extensive experimentation on 48 test instances, the algorithm consistently delivers competitive results, achieving solutions within a margin of less than four percent deviation from the best-known solutions across all instances, with an average deviation ranging from 0% to 3.71%. Although the average runtime of the algorithm is provided, its comparison with existing literature is deemed irrelevant due to significant variations in machine configurations. This work introduces a hybrid genetic algorithm (hGA) specifically designed for solving DFLPs. By integrating fundamental genetic operations with a localized search approach, the proposed hGA demonstrates promising capabilities in tackling this complex optimization problem. The outcomes affirm the efficacy of the hGA in swiftly converging to near-optimal solutions for DFLPs, underscoring its potential for practical applications.

Keyword

Dynamic facility layout problem, Hybrid genetic algorithm, Local search, Roulette wheel selection, Swap mutation.

Cite this article

G. VR, C. SR.Optimizing dynamic facility layout problems: genetic algorithm with local search integration . International Journal of Advanced Technology and Engineering Exploration. 2024;11(115):899-915. DOI:10.19101/IJATEE.2023.10102424

Refference

[1]Aziz FA. Manufacturing system. BoD–Books on Demand, 2012.

[2]Tompkins JA, White JA, Bozer YA, Tanchoco JM. Facilities planning. John Wiley & Sons; 2010.

[3]Abdollahi P, Aslam M, Yazdi AA. Choosing the best facility layout using the combinatorial method of gray relation analysis and nonlinear programming. Journal of Statistics and Management Systems. 2019; 22(6):1143-61.

[4]Montoya-torres JR, Aponte A, Rosas P, Caballero-villalobos JP. Applying GRASP meta-heuristic to solve the single-item two-echelon uncapacitated facility location problem. International Journal of Applied Decision Sciences. 2010; 3(4):297-310.

[5]Balakrishnan J, Cheng CH. Dynamic layout algorithms: a state-of-the-art survey. Omega. 1998; 26(4):507-21.

[6]Koopmans TC, Beckmann M. Assignment problems and the location of economic activities. Econometrica: Journal of the Econometric Society. 1957:53-76.

[7]Sahni S, Gonzalez T. P-complete approximation problems. Journal of the ACM. 1976; 23(3):555-65.

[8]Loiola EM, De ANM, Boaventura-netto PO, Hahn P, Querido T. A survey for the quadratic assignment problem. European journal of Operational Research. 2007; 176(2):657-90.

[9]Rosenblatt MJ. The dynamics of plant layout. Management Science. 1986; 32(1):76-86.

[10]Pradeepmon TG, Panicker VV, Sridharan R. A heuristic algorithm enhanced with probability-based incremental learning and local search for dynamic facility layout problems. International Journal of Applied Decision Sciences. 2018; 11(4):352-89.

[11]Balakrishnan J. Solutions for the constrained dynamic plant layout problem. Indiana University; 1991.

[12]Balakrishnan J, Cheng CH. Genetic search and the dynamic layout problem. Computers & Operations Research. 2000; 27(6):587-93.

[13]Braglia M, Zanoni S, Zavanella L. Robust versus stable layout design in stochastic environments. Production Planning & Control. 2005; 16(1):71-80.

[14]Balakrishnan J, Cheng CH. The dynamic plant layout problem: incorporating rolling horizons and forecast uncertainty. Omega. 2009; 37(1):165-77.

[15]Pillai VM, Hunagund IB, Krishnan KK. Design of robust layout for dynamic plant layout problems. Computers & Industrial Engineering. 2011; 61(3):813-23.

[16]Chen GY. Multi-objective evaluation of dynamic facility layout using ant colony optimization. The University of Texas at Arlington; 2007.

[17]Ballou RH. Dynamic warehouse location analysis. Journal of Marketing Research. 1968; 5(3):271-6.

[18]Kim JG, Kim YD. A branch and bound algorithm for locating input and output points of departments on the block layout. Journal of the Operational Research Society. 1999; 50(5):517-25.

[19]Pérez-gosende P, Mula J, Díaz-madroñero M. A bottom-up multi-objective optimisation approach to dynamic facility layout planning. International Journal of Production Research. 2024 ;62(3):626-43.

[20]Urban TL. A heuristic for the dynamic facility layout problem. IIE Transactions. 1993; 25(4):57-63.

[21]Conway DG, Venkataramanan MA. Genetic search and the dynamic facility layout problem. Computers & Operations Research. 1994; 21(8):955-60.

[22]Kaku BK, Mazzola JB. A tabu-search heuristic for the dynamic plant layout problem. INFORMS Journal on Computing. 1997; 9(4):374-84.

[23]Baykasoğlu A, Gindy NN. A simulated annealing algorithm for dynamic layout problem. Computers & Operations Research. 2001; 28(14):1403-26.

[24]Mckendall JAR, Shang J, Kuppusamy S. Simulated annealing heuristics for the dynamic facility layout problem. Computers & Operations Research. 2006; 33(8):2431-44.

[25]Rezazadeh H, Ghazanfari M, Saidi-mehrabad M, Jafar SS. An extended discrete particle swarm optimization algorithm for the dynamic facility layout problem. Journal of Zhejiang University-Science A. 2009; 10:520-9.

[26]Nahas N, Kadi DA, El FMN. Iterated great deluge for the dynamic facility layout problem. CIRRELT; 2010.

[27]Yang CL, Chuang SP, Hsu TS. A genetic algorithm for dynamic facility planning in job shop manufacturing. The International Journal of Advanced Manufacturing Technology. 2011; 52:303-9.

[28]Molla MR, Naznin M, Islam MR. Dynamic facility layout problem using chemical reaction optimization. In 4th international conference on computer, communication and signal processing 2020 (pp. 1-5). IEEE.

[29]Zouein PP, Kattan S. An improved construction approach using ant colony optimization for solving the dynamic facility layout problem. Journal of the Operational Research Society. 2022; 73(7):1517-31.

[30]Palubeckis G, Ostreika A, Platužienė J. A variable neighborhood search approach for the dynamic single row facility layout problem. Mathematics. 2022; 10(13):1-27.

[31]Mckendall A, Hakobyan A. An application of an unequal-area facilities layout problem with fixed-shape facilities. Algorithms. 2021; 14(11):1-14.

[32]Balakrishnan J, Cheng CH, Conway DG, Lau CM. A hybrid genetic algorithm for the dynamic plant layout problem. International Journal of Production Economics. 2003; 86(2):107-20.

[33]Mckendall JAR, Shang J. Hybrid ant systems for the dynamic facility layout problem. Computers & Operations Research. 2006; 33(3):790-803.

[34]Azimi P, Saberi EJ. An efficient hybrid algorithm for dynamic facility layout problem using simulation technique and PSO. Economic Computation & Economic Cybernetics Studies & Research. 2013; 47(4).

[35]Moslemipour G. A hybrid CS-SA intelligent approach to solve uncertain dynamic facility layout problems considering dependency of demands. Journal of Industrial Engineering International. 2018; 14(2):429-42.

[36]Hosseini S, Khaled AA, Vadlamani S. Hybrid imperialist competitive algorithm, variable neighborhood search, and simulated annealing for dynamic facility layout problem. Neural Computing and Applications. 2014; 25:1871-85.

[37]Chen GY. A new data structure of solution representation in hybrid ant colony optimization for large dynamic facility layout problems. International Journal of Production Economics. 2013; 142(2):362-71.

[38]Khajemahalle L, Emami S, Keshteli RN. A hybrid nested partitions and simulated annealing algorithm for dynamic facility layout problem: a robust optimization approach. INFOR: Information Systems and Operational Research. 2021; 59(1):74-101.

[39]Hosseini SS, Azimi P, Sharifi M, Zandieh M. A new soft computing algorithm based on cloud theory for dynamic facility layout problem. RAIRO-Operations Research. 2021; 55:S2433-53.

[40]Guan C, Zhang Z, Zhu L, Liu S. Mathematical formulation and a hybrid evolution algorithm for solving an extended row facility layout problem of a dynamic manufacturing system. Robotics and Computer-Integrated Manufacturing. 2022; 78:102379.

[41]Matai R. A unique discrete formulation for unequal area dynamic facility layout problem. In international conference on industrial engineering and engineering management 2023 (pp. 622-6). IEEE.

[42]Sotamba LM, Peña M, Siguenza-Guzman L. Driver analysis to solve dynamic facility layout problems: a literature review. In international conference on flexible automation and intelligent manufacturing 2024 (pp. 242-9). Springer, Cham.

[43]Pradeepmon TG, Panicker VV, Sridharan R. Genetic algorithm for quadratic assignment problems: application of Taguchi method for optimisation. International Journal of Operational Research. 2020; 38(2):193-220.

[44]Şahin R, Türkbey O. A new hybrid tabu-simulated annealing heuristic for the dynamic facility layout problem. International Journal of Production Research. 2009; 47(24):6855-73.

[45]Mckendall JAR, Liu WH. New tabu search heuristics for the dynamic facility layout problem. International Journal of Production Research. 2012; 50(3):867-78.

[46]Hosseini-nasab H, Emami L. A hybrid particle swarm optimisation for dynamic facility layout problem. International Journal of Production Research. 2013; 51(14):4325-35.

[47]Turanoğlu B, Akkaya G. A new hybrid heuristic algorithm based on bacterial foraging optimization for the dynamic facility layout problem. Expert Systems with Applications. 2018; 98:93-104.