基于遗传元胞机的多态性作业车间布局建模

，，，

(浙江工业大学 机械工程学院，浙江 杭州 310014)

随着市场竞争的日益激烈，一类复杂产品大规模定制企业和产业集群下大型代工企业，其生产过程在订单、设备、工艺、批量和瓶颈等层次上越来越凸显形态和状态的多样性，对布局的柔性、鲁棒性和动态性需求逐步增强.在当前日益紧张的土地资源背景下，为寻求最佳设备配比、最低物流耗费、最大空间利用和良好的生产柔性，如何有效进行此类多态性作业车间的布局设计和优化，是未来研究的重点和热点.

现有研究表明：单一优化算法已无法满足多态性作业车间这一类复杂性、阶梯型车间布局的需求，两种或两种以上算法融合成为当前研究的新趋势.曾议等[1]提出基于遗传算法杂交策略的连续粒子群优化算法，提高了搜索效率和质量，提供了求解设备单向环形布置的车间布局问题的新思路；张屹等[2]在多目标遗传算法的基础上引入差分演化策略，集成了算法多样性和差分演化策略在解决复杂问题时收敛性强、覆盖范围广的特点，有效解决了多目标优化的生产车间设备布局问题；余世根等[3]建立了多目标、具有固定约束多态性车间的布局问题优化流程，证明遗传算法在求解具有固定约束车间多目标设备布局问题的有效性.Lee K Y等[4]提出一种改进遗传算法解决了具有内部结构墙和通道的多层设备车间布局问题；YKASO A等[5]提出了一种模拟动态布局问题的元胞自动机算法，算法引入尺度敏感性分析，增强了作业布局的自适应性.元胞机是一个时间和空间都离散的动力系统，具有强大的空间运算能力，已应用于材料、交通运输、车间调度等研究领域[6-9]，笔者采用元胞机时空高离散的方法框架模型，利用遗传算法优化元胞机演化规则，建立多态性作业车间布局遗传元胞机模型以获得更优的布局方案.

1 多态性作业车间元胞机框架模型

多态性作业车间的布局设计是指在多品种、多工艺、变批量，对布局多态性和鲁棒性要求高的生产作业车间内将加工设备、物料运输设备和通道等各种制造资源合理地放置在一个具有约束的二维空间当中，并且能够最大化的降低物料搬运费用、提高车间面积利用率和设备平均利用率.多态性作业车间不仅要满足产品的产量、产品的加工工艺、加工流程、各制造资源加工能力等要求，还要满足二维空间的几何约束条件，包括车间布局各方向长度不超出给定车间各方向长度、各制造资源间距必须满足最小缓冲要求等.元胞机模型是对客观世界抽象的结果，按照一定的局部演化规则进化，结合元胞机自身的结果特点，构建多态性作业车间布局元胞机模型，其表达式为

A={L2，Sf，N，R，F}

(1)

式中：A为多态性作业车间布局元胞机模型；L2为二维网格空间结构；Sf为中心设备元胞的状态；N为领域元胞的状态；R为布局约束条件；F为布局演化规则.

1.1 二维网格空间结构

如图1所示，多态性作业车间布局的元胞机模型由设备元胞、缓冲元胞及通道元胞组成.图1中的空间网格的大小是根据实际所要进行布局的车间大小按一定比例缩小后进行划分，对车间当中的设备、设备之间的缓冲空间以及通道进行标准化，均为单位网格的整数倍.

图1 多态性作业车间布局元胞机模型图

其中设备元胞在多态性作业车间布局元胞机模型当中需要占据多个网格，由中心设备元胞、辅助设备元胞组成，设备元胞的模型如图2所示.中心设备元胞控制周围的辅助设备元胞，从而确定设备元胞在空间网格当中的位置.

图2 设备元胞模型图

(2)

(3)

(4)

对于任意一行i上(j+z)列有

(5)

因此可得

(6)

式中Bz为其他元胞不同时刻状态值向量的综合.

中心设备元胞t时刻的状态属性表示为

(7)

式中：fn为设备的名称，静态属性；fs为设备摆放状态，动态属性，fs∈{0，1}，0表示横向摆放，1表示纵向摆放；vq为该中心设备元胞所在设备元胞的占用的纵轴网格数，动态属性，vq∈{vq，hq}；hq为该中心设备元胞所在设备元胞的占用的横轴网格数，动态属性，hq∈{vq，hq}；fo为设备元胞所需占用的网格数，静态属性，fo=vqhq；fl为中心设备元胞当前所在空间网格当中的所在位置(i，j)，动态属性；fc为设备的加工能力，静态属性；fr为设备的安装要求，静态属性，fr∈{0，1}，0表示设备可移动，1表示设备不可移动；fb为设备所需缓冲空间，静态属性.

缓冲元胞t时刻的状态属性表示为

(8)

