Combining Multi-objective Differential Evolution Algorithm and Linear Programming for Multiple Row Facility Layout Problem

doi:10.3901/JME.2019.13.160

Abstract

Abstract: In order to overcome the shortcomings of fixed row number and ignoring spacing constraints between rows in the existing research on multiple row facility layout problem, a multi-objective multiple row facility layout problem model is constructed to optimize material flow cost, layout row number and layout area under the condition of minimum gap constraints, and the model is solved accurately by using Lingo, a mathematical programming software. Based on the multi-objective, multi-constraint and mixed optimization of the proposed problem, a hybrid optimization method of multi-objective differential evolution algorithm and linear programming based on Pareto solution set is proposed. This method uses four-list directly coding method to represent feasible solution, and proposes a decoding method combined with improved line-breaking strategy, which can determine the layout scheme of all possible rows while satisfying boundary constraints. In order to obtain a multi-objective layout result with good convergence and distribution, Pareto method and NSGA-Ⅱ congestion distance mechanism are used to screen external files. The proposed algorithm is applied to solve multiple row facility layout problem with different scales. The effects of three differential evolution modes on the solution quality and efficiency of the proposed method are compared and analysed. Finally, the proposed model and method are applied to two layout examples. The comparative experiments of different algorithms show the effectiveness and superiority of the proposed method.

Key words: evolution algorithm, improve line-wrapping strategies, mixed-integer nonlinear programming, multi-objective optimization, multiple row facility layout problem

CLC Number:

TH165
TP301

GUAN Chao, ZHANG Zeqiang, LI Yunpeng, JIA Lin. Combining Multi-objective Differential Evolution Algorithm and Linear Programming for Multiple Row Facility Layout Problem[J]. Journal of Mechanical Engineering, 2019, 55(13): 160-174.

References

