改进SLP和遗传算法结合的车间设备布局优化*

邓 兵，林光春

(四川大学 制造科学与工程学院，成都 610065)

改进SLP和遗传算法结合的车间设备布局优化*

邓 兵，林光春

(四川大学 制造科学与工程学院，成都 610065)

针对加工多种类产品，且具有固定入口和出口的生产车间，运用改进的SLP和遗传算法相结合的方法进行车间设备布局的优化，从而减少人员、物料的移动成本，提高车间利用率和企业的核心竞争力。首先，在对生产车间的物流进行详细分析的基础上，利用改进的SLP理论确定生产车间设备布局的初步方案。然后，把SLP形成的初步方案作为遗传算法的初始种群的部分染色体，利用改进的遗传算法实现对案例车间设备布局的优化。运用改进的SLP和遗传算法相结合的方法进行车间设备布局的优化，弥补了SLP过于依赖经验、约束过多的缺点，同时，提高了遗传算法的选优能力，减少了随机性所引起的误差，在选出最好个体的同时保证了种群的多样性，使最终的布局方案更具实用价值。

车间设备布局；系统布置设计；遗传算法；优化

0 引言

强化物流管理是提升企业核心竞争力的有效途径。随着对生产加工过程的深入研究，发现在整个生产加工过程中，物料的搬运、存储等非加工环节花费费用和占用时间的比例都很大。而一个优秀的物流运输系统在工厂的费用方面至少可以减少10%～30%[1-2]。因此，好的车间设备布局对企业生产运转、生产成本是至关重要的。

目前，针对车间设备布局优化问题有两大主流方法——传统的系统布置设计方法(Systematic layout planning,简称SLP)[3]和遗传算法[4-5]。SLP构建车间设备布局，其布局方案易受设计人员主观经验的影响。同样，遗传算法的初始种群的选择会直接影响算法的寻优能力，且算法的局部搜索能力较差。

本文针对加工多种类产品，且具有固定入口和出口的车间布局问题，提出一种改进的SLP和遗传算法结合的方法。首先，对SLP进行改进，简化SLP的设计流程，并改进SLP的输入因素。在对车间物流情况进行详细分析的基础上，依据改进的SLP构建车间设备布局的初步方案。然后，将SLP得到的初始方案作为初始种群的部分染色体，同时对遗传算子进行改进，以避免发生早熟。依据改进的遗传算法求解车间设备布局的最终方案。这样，将改进的SLP得到的初步方案融入到遗传算法中，实现了二者的优势互补。同时，考虑到了车间加工产品的多样性以及车间固定入口和出口的限制，使运用此法得到的车间设备布局结果更具实用性。

1 车间设备布局的数学模型

1.1 问题描述

布局的实质是确定车间内设备的位置，使物流成本最小化。本文将设备布局问题视为连续优化的多行设备布局。布局遵循以下原则：已知车间入口和出口的位置；忽略车间和设备的细节形状，将其视为矩形结构，且已知车间的面积；各设备按行排列，且与车间的长度方向(X轴)平行；设备间的横向(X轴)和纵向(Y轴)间距要求已知。这样，车间设备布局问题就简化为满足约束条件的多行设备布局问题。其参数、决策变量、参考线和坐标系的建立如图1所示。

图1 参数、决策变量、参考线示意图

1.2 数学模型

基于上述对问题的分析，车间设备布局的目标是满足总的物流成本最小化。传统的目标函数表达式为[6]：

(1)

其中，C为物流运输的总费用，n为设备台数，Pij为设备i和j之间的单位物料每单位距离的搬运费用，Qij为设备i和j之间的物料搬运频率，Dij为设备i和j之间的矩形距离。

上述目标函数仅考虑设备间的单位物料每单位距离的搬运费用。对于加工多种类产品的生产车间，不同产品的运输难易程度不同会导致搬运费用不同。针对加工多种类产品的生产车间，目标函数采用加权运输量与运输距离的乘积之和。其中，加权运输量是运输量与运输难易程度权数的乘积。将产品运输费用融入到运输量中，解决了由于不同产品运输费用不同的困扰。其目标函数可表达为：

(2)

其中，fij为设备i和j之间的月加权运输量，dij为设备i和j之间的矩形距离。

设备间距表达式：

(3)

其中，xi为设备i的中心的x坐标，yi为设备i的中心的y坐标。

加权月运输量表达式：

(4)

其中，u为车间加工产品的种类数量，Q为同类产品的预计月产量，q为同类产品的单次运输量，w为运输难易程度不同导致的运输成本权数。

设备横坐标：

xi=xk+(li+lk)/2+hik+Δi

(5)

其中，li为设备i的长度，hij为设备i和j之间的最小横向间距要求，hi0为设备i和车间边界的最小横向间距要求，△i为设备i和i-1(或边界)之间的净间距。

设备纵坐标：

yi=(k-1)s+s0如果zik=1,i=1,2,…,n;k=1,2,…,m

(6)

同一行设备不重叠约束条件：

(7)

其中，s为设备行间距，s0为第一行设备与车间边界的间距，m为车间设备布局的总行数。