式中：bs为缓冲元胞当前所在空间网格当中的所在位置(i，j)，动态属性；bf为缓冲元胞邻近网格(i+1，j)的元胞类别，动态属性；bb为缓冲元胞邻近网格(i-1，j)的元胞类别，动态属性；bl为缓冲元胞邻近网格(i，j+1)的元胞类别，动态属性；br为缓冲元胞邻近网格(i，j-1)的元胞类别，动态属性；bf，bb，bl，br∈{0，1，2}，0为设备元胞，1为缓冲元胞，2为通道元胞.

通道元胞t时刻的状态属性表示为

(9)

式中：ps为通道元胞当前所在空间网格当中的所在位置(i，j)，动态属性；pf为通道元胞邻近网格(i+1，j)的元胞类别，动态属性；pb为通道元胞邻近网格(i-1，j)的元胞类别，动态属性；pl为通道元胞邻近网格(i，j+1)的元胞类别，动态属性；pr为通道元胞邻近网格(i，j-1)的元胞类别，动态属性；pf，pb，pl，pr∈{0，1，1}，0为设备元胞，1为缓冲元胞，2为通道元胞.

1.2 模型演化规则

演化规则是模型的关键部分，多态性作业车间布局元胞机演化规则有三条，即移位触发规则、缓冲控制规则和通道选择规则，具体如表1所示.

表1 多态性作业车间布局元胞机模型局部演化规则表

模型的演化规则当中的移位触发规则主要依据车间生产产品的工艺顺序和物流路线；缓冲控制规则主要是根据设备间的最小间隔；通道选择是根据物流路线.

2 基于遗传算法的元胞机演化规则优化

在模型中，利用遗传算法优化局部演化规则嵌套于元胞机模型，通过算法的反复迭代，直到满足终止条件，得到最优布局方案，下面利用遗传算法对局部演化规则进行优化.

2.1 染色体编码与解码

根据设备在网格内的位置和设备所需的缓冲空间，将布局编码分为位置选择染色体和缓冲染色体两个部分.根据两行设备布局编码方案，结合设备元胞在多态性作业车间中二维布置的特点，采用如下染色体编码方式：

(10)

解码就是编码的一个逆向过程，先根据位置染色体确定设备的网格位置，再根据缓冲染色体判断设备间的缓冲间距大小.根据每类产品的工艺顺序调整、推进布局方案的更新.

2.2 初始种群的获取

目前在研究车间布局问题的诸多算法中，广泛采用随机产生初始解的方式，但是这样无法保证所产生初始解的合理性和寻优过程的高效性，并且容易使寻优过程进入局部最优化，从而导致无法产生最优解.因此本文先通过使用SLP法(System layout planning，系统布置设计)进行分析计算，得到初步的布局方案，再对布局方案进行网格化和标准化，作为多态性作业车间布局的初始解，如图3所示.

图3 SLP法布局方案元胞模型化

2.3 适应度函数

鉴于适应度函数单值、连续及最小化等要求，将多态性作业车间布局多目标函数设为适应度函数如下：

F=min[ω1C+ω2(1-Ua)+ω3(1-Uf)]

(11)

式中：ω1，ω2，ω3分别为各个子目标的权重值；C为物料搬运费用；Ua为车间面积利用率；Uf为设备平均利用率.在不同作业车间的布局设计当中可根据决策者对各个子目标的重视程度不同，从而设定各个子目标的权重值(ω1+ω2+ω3=1)，即采用优先权值设定法，事先对各个子目标的权重值进行设定，将多目标优化问题转化为单目标优化问题.

2.4 选 择

选择方法采用轮盘赌选择法，在该方法中每个染色体个体都有机会被选中，而选择概率取决于群体中个体的适应度：

(12)

式中：i为种群中某一个染色体的编号；N为种群中所有染色体的数量，1≤i≤N；Pi为该染色体的选择概率.在这个过程，首先通过初始布局方案解的进化得到新的解集，比较各布局方案解的适应度函数值，适应度低的布局方案将被淘汰，适应度较高的布局方案得以进化寻求更优的布局结果.

2.5 交 叉

适应度较高的布局方案得以交叉进化，在交叉时根据染色体的不同采用不同的方法.位置选择染色体的交叉采用部分匹配交叉(PMX)的方法，先随机选取两个交叉点，然后交换两个父代个体中交

叉点的中间段，最后根据基因之间的映射关系来生成子代染色体，具体操作如图4中的案例所示；缓冲染色体直接采用两点交叉，随机的选择两个交叉点，然后交换他们之间的基因.

图4 位置选择染色体PMX交叉示意图

2.6 变 异

