基于AGA的曲轴自动化生产车间多目标优化布局研究*

申 宽，翟敬梅，张 铁

(华南理工大学 机械与汽车工程学院，广州 510641)

基于AGA的曲轴自动化生产车间多目标优化布局研究*

申 宽，翟敬梅，张 铁

(华南理工大学 机械与汽车工程学院，广州 510641)

为提高车间的生产效率、降低成本，对设备布局进行优化是十分必要的。基于物流费用最小和面积利用率最大的原则，并增加辅助设施(上下料机器人)对布局的约束，建立了曲轴自动化生产车间设备布局的多目标优化模型；采用自适应遗传算法(adaptive genetic algorithm，AGA)求解该问题时，交叉、变异概率基于Logistic曲线自适应调整，有利于优胜劣汰和全局最优解的获得。与改造前的布局相比较，加入机器人后的优化布局使物流费用降低、占地面积减小，对企业降本增效具有一定现实意义。

设备布局；自适应遗传算法；多目标优化

0 引言

设备布局问题(facility layout problem，FLP)是指在一定限制条件下(如车间面积形状、物流方式等)，将生产设备在给定空间内布局，使目标函数(如物流费用、面积使用率等)得到优化。设备布局对企业降本增效具有重要意义，从时间成本上来看，物料从进厂到出厂真正处于加工检验的时间仅占生产周期的5%～10%，而90%～95%的时间都处于搬运或等待状态[1]；从经济成本上来看，物料搬运费用在生产活动总开销中所占比例高达20%～50%。良好的设备布局能使物料更加高效顺畅的流通，减少搬运、等待时间，使物流费用至少降低10%～30%[2]。

目前，设备布局采用数学分析法建立的模型主要包括二次分配模型、二次集合覆盖模型、线性整数规划模型、混合整数规划模型等[3]。Koopmans和Beckmann于1957年首次提出二次分配模型[4](quadratic assignment problem，QAP)，描述n个设施和n个地点，要求给每个设施分配到一个位置，并使设施之间的总流量(或费用)最小。QAP模型的最优求解算法，可以归为分支定界法和割平面法两类[5]。这两种算法都需要较多的计算时间和较大的存储空间，随着布局规模的扩大，最优算法因“组合爆炸”问题已不再适用，20世纪80年代后研究者多转向元启发式算法求次优解。其中，遗传算法因其全局性并行搜索的特点，被广泛运用于QAP求解。

李爱平[6]、赵建东[7]、徐立云[8]等人建立了多行直线布局的QAP模型，但所建立的模型中，行与行之间的距离均设为定值而与该行设备无关，相邻设备之间的净间距采取初始随机生成、后续算法优化的方法确定，不仅增大了运算量，最终优化结果还因为初始值的随机性而波动较大[9]。本文从实际出发，重新定义了行与行之间以及相同行相邻设备之间的距离，并考虑增加的辅助设备(例如上下料机器人等)对原有设备优化布局的约束影响，对多行直线布局的QAP模型进行了改进。在求解QAP过程中，对简单遗传算法作了自适应改进，进化参数可以根据个体自身的优劣程度实时调整，对提高算法的效率和最优解的改善作用明显。

1 FLP的多目标优化模型

1.1 问题描述

为方便计算，对多行直线布局做出以下假设(如图1所示)：①所有设备形状均为其包络矩形，忽略其细节形状及高度；②同一行设备的中心点位于一条直线上，沿X轴正方向依次排列；③零件加工工艺确定；④各行之间有物流通道，与X轴平行，宽度WP为定值。

假设有n台设备，给其固定编号为1～n，设备i的包络矩形沿X轴、Y轴尺寸分别为Ai、Bi。参考设备的技术文档，在其周边留出最小安全距离Hi，用于设置安装、操作、维修、工件缓冲区域等，相邻摆放的两个设备i、j之间的最小距离Hij=Hi+Hj。

图1 线性多行设备布局示意图

在车间长度的约束下，当一个设备序列s确定后，则该序列在每行上的设备分布及设备中心点X轴坐标值可按如下公式递推计算：