[1] ANJOS M F, VIEIRA M V C. Mathematical optimization approaches for facility layout problems:The state-of-the-art and future research directions[J]. European Journal of Operational Research, 2017, 261(1):1-16.
[2] 刘琼, 赵海飞. 基于多目标果蝇算法面向低碳的车间布局与调度集成优化[J]. 机械工程学报, 2017, 53(11):122-133. LIU Qiong, ZHAO Haifei. Integrated Optimization of workshop layout and scheduling to reduce carbon emissions based on a multi-objective fruit fly optimization algorithm[J]. Journal of Mechanical Engineering, 2017, 53(11):122-133.
[3] TOMPKINS J A, WHITE J A, BOZER Y A, et al. Facilities planning[M]. 4th ed. New York:John Wiely & Sons, 2010.
[4] SADRZADEH A. A genetic algorithm with the heuristic procedure to solve the multi-line layout problem[J]. Computers & Industrial Engineering, 2012, 62(4):1055-1064.
[5] ANJOS M F, FISCHER A, HUNGERLÄNDER P. Solution approaches for equidistant double-and multi-row facility layout problems[J]. Cahier du GERADG 2015, 6:33.
[6] ANJOS M F, FISCHER A, HUNGERLÄNDER P. Solution approaches for the double-row equidistant facility layout problem[M]//London:Operations Research Proceedings 2014. Springer International Publishing, 2016.
[7] AMARAL A R S. A parallel ordering problem in facilities layout.[J]. Computers & Operations Research, 2013, 40(12):2930-2939.
[8] MAADI M, JAVIDNIA M, JAMSHIDI R. Two strategies based on meta-heuristic algorithms for parallel row ordering problem (PROP)[J]. Iranian Journal of Management Studies, 2017, 10(2):467-498.
[9] ANJOS M F, HUNGERLÄNDER P. A semidefinite optimization approach to space-free multi-row facility layout[J]. Zhurnal Mikrobiologii Epidemiologii I Immunobiologii, 2012(5):74-85, 190.
[10] SINGH S P, SHARMA R R K. Two-level modified simulated annealing based approach for solving facility layout problem[J]. International Journal of Production Research, 2008, 46(13):3563-3582.
[11] PANAGIOTISKOUVELIS, WEN-CHYUANCHIANG, GANGYU. Optimal algorithms for row layout problems in automated manufacturing systems[J]. AⅡE Transactions, 1995, 27(1):99-104.
[12] HUNGERLÄNDER P, ANJOS M F. A semidefinite optimization-based approach for global optimization of multi-row facility layout[J]. European Journal of Operational Research, 2015, 245(1):46-61.
[13] SAFARZADEH S, KOOSHA H. Solving an extended multi-row facility layout problem with fuzzy clearances using GA[J]. Applied Soft Computing, 2017, 61:819-831.
[14] CAMP D J V, CARTER M W, VANNELLI A. A nonlinear optimization approach for solving facility layout problems[J]. European Journal of Operational Research, 1992, 57(2):174-189.
[15] HASSAN M M, HOGG G L. A review of graph theory application to the facilities layout problem[J]. Omega, 2009, 15(4):291-300.
[16] 郭源源,王谦,梁峰. 基于粒子群优化算法的车间布局设计[J]. 计算机集成制造系统, 2012, 18(11):2476-2484. GUO Yuanyuan, WANG Qian, LIANG Feng. Facility layout design based on particle swarm optimization[J]. Computer Integrated Manufacturing Systems, 2012, 18(11):2476-2484.
[17] GEN M, IDA K, CHENG C. Multirow machine layout problem in fuzzy environment using genetic algorithms[J]. Computers & Industrial Engineering, 1995, 29(1):519-523.
[18] TAVAKKOLI-MOGHADDAM R, TORABI N, GHASEMINEJAD A. A quaternion firefly algorithm to solve a multi-row facility layout problem[J]. International Journal of Engineering, 2015, 28(11):1605-1613.
[19] TUBAILEH A, SIAM J. Single and multi-row layout design for flexible manufacturing systems[J]. International Journal of Computer Integrated Manufacturing, 2017, 30(12):1316-1330.
[20] ANJOS M F, VIEIRA M V C. An improved two-stage optimization-based framework for unequal-areas facility layout[J]. Optimization Letters, 2014, 10(7):1-14.
[21] FORGHANI K, MOHAMMADI M, GHEZAVATI V. Integrated cell formation and layout problem considering multi-row machine arrangement and continuous cell layout with aisle distance[J]. International Journal of Advanced Manufacturing Technology, 2015, 78(5-8):687-705.
[22] AHMADI A, JOKAR M R A. An efficient multiple-stage mathematical programming method for advanced single and multi-floor facility layout problems[J]. Applied Mathematical Modelling, 2016, 40(9-10):5605-5620.
[23] 张超勇,董星,王晓娟,等. 基于改进非支配排序遗传算法的多目标柔性作业车间调度[J],机械工程学报. 2010, 46(11):156-164. ZHANG Chaoyong, DONG Xing, WANG Xiaojuan, et al. Improved NSGA-Ⅱ for the multi-objective flexible job-shop scheduling problem[J]. Journal of Mechanical Engineering, 2010, 46(11):156-164.
[24] COELLO C A C, PULIDO G T, LECHUGA M S. Handling multiple objectives with particle swarm optimization[J]. IEEE Transactions on Evolutionary Computation, 2004, 8(3):256-279.
[25] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm:NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.
[26] HOSSEINI-NASAB H, FEREIDOUNI S, GHOMI S M T F, et al. Classification of facility layout problems:A review study[J]. International Journal of Advanced Manufacturing Technology, 2018, 94(1-4):957-977.
[27] KUMAR K R,HADJINICOLA G C,LIN T L. A heuristic procedure for the single-row facility layout problem[J]. European Journal of Operational Research, 1995, 87(1):65-73.
[28] 左兴权,王春露,赵新超. 一种结合多目标免疫算法和线性规划的双行设备布局方法[J]. 自动化学报, 2015, 41(3):528-540. ZUO Xingquan, WANG Chunlu, ZHAO Xinchao. Combining multi-objective immune algorithm and linear programming for double row layout problem[J]. ACTA AUTOMATICA SINICA, 2015, 41(3):528-540.
[29] GUAN C, ZHANG Z, LI Y. A flower pollination algorithm for the double-floor corridor allocation problem[J]. International Journal of Production Research, 2019:1-22.
[30] SAHRAEIAN R, NIKSAR E, BEYNAGHI A. Simulated annealing algorithm for facility layout problem with fixed machines and multiple process routes[C]//International Conference on Industrial Engineering and Industrial Management. 2011:835-846.
[31] MIAO Z, XU K. Research of multi-rows facility layout based on hybrid algorithm[C]//International Conference on Information Management, Innovation Management and Industrial Engineering. IEEE, Xi'an, CHINA:2009:553-556.
[32] PRATAP A, AGARWAL S, MEYARIVAN T. Differential evolution enhanced with multiobjective Sorting-Based mutation operators[J]. IEEE Transactions on Cybernetics, 2014, 44(12):2792-2805.
[33] TER-SARKISOV A, MARSLAND S. K-Bit-Swap:A new operator for real-coded evolutionary algorithms[J]. Soft Computing, 2017, 21(20):6133-6142.
[34] CHENG R W, GEN M, TSUJIMURA Y. A tutorial survey of job-shop scheduling problems using genetic algorithms.1. Representation[J]. Computers & Industrial Engineering, 1996, 30(4):983-997.
[35] KOTHARI, RAVI, GHOSH, et al. Tabu search for the single row facility layout problem using exhaustive 2-opt and insertion neighborhoods[J]. European Journal of Operational Research, 2013, 224(1):93-100.
[36] YU M, ZUO X, MURRAY C C. A tabu search heuristic for the single row layout problem with shared clearances[C]//2014 IEEE Congress on Evolutionary Computation (CEC) IEEE. Beijing, CHINA:2014:819-825.
[37] TING C K, SU C H, LEE C N. Multi-parent extension of partially mapped crossover for combinatorial optimization problems[J]. Expert Systems with Applications, 2010, 37(3):1879-1886.
[38] SIMMONS D M. One-Dimensional space allocation:An ordering algorithm[J]. Operations Research, 1969, 17(5):812-826.
[39] ARMOUR G C, BUFFA E S. A heuristic algorithm and simulation approach to relative location of facilities[J]. Management Science, 1963, 9(2):294-309.
[40] 汪一筇,米智伟. SLP和遗传算法结合在车间设备布局中的应用[J]. 计算机工程与应用, 2010, 46(5):211-213. WANG Yiqiong, MI Zhiwei. Method of systematic layout planning improved by genetic algorithm and its application in facility layout[J]. Computer Engineering and Applications, 2010, 46(5):211-213.
[41] 周娜,宓为建,徐子奇,等. 基于改进型自适应遗传算法求解设备多行布局问题[J]. 上海交通大学学报, 2013, 47(12):1924-1929. ZHOU Na, MI Weijian, XU Ziqi, et al. Solution to multi-line layout problems of equipment based on improved adaptive genetic algorithm[J]. Journal of Shanghai Jiaotong University, 2013, 47(12):1924-1929.