Combining Multi-objective Immune Algorithm and Linear Programming for Double Row Layout Problem
-
摘要: 设备布局对于提高生产效率和降低运营成本具有重要意义. 本文针对半导体加工制造中常见的双行设备布局问题, 提出了一种结合多目标免疫算法和线性规划的双行设备布局方法来同时优化物料流成本和布局面积两个目标. 首先, 建立了问题的混合整数规划模型;其次, 针对问题既含有组合方面(机器排序)又含有连续方面(机器精确位置)的特点, 分别设计了一种多目标免疫算法来获取非支配的机器排序集合, 提出了一种基于线性规划的方法来构造任一非支配机器排序对应的连续的非支配解集;最后, 由所有连续的非支配解来构造最后Pareto解. 实验结果表明, 该方法对于小规模问题能获得最优Pareto解, 对于大规模问题能够获得具有良好分布性的Pareto解且其质量远好于NSGA-II和精确算法获得的解.Abstract: Facility layout is very significant for improving production efficiency and decreasing operational cost. Aimed at the double row layout problem commonly encountered in the context of semiconductor manufacturing, an approach combining a multi-objective immune algorithm with a linear programming is proposed to simultaneously optimize the two objectives of material flow cost and layout area. Firstly, a mix-integer programming model is established for this problem. Secondly, based on the problem's characteristic of involving both combinatorial (machine sequence) and continuous (exact machine position) aspects, a multi-objective immune algorithm is devised to obtain a set of non-dominated machine sequences, and then a linear programming based method is proposed to construct a set of continuous non-dominated solutions for an arbitrary non-dominated machine sequence. Finally, the set of final Pareto solutions is created from all the continuous non-dominated solutions. Experimental results show that for small size problems our approach is able to obtain the optimal Pareto solutions, and for large size problems our approach can achieve Pareto solutions with good distribution, which are far better than those obtained by NSGA-II and an exact approach.
-
[1] Meller R D, Gau K Y. The facility layout problem: recent and emerging trends and perspectives. Journal of Manufacturing Systems, 1996, 15(5): 351-366 [2] [2] Drira A, Pierreval H, Hajri-Gabouj S. Facility layout problems: a survey. Annual Reviews in Control, 2007, 31(3): 255-267 [3] [3] Braglia M, Zanoni S, Zavanella L. Layout design in dynamic environments: strategies and quantitative indices. International Journal of Production Research, 2003, 41(5): 995-1016 [4] [4] Heragu S S, Kusiak A. Machine layout problem in flexible manufacturing systems. Operations Research, 1988, 36(2): 258-268 [5] [5] Solimanpur M, Vrat P, Shankar R. An ant algorithm for the single row layout problem in flexible manufacturing systems. Computers Operations Research, 2005, 32(3): 583-598 [6] [6] Djellab H, Gourgand A. A new heuristic procedure for the single-row facility layout problem. International Journal of Computer Integrated Manufacturing, 2001, 14(3): 270-280 [7] [7] Heragu S S, Kusiak A. Efficient models for the facility layout problem. European Journal of Operational Research, 1991, 53(1): 1-13 [8] [8] Anjos M F, Vannelli A. Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes. INFORMS Journal on Computing, 2008, 20(4): 611-617 [9] [9] Kumar K R, Hadjinicola G C, Lin T L. A heuristic procedure for the single-row facility layout problem. European Journal of Operational Research, 1995, 87(1): 65-73 [10] Datta D, Amaral A R S, Figueira J R. Single row facility layout problem using a permutation-based genetic algorithm. European Journal of Operational Research, 2011, 213(2): 388-394 [11] Kothari R, Ghosh D. Tabu search for the single row facility layout problem using exhaustive 2-opt and insertion neighborhoods. European Journal of Operational Research, 2013, 224(1): 93-100 [12] Samarghandi H, Taabayan P, Jahantigh F F. A particle swarm optimization for the single row facility layout problem. Computers Industrial Engineering, 2010, 58(4): 529-534 [13] Sadrzadeh A. A genetic algorithm with the heuristic procedure to solve the multi-line layout problem. Computers Industrial Engineering, 2012, 62(4): 1055-1064 [14] Singh S P, Sharma R R K. Two-level modified simulated annealing based approach for solving facility layout problem. International Journal of Production Research, 2008, 46(13): 3563-3582 [15] Kouvelis P, Chiang W C, Yu G. Optimal algorithms for row layout problems in automated manufacturing systems. IIE Transactions, 1995, 27(1): 99-104 [16] Gen M, Ida K, Cheng C H. Multirow machine layout problem in fuzzy environment using genetic algorithms. Computers Industrial Engineering, 1995, 29(1-4): 519-523 [17] Sadrzadeh A. A genetic algorithm with the heuristic procedure to solve the multi-line layout problem. Computers Industrial Engineering, 2012, 62(4): 1055-1064 [18] Chung J, Tanchoco J M A. The double row layout problem. International Journal of Production Research, 2010, 48(3): 709-727 [19] Zhang Z Q, Murray C C. A corrected formulation for the double row layout problem. International Journal of Production Research, 2012, 50(15): 4220-4223 [20] Murray C C, Smith A E, Zhang Z Q. An efficient local search heuristic for the double row layout problem with asymmetric material flow. International Journal of Production Research, 2013, 51(20): 6129-6139 [21] Zhang Ze-Qiang, Cheng Wen-Ming. Decomposition strategies and heuristic for double row layout problem. Computer Integrated Manufacturing Systems, 2014, 20(3): 559-568 (张则强, 程文明. 双行布局问题的分解策略及启发式求解方法. 计算机集成制造系统, 2014, 20(3): 559-568) [22] Amaral A R S. Optimal solutions for the double row layout problem. Optimization Letters, 2013, 7(2): 407-413 [23] Turley J. The Essential Guide to Semiconductors. Upper Saddle River, NJ: Prentice Hall, 2002. [24] Murray C C, Zuo X Q, Smith A E. An extended double row layout problem. Progress in Material Handling Research. Charlotte, North Carolina: Material Handling Industry of America Press, 2012. [25] Chow C K, Yuen S Y. A multiobjective evolutionary algorithm that diversifies population by its density. IEEE Transactions on Evolutionary Computation, 2012, 16(2): 149-172 [26] Kong Wei-Jian, Chai Tian-You, Ding Jin-Liang, Wu Zhi-Wei. A real-time multiobjective electric energy allocation optimization approach for the smelting process of magnesia. Acta Automatica Sinica, 2014, 40(1): 51-61(孔维键, 柴天佑, 丁进良, 吴志伟. 镁砂熔炼过程全厂电能分配实时多目标优化方法研究. 自动化学报, 2014, 40(1): 51-61) [27] Han Min, Liu Chuang, Xing Jun. A multi-objective evolutionary algorithm based on membrane system theory. Acta Automatica Sinica, 2014, 40(3): 431-438 ( 韩敏, 刘闯, 邢军. 一种基于膜系统理论的多目标演化算法. 自动化学报, 2014, 40(3): 431-438) [28] Zuo Xing-Quan, Mo Hong-Wei. Immune Scheduling Principles with Applications. Beijing: Science Press, 2013. (左兴权, 莫宏伟. 免疫调度原理与应用. 北京: 科学出版社, 2013.) [29] Zuo X Q, Tan W, Lin H P. Cigarette production scheduling by combining workflow model and immune algorithm. IEEE Transactions on Automation Science and Engineering, 2014, 11(1): 251-264 [30] Zuo X Q, Mo H W, Wu J P. A robust scheduling method based on a multi-objective immune algorithm. Information Sciences, 2009, 179(19): 3359-3369 [31] Qi Y T, Liu F, Liu M Y, Gong M G, Jiao L C. Multi-objective immune algorithm with Baldwinian learning. Applied Soft Computing, 2012, 12(8): 2654-2674 [32] Yu M, Zuo X Q, Murray C C. A tabu search heuristic for the single row layout problem with shared clearances. In: Proceedings of the 2014 IEEE Congress on Evolutionary Computation. Beijing, China: IEEE, 2014. 819-825 [33] de Castro L N, Von Zuben F J. Learning and optimization using the clonal selection principle. IEEE Transactions on Evolutionary Computation, 2002, 6(3): 239-251 [34] Miettinen K. Nonlinear Multiobjective Optimization. Boston: Kluwer Academic Publishers, 1999 [35] Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197 [36] Aiello G, Enea M, Galante G. A multi-objective approach to facility layout problem by genetic search algorithm and electre method. Robotics and Computer-Integrated Manufacturing, 2006, 22(5-6): 447-455
点击查看大图
计量
- 文章访问数: 1962
- HTML全文浏览量: 48
- PDF下载量: 1330
- 被引次数: 0