xs(1)=Hs(1)+As(1)/2

(1)

xs(i)=xs(i-1)+Hs(i-1)s(i)+(As(i-1)+As(i))/2，i=2,3,…,n

(2)

当xs(j)+As(j)/2+Hs(j)>L时(L为车间长度)，将设备s(j)移至下一行第1位，并按照式(1)、式(2)继续计算设备s(j)、s(j+1)的X轴坐标值。

令hi=Hi+Bi/2，各行设备的中心点Y轴坐标值可按如下公式确定：y1=max{hs(1),hs(2),…,hs(m)}，s(1)、s(2)、…、s(m)为排在第1行的设备；y2=y1+max{hs(1),hs(2),…,hs(m)}+WP+max{hs(m+1),hs(m+2),…,hs(r)}，s(m+1)、s(m+2)、…、s(r)为排在第2行的设备，WP为物流通道宽度。以此类推，直至求出最后一行设备的中心点Y轴坐标值。

1.2 优化目标

通常情况下，一个好的布局方案应遵循满足工艺流程、工件尽量直线前进、减小移动距离、简化搬运作业、充分利用空间、保持生产均衡等原则。为此，本文以物流费用最小和面积利用率最大为优化目标。

上述两个目标确定后，如何确定一个布局，使F、S均能取得理想的结果，这就是一个多目标优化问题。通常来讲，求解多目标优化问题主要有3类方法[10]：①生成法，即先求出大量的非劣解，构成非劣解的一个子集，然后按照决策者的意图找出最终解；②交互法，不先求出很多的非劣解，而是通过分析者与决策者对话的方式逐步求出最终解；③归一法，事先要求决策者提供目标之间的相对重要程度，算法以此为依据将多目标问题转换为单目标问题求解。本文采取第3类方法，用加权法构造新的目标函数：

L=w1F/Fmin+w2S/Smin

(3)

w1、w2为加权因子，根据实际工程中对于物流和面积各自的侧重程度来确定，要满足加权条件w1+w2=1；F、S各除以它们的单目标优化最优值，既消除量纲，又能反映它们偏离最优值的程度。

1.3 约束条件

(1)所有设备不超出车间长、宽范围，即：

max{xi+Ai/2+Hi}≤L

(4)

max{yj+Bj/2+Hj}≤W

(5)

式(4)可由自动换行策略来保证；式(5)可对F和S设置罚函数来保证，例如：

(2)存在物流关系的两台设备不得跨行布置。由图1可知，假如设备s(1)、s(j)之间存在物流关系，则1.2节中定义的dij将失去意义，因为物料不可能“穿越”中间行传递。此项约束条件如在布局设计阶段实现将会比较复杂，采取的办法是对布局结果进行验证排除。

(3)设备相邻关系约束。大多数布局案例[6-8]均没有考虑此类约束，在下文实例中由于车床M1-1/M1-2、磨床M5-1/M5-2要分别与机器人MH6组合使用，因此两组设备要相邻布置，同时还要考虑机器人工作半径对设备间距的约束。本文的解决办法是先对组合单元进行布局，再将组合单元作为一个整体与其他设备布局。

2 自适应遗传算法求解FLP

在标准遗传算法中[11]，交叉、变异算子是固定的，不利于种群多样化，可能会导致算法收敛缓慢，或是过早收敛甚至陷入局部最优(“早熟”现象)。针对这一问题，采取自适应遗传算法，根据个体适应度值的大小实时调整交叉、变异概率，保持进化动力。自适应遗传算法有线型(LAGA)、余弦型(CAGA)和Logistic曲线型(LOAGA)等，由于LOAGA在进化各阶段均有不同侧重，在个体多样性和后期收敛性等方面具有优势[12]，因此本文采取LOAGA求解FLP。

2.1 染色体编码