其中：

(8)

同时，一台设备只能出现一次：

(9)

2 改进的SLP

本文提出的改进的SLP[7-8]方法是基于物流成本最低这一目标实现的。它适用于加工多种类产品，且具有固定的物流入口和出口的布局问题。该方法是基于SLP的基本思路，利用改进的工具对输入因素加以分析，从产品的运输难易程度、物流量和物流强度三个方面对设备间的接近关联程度加以定义和计算，从而得到设备相互关联表，根据关联程度由高到低的顺序构建车间设备布局方案。具体操作流程如图2所示。

图2 改进的SLP流程图

(1)多产品的PQ分析。首先对产品进行分析，划分产品大类；其次收集数据，包括预测产量和各类产品单次运输量；最后运输难易程度会影响运输成本，因此对各产品大类运输难易程度进行评估，将其赋予不同的权重。

(2)设备间的物流量分析。将车间的入口和出口作为两台虚拟的设备，进行物流分析时以入口作为起点，出口作为终点。根据PQ分析所得数据进行设备间加权月运输量的计算，并绘制设备间月加权运输量从至表。

(3)根据各设备尺寸、设备间的间距要求和车间可用面积，将车间进行栅格划分的处理，并标注入口和出口的位置。

(4)依据启发式规则对设备进行排列，得到初步的车间设备布置方案。

3 结合SLP的改进遗传算法

3.1 编码方式

对于多行设备的布局采用自动换行策略，即同一行内的各设备长度与实际间距之和超过最大空间长度时，本行最后一台设备自动换行[9]。其编码表达采用设备符号和净间距两个列表的扩展换位表达式：

[{m1,m2,…mn}，{△1,△2…△n}]

(10)

其中，n代表设备台数，mi代表第i个位置的设备，△i代表设备i-1和设备i之间的净间距。

3.2 初始种群

初始种群的分布状态直接关系到遗传算法的全局收敛性与搜索效率。为了加快遗传算法的收敛速度，采用随机产生与特定代换相结合的方式产生初始种群，即用SLP得到的设备排列方式代替随机产生的初始种群的部分染色体的设备排列方式。其次，为了简化目标函数，在构建目标函数表达式时，没有考虑车间的入口和出口的位置。因此，需对染色体中设备排列方式进行调整，直接固定与车间入口和出口临近的设备序列号。即根据SLP计算的设备间加权月运输量，调整染色体中设备的序列号。使与入口邻近的是设备与入口之间的月加权运输量最大的设备，与出口邻近的是设备与出口之间的月加权运输量最大的设备。

3.3 适应度函数

采用自动换行策略，则在X方向不会发生设备超出车间区域的情形。因此，只需判断最后一行设备在Y方向是否超出车间区域。

(11)

其中，Pk为不合理惩罚项，H为车间宽度，T为正的大数惩罚值。

根据适应度函数的特点，将目标函数和不合理惩罚项用一个函数实现，减少重复计算。对于染色体Vk的适应度函数定义为：

fit(Vk)=1/(C+(T×(m-1)×s+s0)>H)

(12)

3.4 选择算子

经典遗传算法中采用较多的是轮盘赌选择算子。为了提高算子的选优能力和减少了随机性所引起的误差，采用改进的无放回的基于排序的多轮轮盘赌选择算子[10]，它在选出最好个体的同时能保证种群的多样性。该选择算子的具体执行过程如下：

(1)设种群大小为M，将所有个体按其适应度值由大到小进行排序。

(2)根据个体被选取的概率将[0,1]划分为M个区间。

(3)进行多轮轮盘赌选择，产生M个[0,1]之间的均匀随机数，统计落入各区间的数值个数，取最大个数所在区间对应的个体为本轮所选中的个体，若多个区间落入数值个数相等，取适应度最大的的个体为本轮所选中的个体。用此方式选出M个个体作为子代种群。

(4)计算子代种群个体的适应度值，用父代种群适应度值最大的个体代替子代种群适应度值最小的个体。存储所有新选出来的个体作为新的子代种群。

3.5 交叉算子

用部分映射交叉方法处理染色体中设备排列序列的交叉操作，用算术交叉方法处理染色体中设备净间距的交叉操作。在对染色体中设备排列序列进行交叉操作后，需再次调整设备序列号的排列方式。使与入口邻近的是设备与入口之间的月加权运输量最大的设备，与出口邻近的是设备与出口之间的月加权运输量最大的设备。

3.6 变异操作

4 计算实例

本文给出的实例车间为19m×18m的矩形固定车间。出口和入口均布置在车间的同一宽度方向，入口中心到车间下边界的距离为3m，出口中心到入口中心的距离为8m。车间共有16台设备。其中，编号1、2、3，7、8，10、11，13、14、15分别为同一型号设备。第一行设备到车间下边界的距离s0为3m，设备行间距s为4m。车间示意图如图3所示，各设备大小如表1所示，加权运输量矩阵[fij]、设备间水平最小间距要求矩阵[hij]以及各设备和车间边界的最小水平间距[hi0]分别如式(13)～式(15)所示。

