基于分割树遗传算法的空间布局多目标优化研究

连建新，闫 辉，张小稔

（河北工业大学 经济管理学院，天津 300130）

基于分割树遗传算法的空间布局多目标优化研究

连建新，闫 辉，张小稔

（河北工业大学 经济管理学院，天津 300130）

在分析单目标平面布局优化不足的基础上，构建了多目标的车间空间结构布局的非线性规划模型，弥补了传统车间布局过程中对高度、车间空间约束等因素的忽略；同时利用分割树、波兰表达法和遗传算法相结合的方法，对染色体编码和遗传算子变异进行了有效的改进，大大提高了搜索速度．并以某机械加工企业的油缸车间为例，对其布局进行优化，最后画出更加切合实际需求的车间布局图．

空间；多目标优化；分割树；遗传算法

0 引言

随着经济全球化的进程日益深入，制造企业的生产模式逐渐趋于大规模个性化订制，相互之间竞争也进入了短兵相接阶段．而作为企业生产得以实施的载体——制造车间，也面临更加严峻的考验．因为为了能够迅速的对客户的要求作出响应，能在最短时间、以最低成本制造出使顾客满意的产品，需要对原有车间进行重构与优化，以适应生产．

据统计表明：在制造业中，企业总运营费用的15%～70%用于物料运输，而一个高效的布局车间可使此费用节约10%～30%[1]．此外在整个工厂的生产物流活动当中，生产周期的5%～10%用于加工、检验，剩余时间都处于搬运、等待状态[2]．因此美国每年要花费超过2 500亿美元用于车间的布局优化上[3]．由此可见布局研究对于制造企业来说至关重要．它可以最大限度地降低车间内的物料运输、废料处理成本，充分利用现有的生产空间、均衡设备能力等，有利于提高企业的整体运作效率．然而车间的重构与优化绝非易事，不仅要承担停产的损失，还要考虑车间空间、物料搬运成本、工艺流程等条件的制约．

为此本文针对多行布局，通过充分考虑空间、成本等因素的条件下[4]，运用分割树遗传算法，对车间布局问题进行研究．因为通过分割树与遗传算法相结合的方法，即可以显著提高布局规划人员的效率和最终方案的质量；又对传统遗传算法进行了改进，使编码更加容易，易于提高搜索速度；同时在布局过程中，是根据设备的实际需求面积进行规则的块状分割，将不规则设备和设备的摆放方位也给于充分的考虑．

1 问题的描述

1.1 问题假设

车间布局问题就是合理安排车间内部各种设施及其相关的辅助设施的相对位置与面积，以确保在生产过程中物料与信息的畅通．为了便于简化计算，在构建模型过程中做了如下简化与假设：

1）将1个设备摆放、操作、辅助设施等所需的空间看成1个整体，称为1个作业单位，且作业单位尺寸已知，如图1中所示；

2）所有作业单位都被看成规则的立方体或长方体，忽略细节形状；且输出、输入零部件点位于作业单位的中心点；

3）所有零部件都是从入口进入车间，从出口出，不存在从入口出或出口入的现象；运输距离除了水平还包括竖直方向；

4）零部件的加工工艺以及与其相对应的设备已知；

5）所有作业单位沿着车间主运输道2边排列；

6）物料在搬运过程中忽略装卸费用．

1.2 空间布局模型建立

车间布局示意图，如图1所示，其中L、W、H分别为车间的长、宽、高；Ld为出入口与车间主运输车道的宽度；（XI，W），（XI，0）分别为出、入口坐标；i为作业单位编号，其中i=1,...,n；Wi、Li、Hi为作业单位宽、长、高；hi为作业单位i的操作平台高度；Zi为作业单位i离车间顶部距离；xi，yi为作业单位i相对于坐标原点O的X，Y坐标．

图1 布局结构参数示意图Fig.1 Schematic diagram of layout structure parameters

1.2.1 成本物流模型

实际生产制造过程中，物料在作业单位间的运输距离，除了水平方向的移动量，还包括竖直方向的移动量．另外物料由车间入口处至加工第1道工序的作业单位处，由加工最后1道工序的作业单位处至出口处的运输方式都与作业单位间的物料运输方式是不一样，因此运输成本也不一样．

假设车间共有n台设备，加工Q种零部件，则物流与重置成本表达式如式 (1)