采用顺序编码方式，给n个设备各指定一个1～n之间的整数编号(一一对应无重复)，以1～n的一个排列作为1条染色体(代表一个设备序列)。根据1.1节中的递推方法，求出该序列每个设备的X、Y坐标值；再根据1.2节中式(3)求出加权统一的多目标优化函数值L。由于所求目标为极小值，所以适应度函数可设为f=1/L。随机生成m个序列，作为算法的初始种群A。

2.2 选择

采取随机联赛选择方式[11]，联赛规模为N。具体过程是：①从A中随机选取N条染色体，比较它们的适应度函数值大小，将其中最大的保留进入下一代群体；②重复上述过程M次，得到包含M条染色体的群体As。

2.3 交叉

交叉算子选用部分映射交叉(PMX)方式。如图2所示，先选择交叉位置(图中带框编号)，交换两个父代染色体对应位置的编号，然后对交叉位置以外的重复编号(图中带下划线编号)按交叉时建立的映射关系逐一替换，确保交叉产生的子代染色体的合法性(即不含重复编号)。将As中的染色体两两配对，按照自适应交叉概率决定是否交叉，交叉后得到子代群体Ac。

图2 部分映射交叉

自适应交叉概率：

式中，pcmax、pcmin为设定的交叉概率的上、下限，f′为两条配对染色体中较大的适应度值，favg为当代群体的平均适应度值，fmax为当代群体的最大适应度值，a为常数。自适应交叉概率的意义在于：当配对染色体适应度小于当代群体的适应度时，交叉率取上限，增大交叉发生的可能性；当配对染色体适应度大于当代群体的适应度时，交叉率会有所下降，减少交叉发生的可能性。这样一方面提高进化初期个体适应度不高时的进化速度，另一方面减少了进化后期低适应度值个体的数量，以节约计算时间和资源。

2.4 变异

变异算子采用邻域技术，如图3所示，对需要变异的染色体，随机选择3个基因位(图中带框编号)，再互换它们的位置得到该染色体的一个邻域，选择邻域中适应度函数值最大的作为变异成果。为增加新染色体的数量，将As、Ac中的每条染色体都按照自适应变异概率决定是否变异，并得到变异的群体Am。

图3 变异产生的邻域

自适应变异概率：

式中，pmmax、pmmin为设定的变异概率的上、下限，f为当前染色体的适应度值。自适应变异概率的意义在于：在进化前期，较优解和较差解都取小的变异概率，利于优良基因保留和较差基因淘汰；在进化后期，种群中各染色体的适应度值相差越来越小，变异概率将会增大，有利于生成新解，防止进化停滞不前。

2.5 进化及终止

将群体As、Ac、Am中的每个个体按照适应度值大小排序，选取前m个个体作为当前进化的结果(更新群体A)，然后进行下一次进化。遗传算法终止条件有：①根据进化次数，一般取值范围为100～500；②根据适应度函数值的最小偏差；③根据适应度函数值的变化趋势(趋于缓和或不再变化)。本文以进化次数作为终止条件。

3 曲轴生产车间的优化布局改造

本文主要研究W集团压缩机有限公司的冰箱压缩机曲轴生产车间的设备布局。该曲轴由相互平行的主轴颈、曲轴颈以及中间的半圆形平衡块组成(见图4)，主要特征有螺旋形油槽、直油槽、油孔、定位孔等，主轴颈为空心圆柱结构。曲轴毛坯为铸造件，主要工艺如图5所示，加工过程需要车床、钻床、铣床、磨床等9台设备以及清洗、检验工位。生产车间长宽为22m×22m，改造前是按照工艺路线采取“S”形多行直线布局。为加快生产节拍、提高效率，公司引进两个6自由度机器人分别为两台车床和两台无心磨床自动上下料(图5中虚线框部分)，并且对加工设备重新布局，使物料流通更加顺畅高效。

图4 冰箱压缩机曲轴结构示意图

图5 冰箱压缩机曲轴工艺路线

3.1 设备和机器人组合的布局

