一种结合多目标免疫算法和线性规划的双行设备布局方法

左兴权; 王春露; 赵新超

doi:10.16383/j.aas.2015.c140082

一种结合多目标免疫算法和线性规划的双行设备布局方法

doi: 10.16383/j.aas.2015.c140082

左兴权^1,2, ,,
王春露^1,2,
赵新超³

1.
北京邮电大学计算机学院北京 100876;
2.
可信分布式计算与服务教育部重点实验室北京 100876;
3.
北京邮电大学理学院北京 100876

基金项目:

国家自然科学基金(61374204, 61375066)资助

详细信息

作者简介:
王春露北京邮电大学计算机学院副教授.1994年获得哈尔滨工业大学计算机科学与技术专业硕士学位.主要研究方向为计算智能, 云计算, 文件存储系统.E-mail: wangcl@bupt.edu.cn

通讯作者:
左兴权北京邮电大学计算机学院副教授.2004年获得哈尔滨工业大学控制科学与控制工程专业博士学位.主要研究方向为智能优化与调度, 设备布局优化, 进化计算及应用.本文通信作者. E-mail: zuoxq@bupt.edu.cn

计量
- 文章访问数: 2034
- HTML全文浏览量: 48
- PDF下载量: 1337
- 被引次数: 0
出版历程
- 收稿日期: 2014-02-19
- 修回日期: 2014-10-16
- 刊出日期: 2015-03-20

Combining Multi-objective Immune Algorithm and Linear Programming for Double Row Layout Problem

1.
Computer School, Beijing University of Posts and Telecommunications (BUPT), Beijing 100876;
2.
Key Laboratory of Trustworthy Distributed Computing and Service (BUPT), Ministry of Education, Beijing 100876;
3.
School of Science, Beijing University of Posts and Telecommunications, Beijing 100876

Funds:

Supported by National Natural Science Foundation of China (61374204, 61375066)

摘要

摘要: 设备布局对于提高生产效率和降低运营成本具有重要意义. 本文针对半导体加工制造中常见的双行设备布局问题, 提出了一种结合多目标免疫算法和线性规划的双行设备布局方法来同时优化物料流成本和布局面积两个目标. 首先, 建立了问题的混合整数规划模型;其次, 针对问题既含有组合方面(机器排序)又含有连续方面(机器精确位置)的特点, 分别设计了一种多目标免疫算法来获取非支配的机器排序集合, 提出了一种基于线性规划的方法来构造任一非支配机器排序对应的连续的非支配解集;最后, 由所有连续的非支配解来构造最后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.
- Facility layout problem /
- immune algorithm /
- multi-objective optimization /
- linear programming

HTML全文

参考文献(36)

[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

施引文献

资源附件(0)

访问统计

计量

文章访问数: 2034
HTML全文浏览量: 48
PDF下载量: 1337
被引次数: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

留言板

一种结合多目标免疫算法和线性规划的双行设备布局方法

doi: 10.16383/j.aas.2015.c140082

作者简介:
王春露北京邮电大学计算机学院副教授.1994年获得哈尔滨工业大学计算机科学与技术专业硕士学位.主要研究方向为计算智能, 云计算, 文件存储系统.E-mail: wangcl@bupt.edu.cn

通讯作者:
左兴权北京邮电大学计算机学院副教授.2004年获得哈尔滨工业大学控制科学与控制工程专业博士学位.主要研究方向为智能优化与调度, 设备布局优化, 进化计算及应用.本文通信作者. E-mail: zuoxq@bupt.edu.cn

计量

Combining Multi-objective Immune Algorithm and Linear Programming for Double Row Layout Problem

计量

目录

留言板

一种结合多目标免疫算法和线性规划的双行设备布局方法

doi: 10.16383/j.aas.2015.c140082

作者简介: 王春露 北京邮电大学计算机学院副教授.1994年获得哈尔滨工业大学计算机科学与技术专业硕士学位.主要研究方向为计算智能, 云计算, 文件存储系统.E-mail: wangcl@bupt.edu.cn

通讯作者: 左兴权 北京邮电大学计算机学院副教授.2004年获得哈尔滨工业大学控制科学与控制工程专业博士学位.主要研究方向为智能优化与调度, 设备布局优化, 进化计算及应用.本文通信作者. E-mail: zuoxq@bupt.edu.cn

计量

出版历程

Combining Multi-objective Immune Algorithm and Linear Programming for Double Row Layout Problem

计量

出版历程

目录

作者简介:
王春露北京邮电大学计算机学院副教授.1994年获得哈尔滨工业大学计算机科学与技术专业硕士学位.主要研究方向为计算智能, 云计算, 文件存储系统.E-mail: wangcl@bupt.edu.cn

通讯作者:
左兴权北京邮电大学计算机学院副教授.2004年获得哈尔滨工业大学控制科学与控制工程专业博士学位.主要研究方向为智能优化与调度, 设备布局优化, 进化计算及应用.本文通信作者. E-mail: zuoxq@bupt.edu.cn