图3 车间尺寸示意图

表1 设备尺寸

(12)

(13)

(14)

本实例由SLP方法构建的三组车间设备布局方案均为4×4的排列方式，其设备排列方式如下：

{1 2 13 6 3 15 14 16 9 8 7 4 12 11 15 5}

{1 3 6 4 2 14 13 5 9 15 16 10 12 8 7 11}

{1 2 3 5 15 14 13 4 9 8 16 6 12 7 11 10}

其中，运用启发式方法对设备进行排列时，同一型号的编号为1,2,3的设备应与入口邻近，选择编号为1的设备与入口相邻，编号为9的设备与出口相邻。

本文仅用此实例介绍上述方法进行车间设备布局优化的可行性和实用性，为描述简洁，△i都取0。其遗传算法的运行参数：种群数量100，终止代数500，交叉概率0.65，变异概率0.01，正的大数惩罚值500，Umin为0，Umax为0。

最后，得到的最好染色体为[{1 15 3 2 14 13 10 5 9 2 12 16 11 4 8 7},{0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0}]。

第一行设备：1(3.2，3)、15(7.2，3)、3(11.2，3)、2(14.7，3)

第二行设备：14(2.9，7)、13(6.6，7)、10(10.2，7)、5(14.2，7)

第三行设备：9(3.3，11)、2(7.2，11)、12(11.4，11)、16(15.5，11)

第四行设备：11(3.8，15)、4(7.8，15)、8(11.3，15) 、7(15.3，15)

其遗传进化过程如图4所示，车间设备布局优化结果如图5所示。

图4 遗传进化过程图

图5 车间设备布局优化结果图

4 结论

(1)利用改进的SLP和遗传算法相结合的方式，对车间设备布局进行优化。采用改进的SLP方法减少了人的经验判断对初步的车间设备布局方案的影响。同时，将得到的初步方案作为遗传算法的部分初始种群，提高了遗传算法的搜索效率。

(2)对多行设备布局模型的改进，该模型是基于使综合物流成本最低这一目标实现的。适用于加工多种类产品的生产车间。

(3)对选择算子的改进。改进的选择算子提高提高了选优能力，减少了随机性所引起的误差，在选出最好个体的同时能保证种群的多样性。

[1] 杨国俊,陈健,孙思蒙,等. 基于遗传算法的车间布局优化研究[J]. 机械研究与应用,2016(1)：12-14.

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

[3] 叶连发,刘胜,包北方. SLP在H公司柴油机零配件生产车间布局优化中的应用研究[J]. 现代管理技术,2012(5)：24-28.[4] 张屹,卢超,张虎,等. 基于差分元胞多目标遗传算法的车间布局优化[J]. 计算机集成制造系统,2013,19(4)：727-734.

[5] 张志海,张岱峰. 基于遗传算法的氰酸酯树脂生产车间布局优化研究[J]. 山东交通学院学报,3011,19(3):80-83.

[6] 吴鹏.MATLAB高效编程技巧与应用：25个案例分析[M].北京:北京航空航天大学出版社,2010.

[7] 罗军荣,史烽,肖吉军,等.SLP技术在制造车间布局中的应用研究[J].企业科技与发展，2011(22)：11-14.

[8] 樊雪梅,王龙昭. SLP方法在粮食物流中心内部规划布局中的应用[J]. 物流技术，2012,31(7)：354-356.

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

[10] 李晨,宁红云.改进的遗传算法选择算子[J].天津理工大学学报,2008,24(6):1-4.

(编辑 李秀敏)

Workshop Facility Layout Optimization by Using Improved SLP and Genetic Algorithm

DENG Bing, LIN Guang-chun

(School of Manufacturing Science and Engineering, Sichuan University, Chengdu 610065, China)

The workshop manufactures multiple types of products, and has fixed entrance and exit. The paper uses the combination of improved SLP and genetic algorithm to optimize the layout of workshop facility, which reduces the cost of move of employee and product, improves the utilization of workshop and enterprise's core competitiveness. Firstly, according to the logistics analysis of the workshop, we use the improved SLP to determine the preliminary scheme of the layout of workshop facility. Then, we take the preliminary scheme as part of the initial population of chromosomes of genetic algorithm, and use improved genetic algorithm to calculate optimal facility layout scheme of case workshop. Using the improved SLP and the genetic algorithm to optimize the layout of workshop facility, we make up for the shortcomings of rely on experience and have a lot of constraints, improve the ability of the selection of genetic algorithm, reduce the error caused by random, ensure the diversity of population, and make the final layout plan more practical value.

workshop facility layout; systematic layout planning; genetic algorithm; optimization

1001-2265(2017)08-0148-04

10.13462/j.cnki.mmtamt.2017.08.039

2016-10-14；

2016-11-13

四川省科技计划项目(2015FZ0005)

邓兵(1991—)，男，四川绵阳人，四川大学硕士研究生，研究方向为机构学及工业机器人， (E-mail)1501848963@qq.com。

TH181；TG506

A