各设备的型号及外形尺寸如表1所示。公司选用机器人的型号为安川MOTOMAN-MH6，其最大工作半径1422mm，基座回转角度±170°。如果两台加工设备(M1-1、M1-2或M5-1、M5-2)采取“一一”型或“L”型布局，则机器人需要移动才能完成上下料，增加了行走模组和控制系统的成本。因此，将加工设备面对面摆放，机器人位于中间，这样虽然设备的安全距离有所重叠，但因采取了机器人上下料，对安全生产的影响可以忽略。设备之间的距离取2.4m(<2×1422mm)，则M1-1、M1-2和MH6组成的车削单元M1长度5.66m、宽度3.11m，M5-1、M5-2和MH6组成的磨削单元M5长度5.9m、宽度1.95m。

表1 曲轴加工设备尺寸 单位：m

3.2 LOAGA与SGA优化对比

物流通道宽度WP=2 m，方向与X轴平行。为便于取件，各设备的操作面与物流通道垂直。将车削单元、磨削单元均视为一个设备，根据加工工艺统计出设备之间的访问次数矩阵：

由于曲轴在加工时损失的质量不大，设备i、j之间单位距离上单位工件的物流费用qij可视为定值，不妨设其为1。

设备数n=9，取初始种群大小m=100，联赛选择的规模N=2、M=50，进化代数T=300。先按照单目标优化，分别求出最小物流费用Fmin=85.9850、包络矩形最小面积Smin=262.0072。再用两种遗传算法求解多目标优化布局：方法1采用简单遗传算法(SGA)，交叉、变异概率为定值，交叉概率pc=0.75，变异概率pm=0.1；方法2采用自适应遗传算法(LOAGA)，交叉概率pcmax=0.95、pcmin=0.55，变异概率pmmax=0.15、pmmin=0.05，常数a=9.903。

在Matlab中编写SGA和LOAGA的程序，均从相同的初始群体出发，运行6次的结果如图6所示，横坐标为进化代数(t)，纵坐标为每代最大适应度值(fitbest)。从图6可以看出，在解的质量方面，LOAGA有5次得到了最佳值(fitbest=0.9233)，SGA仅有2次(第4次、第5次还出现明显的“早熟”现象)，说明在进化过程中LOAGA比SGA更容易跳出局部最优；在求得最佳值的速度方面，LOAGA仍然领先于SGA，除第6次外LOAGA均用较少的进化代数得到了最佳值。

图6 SGA与LOAGA优化结果对比

3.3 布局结果分析

在引入机器人之前，生产车间是根据图5所示的工艺流程并按照“S”形路线进行的布局，设备序列为[M2 M1-1 M1-2 M4 M5-1 M9 M8 M3 M5-2 M6 M7]，如图7所示(矩形内数字为设备编号，矩形外数字为该设备完成的工序)。经计算，此种布局物流费用F=118.675，其包络矩形面积S=290.7628。

引入机器人后，由3.2节可得出多目标优化布局的设备序列为[M8 M3 M4 M2 M7 M9 M1-1 MH6 M1-2 M6 M5-1 MH6 M5-2]，如图8所示，此时的物流费用F=96.015、包络矩形面积S=274.9956，比之前的布局分别减少了19.1%、5.4%，较好地实现了优化布局的目标。

表2为优化之后的各设备中心点坐标。另外由图8可以看出，第1行与第3行的设备均没有物流关系，满足1.3的约束条件。

表2 布局优化后的各设备中心点坐标

图7 加入机器人之前的S形布局

图8 加入2个机器人之后优化的布局

4 结论

本文改进了多行直线布局的QAP模型中行与行之间、相邻设备之间距离的定义，使之更加符合生产实际；并考虑新引入辅助设备(2台上下料机器人)的影响，先局部单元组合再车间整体优化，尽管增加了设备但最终优化的布局更加紧凑。在求解QAP过程中，基于Logistic曲线改进的LOAGA优于SGA，其原因在于LOAGA能够根据个体适应度值的大小，实时调整交叉、变异概率，减小“早熟”的可能性，使群体始终保持多样性，有利于优胜劣汰和全局最优解的获得。经过多目标优化，生产车间的物流费用降低19.1%、占地面积减小5.4%，物流费用的降低是因为总的物流距离缩短；可以预见，工件的运输时间、设备的等待时间都将缩短，因此优化的布局可以有效提高生产效率，较好地实现了降本增效的目标。

