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

设备布局对于提高生产效率和降低运营成本具有重要意义. 本文针对半导体加工制造中常见的双行设备布局问题, 提出了一种结合多目标免疫算法和线性规划的双行设备布局方法来同时优化物料流成本和布局面积两个目标. 首先, 建立了问题的混合整数规划模型;其次, 针对问题既含有组合方面(机器排序)又含有连续方面(机器精确位置)的特点, 分别设计了一种多目标免疫算法来获取非支配的机器排序集合, 提出了一种基于线性规划的方法来构造任一非支配机器排序对应的连续的非支配解集;最后, 由所有连续的非支配解来构造最后Pareto解. 实验结果表明, 该方法对于小规模问题能获得最优Pareto解, 对于大规模问题能够获得具有良好分布性的Pareto解且其质量远好于NSGA-II和精确算法获得的解.

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

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.