SCI论文（www.lunwensci.com）
摘 要：为解决高效的车间动态设施布局问题,以重布局费用、非物流关系和面积利用率为目标,对 NSGA-II 算法进行 了优化,将随机变异操作与最近和最远法的非支配解选择结合,对 NSGA-II 算法进行了改进并对其进行求解。通过经典算例的 模型求解测试,验证了该方法的可行性和有效性。
关键词：动态设施布局,多目标优化,改进NSGA-II算法
Research on Dynamic Layout of Multi-objective Facilities Based on Improved NSGA-II Algorithm
WU Mei
(Jiangsu Urban and Rural Construction Vocational College, Changzhou Jiangsu 213147)
【Abstract】：In order to solve the problem of efficient dynamic facility layout in the workshop, the NSGA-II algorithm was optimized with the objectives of rearrangement cost, non-logistics relationship and area utilization rate. The random mutation operation was combined with the non-dominated solution selection of the nearest and farthest method to improve the NSGA-II algorithm and solve the problem. The feasibility and effectiveness of the proposed method are verified by the model solving test of a classical example.
【Key words】：dynamic facility layout;multi-objective optimization;improved NSGA-II algorithm
对企业生产系统来说,一个高效的车间设施布局 (Facility Layout, FL)显得尤为重要。研究表明 [1] ：产品生 产过程中,原料的搬运费用占了生产成本的 20% ~ 50%, 然而,合理的设备布局却能够降低 10% ~ 20% 的原料 搬运费用。
随着人工智能的发展, 模拟退火算法、遗传算法等 被用来解决动态设施布局问题。文献 [2] 使用模拟退火 算法来求解最佳布局 ;文献 [3] 引入自适应策略的改进 遗传算法用于动态设施布局问题的求解 ;文献 [4] 以带 精英策略的非支配遗传算法对该问题进行求解,弥补了 难以确定加权系数以及多目标无法同时优化的不足。这 些方法的求解质量有待进一步提高。
基于此, 本文以动态设施布局问题为背景,将车间 与设备假设成有形状规则的矩形。在二维平面内,将动 态设施布局问题抽象为在矩形容器内矩形设备的摆放问题,并提出一种改进的 NSGA-II 算法对其进行求解。
1 多目标设施动态布局模型
1.1 问题描述
多目标设施动态布局问题以车间中设备的多阶段布局 为背景,为了方便从理论上研究,作出以下基本假设 [5] ：
(1)设施为矩形,各设施面积不等 ;
(2)车间为矩形且长宽给定 ;
(3)设施在车间内水平或垂直放置 ;
(4)设施之间物料搬运沿着水平或垂直方向 ;
(5)设施自动分行放置,从左到右,从下到上。
当满足以下条件时,将已知长和宽的矩形设备放入 同样已知长宽的矩形车间内 ：
(1)矩形设备之间互相不重叠 ;
(2) 设备不能超出矩形容器或者与矩形容器有嵌入 ;
(3)在整个计划期内物料搬运费与设施重置费之和最小,且非物流关系最大。
1.2 优化目标及数学模型
本文选择以下 3 个具有实际应用价值的优化目标 ： (1) 最小物体搬运费和设施重置费,如式(1)所示 ：
(2)最大非物流关系强度,如式(2)所示 ：
1.3 约束条件
多目标设施动态布局模型约束条件如下 ：
(1)间距约束 ：同行设施之间不嵌入 ;
(2)边界约束 ：所有设施不超出车间边界 ;
(3)第一行设施距离边界为 v0.设施 i 与车间的左右边界的水平最小间距为 hi。
1.4 罚函数
为了使设施在纵向满足边界约束, 引入罚函数,如式(4)所示 ：
2 改进 NSGA-II 算法设计
2.1 NSGA-II 算法描述
NSGA-II 算法是由遗传算法改进而来。初始化一个 数量为 100 的种群,经过选择、交叉、变异 3 个操作后 得到第一代子代种群。合并父代种群与子代种群,进行快速非支配排序,根据非支配关系以及拥挤度大小选取 合适的个体形成新的父代种群 ;最后,通过遗传算法的 基本操作产生新的子代种群,依次迭代,直至达到最大 迭代次数,程序完成 [6]。算法流程图如图 1 所示 ：
2.2 NSGA-II 算法改进
(1) 编码方案。以一个二维矩阵的方式来表示, 矩 阵的列表示每个子周期内的布局方案,矩阵的总列数表 示总计划期数 r,总行数代表需布局的设备总数量 n[3]。
(2) 交叉策略。在设施布局问题中, 采用部分匹配 交叉(Partial Matched Crossover,PMX) 方法 [7]。随 机选择两个位置作为父代的交叉点,由这两点定义的子 串称为映射段。互换这两个子串,产生原始后代,根据 映射关系交换后代映射段外的个体。
(3) 变异策略。变异操作能够增加种群多样性, 弥 补了交叉操作产生的后代适配值没有达到最优且不再进 化而早熟收敛的不足。本文采取随机变异方法,将单点 交换、插入、逆序、多点交换变异策略结合在一起使 用,即每次执行变异操作时随机选择其中的一种。
(4) 非支配层选择。先选取级别小的个体,如果级 别一致,选择最近最远候选解法选取 [8]。
3 算法测试分析
选取文献 [4] 中的动态设施布局问题的经典算例为测试 算例。参数做如下定义 ：种群中的个体数量为 100 ;车间 的长为 14m,宽为 12m ;罚函数p 中的常数值 6 为 500.
当迭代次数为 1000 时,采用基于插入变异策略计 算结果相对较好,但不能达到最优,如表 1 所示。而采用随机变异策略的计算结果比单一选用要好,如表 2 所示。采用随机变异与最近最远候选法结合得到的结果则最优,如表 3 所示。选出一个最优解 a,即目标值为(1294603.80 ;243.99 ;222.60) 时的解, 此时的布局图如图 2 所示。
4 结论
合理的动态设施布局可以减少资源浪费和污染物的 排放,降低生产成本,从而提高产品利润。本文将动态 设施布局问题转化成带约束条件的数学模型,提出了一 种将随机变异操作与最近最远法的非支配解选择结合的 改进 NSGA-II 算法求解优化模型,并进行了实验比较, 验证了算法的有效性和可行性。
参考文献
[1] BRAGLIA M,ZANONI S,ZAVANELLA L.Layout Design in Dynamic Environment:Strategies and Quantative Indices[J].International Journal of Production Research, 2003.41(5):995-1016.
[2] HERAGU S S,ALFA A S.Experimental Analysis of Simulated Annealing Based Algorithms for the Layout Problem[J].European Journal of Operational Research, 1992.57(2):190-223.
[3] 郭爽,徐克林,孙立锋.基于遗传算法的动态连续型设备布局 方法[J].现代制造工程,2011(11):58-77.
[4] 黄君政,李爱平,雷明.基于NSGA_II的多目标设备动态布局 方法[J].中国工程机械学报,2014.12(1):1-6.
[5] 王亚良,钱其晶,曹海涛,等.基于动态差分元胞多目标遗传算 法的混合作业车间布局改善与优化[J].中国机械工程,2018.14 (29):1751-1757.
[6] DEB K.A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-II[J].IEEE Transaction on Evolutionary Computation,2002.6(2):180-197.
[7] 李波,邱枫.基于单亲遗传算法的动态设备布局仿真研究[J]. 智能系统学报,2007.2(1):74-79.
[8] BAYKASOGLU A,DEREL T,SABUNCU I.An Ant Colony Algorithm for Solving Budget Constrained andUnconstrained Dynamic Facility Layout Problems[J]. International Journal of Management Science,2006. 34(4):385-396.
关注SCI论文创作发表，寻求SCI论文修改润色、SCI论文代发表等服务支撑，请锁定SCI论文网！
文章出自SCI论文网转载请注明出处：https://www.lunwensci.com/jisuanjilunwen/63129.html