其中：Pqij为第q种零件在作业单位i与j之间搬运总费用；PqI为第q种零件从入口至加工第1道工序的作业单位处的移动成本；PqO为第q种零件加工完成后从作业单位至出口的移动成本．其中Pqij，PqI，PqO定义如式(2)～(4)所示

其中cqij，fqij分别为第q个零件在作业单位i与j之间的单位物流成本和物流量；

其中fqI，cqI分别为加工第q个零件时，从入口至第1道工序处的物流量和单位物流成本；xqI，yqI，hqI分别为加工第q个零件时，第1道工序的作业单位相对于坐标原点O的X，Y，Z坐标．

其中cqo，fqo分别为加工第q个零件时，从最后1道工序加工完成之后至出口的单位物流成本和物流量；xqo，yqo，hqo分别为加工第q种零件时，最后1道工序的作业单位相对于坐标原点O的X，Y，Z坐标．

1.2.2 车间面积利用率模型

车间面积利用率如式 (5)所示

1.3 约束条件

1）面积约束如式 (6)

其中Ai是作业单位i所需要的面积．

2）形状约束如式 (7)～式 (8)

3）非负、边界约束如式 (9)～式 (13)

其中式 (9)～式 (13)确保所有作业单位都未超出车间；式 (13)定位车间主运输通道的．

4）定位、不重叠约束如式 (14)～式 (21)

式 (14)与式 (15)表示作业单位i位于车间入口处（用来定位）；式 (16)与式 (17)中PHr与PHl分别表示1个水平分割树的右、左叶子；式 (18)与式 (19)中PVr与PVl分别表示1个垂直分割树的右、左叶子；式 (20)中TVr与TVl分别是垂直分割树的右与左子树；式 (21)中THr与THl分表示的是水平分割树的右与左子树；

2 设备布局的遗传算法

2.1 染色体编码与解码

2.1.1 编码

编码是将问题的可行解从解空间转换成遗传空间的，由基因按一定结构组成的染色体的过程．本文采用分割结构（块状布局）来表达，令水平切割和垂直切割用算子（内部节点）+和*表示，分割结构包含n个给定的作业单位（称作操作数或叶子），用字母集=(1,2,...,n,*,+)的分割树或波兰表达法进行编码表示．操作数与算子之间关系与表达方式如下图2所示，编码过程如图3所示．

图2 分割结构及其表示Fig.2 Segmentation structure and its representation

图3 波兰编码过程Fig.3 Poland coding process

在编码过程中必须遵循以下准则：1）1个染色体必须有n个不同的操作数（作业单位数）和（n 1）算子；2）1条染色体中，任何1个元素i（包括i）之前的操作数总数必须大于等于，其中为算子数，否则不能生成并建立合法的波兰表达式．

2.1.2 解码

解码：编码的逆向过程，将波兰表达式转换成分割结构（块状布局）．对于1个长度为（2n 1）的分割树，令i是分割树上任意分割点（或位置），令分别为从分割点右侧到树的最右侧包含的操作数和算子总数．则解码过程如下．

如果分割点i是第1个位置，在2n 1～1的范围内从右向左查找使等式成立的位置．则在分割点i分割树可以分成：1）包括给定分割树中从1～i的元素的左子树；2）包括给定分割树中从i+1～2n 2的元素的右子树，具体如图4所示．

图4 解码过程Fig.4 Decoding process

2.2 初始种群的产生

运用遗传算法[5]进行车间布局研究时，必须有1个初始种群作为初始解，其通常是随机产成的，但随机产成的初始解无法收敛于最优解．同时种群的数量对求解也有显著影响[6]，数量过多，运行时间长，影响搜索效率；种群过少，则会过早收敛．因此本文采用系统布置设计SLP（Systematic Layout Planning）与随机法来确定初始种群，种群数量以20～100为宜[7]．

2.3 适值函数

适值函数定义为

2.4 选择

采用Holland正比选择法，即根据每个染色体适值的比列来确定个体的选择概率[8]．选择过程就是根据这些概率先建立1个轮盘赌模型，然后旋转轮盘pop size（种群规模）次，每次为新种群选出1个个体．设fi为种群中个体i的适值，N为种群数．则个体i被选中的概率是

根据式 (23)，适值概率越高的个体被选中的几率越大．

2.5 变异操作

针对每个染色体采用2种变异方式．第1种是2个算子相互替代，如图5所示；第2种是交换2个操作数或算子的位置，如图6所示．这种变异可保证产生合法的后代．