[1] 胡广华. 制造车间布局优化方法研究与系统实现[D]. 武汉:华中科技大学, 2007.

[2] BragliaM, ZanoniS, ZavanellaL. Layout design in dynamic environments: Strategies and quantitative indices[J]. International Journal of Production Research, 2003,41(5):995-1016.

[3] 锁小红, 刘战强. 制造系统设备布局的建模理论与求解方法[J]. 计算机集成制造系统,2007, 13(10):1941-1951.

[4] 张惠珍, 马良, (西)罗佑. 二次分配问题及其线性化技术[M]. 上海: 上海人民出版社, 2013.

[5] Kusiak A, Heragu S S. The facility layout problem [J]. European Journal of Operational Research, 1987, 29(3):229-251.

[6] 李爱平, 鄢泽耀, 谢楠,等. 基于NSGA-Ⅱ的多目标车间设备布局[J]. 机械设计与研究, 2012, 28(6):90-95.

[7] 赵建东, 郑军, 赵琪. 基于遗传算法的TFT-LCD冲压生产线布局优化[J]. 北京交通大学学报, 2013, 37(1):172-176.

[8] 徐立云, 杨守银, 李爱平,等. 生产车间布局多目标优化及其仿真分析[J]. 机械设计与研究, 2011, 27(6):55-59.

[9] 魏军凯, 吴芳, 戚峰. 基于遗传算法求解车间设备布局优化问题[J]. 兰州交通大学学报, 2011, 30(3):75-78.

[10] 肖晓伟, 肖迪, 林锦国,等. 多目标优化问题的研究概述[J]. 计算机应用研究, 2011, 28(3):805-808.

[11] 雷英杰, 张善文, 李续武, 等. MATLAB遗传算法工具箱及应用[M]. 西安: 西安电子科技大学出版社, 2005.

[12] 徐明明, 宋宇博. LO型曲线的自适应遗传算法研究[J]. 电子技术应用, 2015, 41(12):129-132.

AResearchofMulti-objectiveOptimizationBasedonAGAfortheFacilityLayoutinCrankshaftAutomationWorkshop

SHEN Kuan, ZHAI Jing-mei, ZHANG Tie

(School of Mechanical & Automotive Engineering, South China University of Technology, Guangzhou 510641, China)

It is necessary to optimize the facility layout, which can improve the production efficiency and reduce the cost. A multi-objective optimization model for the facility layout of crankshaft automation workshop was created: it was based on the principles of minimum material transport cost and maximum workshop area utilization, also added the constraint of auxiliary devices (loading and unloading robots). A kind of adaptive genetic algorithm (AGA) was used to find the best solution of this model. The crossover and mutation probability based on the Logistic curve could adjust adaptively, which was advantageous to the evolution and the global optimal solution. Compared with the old layout, the optimized layout including the added robots makes the logistics cost less and the footprint decrease, which has certain significance for the enterprise to reduce the cost and improve the efficiency.

facility layout；adaptive genetic algorithm；multi-objective optimization

TH181;TG506

A

1001-2265(2017)12-0151-05

10.13462/j.cnki.mmtamt.2017.12.038

2017-02-13；

2017-03-16

国家04科技重大专项(2015ZX04005006)；广东省科技重大专项(2014B090921004，2015B010918002)；中山市科技重大项目(2016F2FC0006)

申宽(1986—)，男，湖北襄阳人，华南理工大学硕士研究生，研究方向为机床与机器人一体化、设备优化布局等，(E-mail)270710478@qq.com；通讯作者：翟敬梅(1967—)，女，辽宁鞍山人，华南理工大学教授，博士，研究方向为机械系统建模与优化、机电装备与信息化、人工智能等，(E-mail)mejmzhai@scut.edu.cn。

(编辑李秀敏)