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

被引:23
作者
左兴权 [1 ,2 ]
王春露 [1 ,2 ]
赵新超 [3 ]
机构
[1] 北京邮电大学计算机学院
[2] 可信分布式计算与服务教育部重点实验室
[3] 北京邮电大学理学院
关键词
设备布局问题; 免疫算法; 多目标优化; 线性规划;
D O I
10.16383/j.aas.2015.c140082
中图分类号
TB491 [规划与设计]; TP18 [人工智能理论];
学科分类号
08 ; 081104 ; 0812 ; 0835 ; 1405 ;
摘要
设备布局对于提高生产效率和降低运营成本具有重要意义.本文针对半导体加工制造中常见的双行设备布局问题,提出了一种结合多目标免疫算法和线性规划的双行设备布局方法来同时优化物料流成本和布局面积两个目标.首先,建立了问题的混合整数规划模型;其次,针对问题既含有组合方面(机器排序)又含有连续方面(机器精确位置)的特点,分别设计了一种多目标免疫算法来获取非支配的机器排序集合,提出了一种基于线性规划的方法来构造任一非支配机器排序对应的连续的非支配解集;最后,由所有连续的非支配解来构造最后Pareto解.实验结果表明,该方法对于小规模问题能获得最优Pareto解,对于大规模问题能够获得具有良好分布性的Pareto解且其质量远好于NSGA-II和精确算法获得的解.
引用
收藏
页码:528 / 540
页数:13
相关论文
共 24 条
[1]   双行布局问题的分解策略及启发式求解方法 [J].
张则强 ;
程文明 .
计算机集成制造系统, 2014, 20 (03) :559-568
[2]   一种基于膜系统理论的多目标演化算法 [J].
韩敏 ;
刘闯 ;
邢军 .
自动化学报, 2014, 40 (03) :431-438
[3]   镁砂熔炼过程全厂电能分配实时多目标优化方法研究 [J].
孔维健 ;
柴天佑 ;
丁进良 ;
吴志伟 .
自动化学报, 2014, 40 (01) :51-61
[4]   An efficient local search heuristic for the double row layout problem with asymmetric material flow [J].
Murray, Chase C. ;
Smith, Alice E. ;
Zhang, Zeqiang .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2013, 51 (20) :6129-6139
[5]   Tabu search for the single row facility layout problem using exhaustive 2-opt and insertion neighborhoods [J].
Kothari, Ravi ;
Ghosh, Diptesh .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2013, 224 (01) :93-100
[6]   Optimal solutions for the double row layout problem [J].
Amaral, Andre R. S. .
OPTIMIZATION LETTERS, 2013, 7 (02) :407-413
[7]   Multi-objective immune algorithm with Baldwinian learning [J].
Qi, Yutao ;
Liu, Fang ;
Liu, Meiyun ;
Gong, Maoguo ;
Jiao, Licheng .
APPLIED SOFT COMPUTING, 2012, 12 (08) :2654-2674
[8]   A corrected formulation for the double row layout problem [J].
Zhang, Zeqiang ;
Murray, Chase C. .
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2012, 50 (15) :4220-4223
[9]   A genetic algorithm with the heuristic procedure to solve the multi-line layout problem [J].
Sadrzadeh, Amir .
COMPUTERS & INDUSTRIAL ENGINEERING, 2012, 62 (04) :1055-1064
[10]   Single row facility layout problem using a permutation-based genetic algorithm [J].
Datta, Dilip ;
Amaral, Andre R. S. ;
Figueira, Jose Rui .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2011, 213 (02) :388-394