3 实例应用

以某机械加工企业的油缸车间为例，该车间总共有11台设备（5台深孔镗床，5台普通车床，1台珩磨机），36种不同规格油缸．为了便于计算此处将其全部转换成物流量；总面积为17×30m2，实际上用于设备布局的面积为15×24m2．

图5 替代操作Fig.5 Alternative operations

图6 交换操作Fig.6 Switching operations

表1 机加工工序和设备尺寸Tab.1 Machining processes and equipment dimensions

表2 作业单位与几何约束Tab.2 Operating units and geometric constraints

表3 设备间当量物流量 (kg/d)Tab.3 Equipment room equivalent flow rate (kg/d)

0、12分别为入、出口；1，…，5代表深孔镗床；6，7，…，10普通车床；11为珩磨机．进出、入口搬运费用为0.002元/（m kg），设备之间搬运费用0.001元/（m kg）．入、出口坐标分别为（4，0）、（4，24）．遗传算法的相关参数设：pop size=50，pm=0.001，max gen=200．总目标的权重定为u1=0.6、u2=0.4．计算结果如下：[12345****11678910****++]．则该车间布局的原始图见图7，优化后的布局图以及相应的分割树见图8、图9．

从表4中可得知，车间重构后物料搬运的总距离减少了42.5m，搬运费用降至3 320，车间的空间利用提高了．

图7 原始图Fig.7 The original graph

图8 优化图Fig.8 Optimization diagram

图9 优化后的树表示Fig.9 Optimal tree representation

表4 重构前后的相关参数对比Tab.4 Comparison of correlation parameters before and after reconstruction

4 结语

有效、合理的车间设施布局可以最大限度地缩短物料搬运距离，提高车间的利用率，降低生产成本．本文针对多行布局，构建了多目标的车间空间布局非线性规划模型，并利用分割树遗传算法进行求解．通过以某机械加工企业的油缸车间重构前后物流费用，占用面积比率的对比，验证了该算法与模型的有效性．

综上所述，通过对运输费用、加工工艺、车间的空间限制条件等影响车间布局的相关因素分析，并通过相关案例的应用，可以得出分割树遗传算法可以有效的解决或优化这种含有不同种类设备、多约束条件下的车间布局问题．

[1]Tompkins JA，White JA．Facilities planning[M]．3rd edn，New York：Wiley，2003．

[2]方庆琯，王转．现代物流设施与规划 [M]．北京：机械工业出版社，2009．

[3]Lee H J．Heuristic graph-theoretic approach in facility layout problem：the development of a decision support system[J]．Annual Reviews in Control，2007，31（1）：255-267．

[4]Kim Jae Gon，Kim Yeong Dae．Layout planning for facilities with fixed shapes and input and output points[J]．Internationanl Journal of Production Research，2000，38（18）：4635-4653．

[5]Farhad Azadivar，Wang John（Jian）．Facility layout optimization using simulation and genetic algorithms[J]．Interntional Journal of Production Reserch，2000，38（17）：4369-4383．

[6]Yosra Ojaghi，Alireza Khademi．Production layout optimization for small and medium scale food industry[J]．Procedia CIRP，2015（26）：27-251．

[7]肖国红，弓清忠，荣星，等．基于设备参数化的镜片车间优化布局 [J]．技术创新，2015，38（5）：63-65．

[8]Mitsuo Gen，Runwei Cheng．Genetic algorithms and engineering optimization[J]．International Journal of Production Research，2013，24（3）：1095-1109．

[责任编辑 田 丰 夏红梅]

Based on the segmentation tree space layout of the multi-objective optimization of genetic algorithm research

LIAN Jianxin，YAN Hui，ZHANG Xiaoren

(School of Economics and Management,Hebei University of Technology,Tianjin 300130,China)

On the basis of the logistics cost and two-dimensional layout optimization analysis of defects on buliding a multi-objective dynamic spatial facility layout optimization model for multi-variety production system.On account of the logistics cost,replacement cost,space utilization,equipment utilization rate,and other factors,the use of partheno genetic algorithm based on objective weighting method and polish expression to evaluate selection,them ore reasonable plan.

space;multi-objective optimization;cut tree;genetic algotithm

F273.1

A

1007-2373(2016)05-0056-08

10.14081/j.cnki.hgdxb.2016.05.009

2016-09-27

连建新（1971-），男（汉族），副研究员．