布局方案解除了进行交叉进化还可以利用变异获得更优的布局方案解，变异是种群按照变异概率Pm任选若干基因位改变其位置，它决定了遗传算法的局部搜索能力.变异分为两种：1)位置选择染色体采用交换变异方法，即随机选择两个变异位，然后交换两个位的基因；2)缓冲染色体采用实数变异方法.首先在[0，5]区间内建立一个2×n(n为设备数)阶矩阵作为初始化矩阵，上下两行对应位相减得到一个新的1×n阶矩阵，将该矩阵的每个位基因乘以一个1到变异长度的随机值，与Δ中相应的变异位相加并绝对值，产生一个新的实数来取代原来位的基因，具体操作如图5中的案例所示.

图5 缓冲染色体变异示意图

3 多目标函数

多态性车间布局当中由于产品的多样性和更新换代，导致产品工艺的不同，影响了布局设备的利用率.因此，在多态性车间布局的目标不仅是使物流费用最低，并且考虑到车间布局的美观性、投资成本以及布局设备的利用率，目标函数将车间面积利用率和车间设备平均利用率也考虑进去.

前述三个目标的目标函数如下：

1) 物料搬运费用最小，即

(13)

2) 车间面积利用率最大，即

(14)

式中：Ua为车间面积利用率；St为车间实际占地面积；Se为布局方案最终确定的布局结果总面积.

3) 设备平均利用率最大，即

(15)

通过权重加和法得到车间布局的多目标函数：

F=min[ω1C+ω2(1-Ua)+ω3(1-Uf)]

(16)

式中：ω1，ω2，ω3分别为各个子目标的权重值.

在多态性作业车间布局元胞机模型当中，通过设备元胞、缓冲元胞和通道元胞的调整和局部演变从而获得最优的布局方案.在模型当中，这三类元胞必须在布局网格以内，同时设备元胞之间满足最小缓冲空间要求，因此提出如下两条约束条件：

1) 边界约束

(17)

(18)

2) 缓冲约束

(19)

4 实例验证

表2 产品的工艺流程

表3 设备的外形尺寸和数量

表4 设备间物流量

图6 车间布局初始解

使用遗传元胞机算法进行车间布局优化，首先对布局初始解进行网格化和标准化，单位网格0.5 m×0.5 m，各设备单元化后的尺寸如表3所示.然后进行相关参数设定，遗传算法优化部分取迭代次数N=100，交叉概率Pc=0.7，变异概率Pm=0.001，将布局总目标作为适应度函数，设定权重ω1=0.4，ω2=0.3，ω3=0.3.获得适应度值最大解作为最终的布局方案如图7所示.对应三个子目标和一个总目标值如表5所示.

图7 车间布局最优解

表5 目标函数值

从表5中的各函数值可以看出：最终布局方案较初始方案能够有效的降低物料搬运费用，提高车间面积利用率和平均设备利用率，获得更优的布局总目标，因此所提出的遗传元胞机模型在解决多态性作业车间布局问题方面可行、有效.

5 结 论

作业车间布局是车间设计规划中的重要一环，其结果直接影响生产系统的经济性、安全性和整体效率.将元胞机与遗传算法相结合用于求解多态性作业车间布局优化问题，通过布局实例的初始解和最优解相比较，验证了元胞机和遗传算法相结合的算法在求解多态性作业车间布局问题具有可行性和有效性，能够提高布局性能，为解决多态性作业车间布局问题提供了一种新方法.但目前关于多态性作业车间布局问题的研究还不完整，在考虑布局因素时只提及了物料搬运费用、车间面积利用率和设备利用率，在今后的研究中，希望将更多的不确定因素加入模型进行探讨.

参考文献：

[1] 曾议，竺长安，沈连嬉，等．基于群智能算法的设备布局离散优化研究[J].计算机集成制造系统，2007,13(3):542-549.

[2] 张屹，卢超，张虎，等.基于差分元胞多目标遗传算法的车间布局优化[J].计算机集成制造系统，2013,19(2):727-734.

[3] 余世根，鲁建厦.基于GA的固定约束条件下多目标车间设备布局问题研究[J].浙江工业大学学报，2010,38(4):401-405.

[4] LEE K Y， ROH M I， JEONG H S. An improved genetic algorithm for multi-floor facility layout problems having inner structure walls and passages[J]. Computers and Operations Research，2005,150(32):879-899.

[5] YKASO A， NABIL N， GIND Y. A simulated cellular automata algorithm for the dynamic layout problem [J]. Computers and Operations Research，2010,155(28):1403-1426.

[6] 陈勇，阮兴聪，鲁建厦，等.基于元胞机和改进GA的大型零件柔性作业车间调度算法[J].中国机械工程，2012,23(21):177-184,190.

[7] 陈勇，阮兴聪，王亚良.基于元胞机的大型机械构件生产车间柔性调度求解[J].浙江工业大学学报，2011,39(4):433-439.

[8] 陈勇，潘益菁，王亚良，等.多态性作业车间鲁棒调度CA-GA建模[J].浙江工业大学学报，2014,42(2)：124-131.

[9] 陈向东，金先龙，张晓云，等.基于元胞自动机的路面车流荷载[J].上海交通大学学报，2008,42(6)：870-873.