随机型装配线平衡与缓冲区配置集成优化

刘雪梅， 刘 涛， 顾佳巍， 李爱平

(同济大学 机械与能源工程学院，上海 201804)

线平衡和缓冲区配置是装配线设计的两个核心环节，通常先进行装配线平衡，再进行缓冲区配置.对于操作时间不确定的装配线平衡问题，一般通过操作时间概率分布或模糊时间的方法进行求解.在装配线平衡方案确定后，各工位工作节拍不可能完全相同，且装配线运行过程中会受到操作时间波动的影响，需要在工位间设置合适容量的缓冲区，以避免生产停机.由于工位时间的变化对缓冲区配置以及整线生产率产生较大影响，先平衡再缓冲区配置的串行优化模式，难以得到全局最优的结果[1]，因此，随机装配线平衡问题应与缓冲区配置问题集成考虑.

缓冲区配置问题BAP(buffer allocation problem)是要确定缓冲区的合理容量和适当位置，主要目的是使串行布置的各工位运行更为独立，以减少缺料和堵料导致的空闲时间，从而提高生产率.但是缓冲区会占用生产空间，增加生产成本.BAP常见问题有：给定缓冲区总容量最大化生产率，或满足生产率要求的前提下最少化缓冲区容量.在BAP问题中，通常各工位的生产率或操作时间已知，即生产线平衡方案已确定.工位操作时间和缓冲区配置存在复杂的交互影响，Hillier[11]针对无缓冲区装配线提出一种倒碗式的最优工位操作分配方式，认为这种方式可以有效提高装配线产能.与之对应，Harris[12]提出了一种倒碗式的缓冲区优化模型，在缓冲区总数一定的情况下，缓冲区最优配置的图案也呈倒碗的形状，但并没有相关研究评估这两种方式的交互作用.Boysen[13]认为工位时间的细微调整就可能引起缓冲区配置的巨变，平衡方案确定后的缓冲区优化忽略了这种影响.因此，生产线平衡和缓冲区配置顺序求解方法难以得到最优生产线方案.

本文针对随机型装配线设计问题，集成考虑装配线平衡和缓冲区配置优化，同时利用复杂性测度衡量工位操作时间随机性的影响，以生产率最大，工位复杂度均衡指数、标准操作时间均衡指数和缓冲区总数量最小为优化目标，改进遗传算法获取集成优化方案.

1 随机型装配线平衡与缓冲区配置集成优化模型

1.1 问题描述

本文针对的是工位间配置有限容量缓冲区的随机型装配线.优化问题可描述为给定一系列作业元素，作业元素之间的优先关系已知，作业元素的操作时间不确定，各工位缓冲区容量上限已知，在节拍和作业元素优先关系约束下将作业元素分配至给定工位，并合理分配缓冲容量，实现各工位负荷均衡、生产率最大和缓冲区总容量最小.

问题相关建模参数定义如下：

K为装配线上工位总数；k为装配线上第k个工位，k=1,2,3,…,K；C为生产节拍；N为作业元素数；i和j为作业元素编号；O为作业元素集合，O={1,2,…,N}；ti为第i个作业元素的操作时间，i∈O；Tk为第k个工位的标准操作时间；Bk为第k个工位的缓冲区容量大小；Sk为第k个工位的作业元素集合；Y为作业元素优先关系矩阵.

1.2 基于信息熵的工位复杂性测度

大多数随机型装配线平衡问题主要考虑各工位标准操作时间平衡，由于操作时间随机波动，容易导致平衡结果产生偏差，为了有效处理随机装配线的时间扰动，本文对工位复杂性进行测度，量化分析操作时间动态波动对装配线平衡的影响，结合静态时间优化目标，实现对装配线静、动态平衡综合优化，保证平衡方案的有效性.目前，信息熵是研究制造系统复杂性最为重要的手段之一，本节将基于信息熵理论提出一种装配线工位复杂性测度方法.

若存在离散随机变量X，则X的熵定义为

(1)

式中，pi≥0.如果X表示某系统，(x1,x2,…,xn) 和(p1,p2,…,pn)分别表示该系统n个可能出现的状态及其对应的概率，则E(X)为系统X的信息熵，是描述系统X时所需要的信息量，表征系统不确定性的大小.

装配线中工位操作时间的偏差可达20%[6]，潘国强[14]在电机装配线工位作业时间的统计中发现，人工工位作业时间呈近似正态分布，半自动工位作业时间呈近似三角分布，工位作业时间的最高偏差达23.3%.本文以作业元素实际操作时间的分布情况作为计算工位复杂度的状态，通过对操作时间波动性的研究，能够定量描述工位操作时间的不确定性，其大小取决于工位上作业元素操作时间可能出现的各个状态及相应概率.工位熵值越大，工位状态的不确定性和不可预测性越大，工位情况越复杂.

作业元素i的标准操作时间为ti0，经统计得到若干实际操作时间样本，将其与标准操作时间进行对比，分作以下m个区间(s1,s2,…,sm)，分别表示m种状态：操作时间为ti1～ti2,ti2～ti3,…,tim～tim+1；时间分段间隔为ε，间隔大小即划分粗细程度.根据具体实例，ti0与ti最小值之差为Δia，若ti0前分为m1个区间，则

(2)

ti最大值与ti0之差为Δib，ti0后分为m2个区间，则

m2=maxΔ1bε,…,Δibε,…,Δnbε

(3)

作业元素i操作时间所分成的m个区间分别为：ti0-m1ε～ti0-(m1-1)ε,…,ti0-ε～ti0,ti0～ti0+ε,ti0-(m2-1)ε～ti0-m2ε.

统计得到作业元素i的操作时间出现在这m个区间的概率分别为(pi1,pi2,…,pim)，第k工位作业元素数为nk，作业元素i的操作时间所处状态为ji，作业元素i出现ji状态的概率为piji.该工位上的操作依次进行，工位出现某一种状态的概率为p1j1p2j2…pnkjnk，所有状态出现的概率之和为1，即

(4)

根据信息熵理论，该工位所含平均信息量，即工位复杂度为

(5)

式中:Hk为第k工位复杂度.

1.3 优化模型的建立

1.3.1目标函数

工位复杂度为工位操作时间的不确定性给出了量化指标，如前所述，工位复杂度越高，则工位操作时间可能出现的状态越多，随机性越大.如果工位间复杂性差异过大，则会造成有些工位时常出现空闲和超载严重，甚至引起阻塞.同时，操作时间超过节拍要求，工人更容易出现操作失误，对生产进一步造成延误.因此，平衡规划阶段需要考虑工位复杂性，减少各工位间复杂性的差异，使各工位操作时间不确定性趋于均衡，以提高平衡的有效性.工位复杂性差异度目标函数为

(6)

式中：G为工位复杂度均衡指数；Hmax为各工位复杂度的最大值.

除了新引入的工位复杂性差异度这一动态平衡目标外，区别于传统基于工位标准操作时间均衡进行作业元素平衡分配的方法，本文考虑工位操作时间与缓冲区容量配置的交互影响，利用软件仿真获取装配线生产率，将生产率R、工位标准操作时间均衡指数M和缓冲区总容量B作为目标函数，以保证装配线性能.

其中工位标准操作时间均衡指数M定义如下：

(7)

式中:Tmax为工位标准操作时间的最大值.

缓冲区总容量B定义如下：

(8)

1.3.2整线生产率获取方法

生产率R作为优化目标之一，针对每一次生成的平衡分配与缓冲区配置方案，均需要准确评价，通过Matlab调用Plant Simulation软件仿真来得到准确的生产率，仿真流程如图1所示.

图1 调用Plant Simulation软件仿真过程

Plant Simulation是一款离散事件系统仿真软件，利用其面向对象建模的编程方法可以快速地实现系统建模，但是软件内无法实现多个生产线方案的自动建模比较.本文利用Plant Simulation软件的COM组件接口，在MATLAB中生成COM服务器并且访问COM组件，将作业元素分配和缓冲区配置的集成方案输入到Plant Simulation中，调用软件中的method建立仿真模型，之后执行仿真，在仿真结束时传回方案的相关数据，为生产线方案提供准确的生产率R的数值.

通过COM组件，MATLAB可以自动执行规划方案的仿真，而不需要人为搭建模型，执行仿真操作，同时可以和优化算法相集成，利用仿真精度高的优势来综合评估线平衡与缓冲区配置对装配线带来的交互影响从而支持优化算法的寻优过程.

1.3.3优化模型

综合上述内容，将作业元素集O={1,2,…,N}分配到K个工位上{Sk/k=1,2,…,K}, 并设置各个工位后缓冲区容量大小，集成优化的优化目标如下：

(9)

约束条件为

(10)

Sk1∩Sk2=∅(k1≠k2;k1,k2=1,2,…,K)

(11)

Tk

(12)

Bk

(13)

Y=(yij)N×N(i,j=1,2,…,N)

(14)

约束(10)表示每个作业元素都要被分配至工位；约束(11)表示每个作业元素只能被分配一次；约束(12)表示工位的操作时间必须小于装配线预设工作节拍；约束(13)表示工位的缓冲区大小必须小于装配线预设缓冲区容量上限，且最后一个工位不设置缓冲区；约束(14)表示N个作业元素的N×N优先矩阵,其中矩阵元素yij取决于作业元素i与作业元素j的先后关系.如果作业元素i是作业元素j的优先作业元素，则yij=1,否则yij=0.

2 算法设计

装配线平衡和缓冲区配置集成优化是典型的组合优化问题，随着问题规模的增加，搜索空间急剧扩大.遗传算法是最常用的解决组合优化问题的一种启发式算法，可以有效求解线平衡[15]和缓冲配置[16]等问题，但是遗传算法无法“记忆”较优的解，易导致求解速度慢或者出现早熟现象，本文针对所提出的集成优化模型，设计了一种改进的遗传算法来进行求解.

2.1 染色体编码方式

染色体编码采用结构体编码的直接编码方式，编码包括作业元素排序和缓冲区配置方案两个部分.其中，作业元素排序对所有需要分配的作业元素根据作业元素优先关系矩阵进行实数编码排序，缓冲区配置方案对应缓冲容量大小，编码长度为需要设置缓冲区的工位个数.编码结构如图2所示.

图2 染色体结构

2.2 染色体解码方式

为了得到包含作业元素排序与工位分配、缓冲区配置的完整设计方案，按顺序对染色体编码进行解码.首先解码得到作业元素排序，根据单个工位节拍上限按顺序将作业元素分配到各工位.然后结合装配线工位总数，解码缓冲区配置容量，得到缓冲区配置方案，从而得到装配线配置方案.

2.3 改进的遗传算法流程

针对所提出的集成优化模型，为避免最优方案丢失和出现早熟现象，设计了一种改进的遗传算法来进行求解，采用精英保留策略对最优解进行复制保留和变异处理，保证算法收敛性.求解分为3个阶段：

(1)根据工位数和节拍上限，生成作业元素分配方案，同时配置各缓冲区容量；

(2)通过仿真得到整线生产率，同时计算得到工位标准操作时间均衡指数和整线工位复杂度均衡指数；

(3)计算适应度值，通过图3所示改进的遗传算法流程循环保留最优方案.

改进的遗传算法流程如下：

(1)根据个体适应度值对种群中存在的个体进行排序；

(2)保留最优解并对其进行复制，保留解染色体不变，复制解对染色体缓冲区配置部分进行邻值变异；

(3)非保留解进行交叉变异.

(4)对新生成的染色体种群进行作业元素分配，判断新生成的方案是否满足工位数约束，若满足，则通过仿真计算得到适应度值；若不满足，进行惩罚使适应度值为0；

(5)当前种群个体按照适应度值排序；

(6)终止条件为限定的遗传进化代数或末位50代适应度值标准差低于设定值，判断是否满足算法收敛条件，若满足，根据个体适应度选择最优方案；若不满足，重复步骤(2)～步骤(6).

图3 改进的遗传算法过程

2.4 算法实现

2.4.1设定工位节拍上限

根据作业元素总的操作时间、工位数量等基本信息，估算出工位节拍时间上限，作为初始种群作业元素分配的工位操作时间约束.

2.4.2产生初始种群

根据作业元素优先关系矩阵挑选最前序作业元素生成优先级最高的作业元素集，并随机选择一个元素放入染色体，删掉已分配元素；然后，剩余元素中生成优先级最高的作业元素集，随机选择一个元素按序置入染色体，如此反复直至所有元素分配完成即生成一条染色体作业元素排序部分；缓冲区配置部分依次在缓冲区容量的上限值内进行随机取值；重复种群生成操作循环生成种群规模为z的初始种群.

2.4.3交叉变异算子

(1)交叉算子

选取两条染色体父代1、父代2，对作业元素排序部分进行交叉操作.交叉算子采用两点交叉法，设交叉概率为Pc，随机产生两个交叉点，得到父代1两交叉点间的基因段，如图4所示.在父代2中搜索该基因段的排列方式，将父代1基因段替换成新的排序方式获得子代1，同样的交叉过程获得子代2，如图5所示.由于交叉算子不破坏作业元素之间的先后顺序约束，所以生成的两个新作业序列是可行的.

对于缓冲区容量而言，由于不同工位间的缓冲区容量设置差异较大，不符合缓冲区容量变化的基本逻辑，因此对缓冲区配置编码不进行交叉操作.

图4 两点交叉算子随机选点

图5 交叉后子代编码顺序

(2)变异算子

设变异概率为Pm，选择一条染色体为父代，随机产生变异点，根据优先关系矩阵，对变异点后面的作业排序基因段进行重新排列，获得新的子代染色体，如图6所示.

图6 单点变异算子随机选点

对于缓冲区容量而言，单个缓冲区容量的最优结果往往在个位数的变化范围内产生，因此对缓冲区配置编码进行邻值变异操作，对每一个缓冲区的容量配置进行上下小区间的邻值变异操作.

2.4.4适应度评价

本文随机型装配线平衡与缓冲区配置集成优化的目标是：最大化装配线生产率，最小化工位复杂度均衡指数、标准操作时间均衡指数和工位间缓冲区配置总量.其中生产率和缓冲区容量设置直接影响到装配线生产效益和成本，工位复杂度均衡指数和工位标准操作时间均衡指数则直接反应工位负荷情况.

装配线的经济性评价指标P与单位时间装配线的产值和单位时间缓冲区总成本等有关，其中单位时间装配线的产值由生产率R与单个产品产值p求得；单位时间缓冲区总成本则通过单位容量缓冲区单位时间成本c与缓冲容量总数B求得

P=pR-cB

(15)

化简可得有效生产率P*，即

(16)

式中，生产率R通过软件仿真得到，cp-1即单个产品缓冲成本率，根据装配线实例可得其具体数值，记为c*.从工位生产负荷出发，工位负荷的大小和均衡与否会影响到装配线的实际生产过程，进而影响整线的经济性指标.

综上，适应度函数f(R,B,G,M)设计为

(17)

在染色体解码过程中，合理分配意味着不出现最后一个工位上没有作业或作业分配不完的情况.如果出现不合格的染色体，对其将进行惩罚，令适应度值为0.

2.4.5保留复制策略

为了尽可能将优秀个体保留到下一代种群中，本文采用精英保留复制策略，精英选择概率为PS，即选取这一代中a(a=zPS)个最优的个体直接进入下一代.同时对这a个最优个体进行染色体的复制，并对其进行缓冲区的邻值变异后进入下一代.

3 实例验证

以某汽车企业变速箱装配线分装线为例对本文算法进行应用验证.该变速箱分装线共有38个作业元素，遵循的优先关系如图7所示.作业元素用数字进行标识，每一个连接线前后分别为紧前作业元素和紧后作业元素.

该变速箱分装线共计8个串行工位，单个工位能够配置的最大缓冲区容量为5，生产线节拍上限C估算为65 s，各作业元素的标准操作时间和波动时间数据均已知.所有作业元素只存在前后顺序约束，并行作业元素无前后限制，单个产品缓冲成本率c*为0.043.

将作业元素i操作时间低于标准操作时间的部分分成3个区间，由于序号为24的作业元素标准操作时间与操作时间最小值之差最大为3 s.则作业元素i被分为4种状态：ti0-3 s～ti0-2 s,ti0-2 s～ti0-1 s,ti0-1 s～ti0,ti0～ti0+1 s，对应的概率分别为 (pi1,pi2,pi3,pi4)，经过区间划分，各作业元素标准时间和出现在4个区间的概率如表1所示.

图7 作业元素优先关系

表1 作业元素标准操作时间及其区间概率

Tab. 1 Standard operation time and its interval probability

iti0pi1pi2pi3pi4iti0pi1pi2pi3pi4iti0pi1pi2pi3pi411400.230.730.04141600.230.730.04271500.230.730.0421100.200.780.02151400.080.860.06281600.200.780.023230.070.100.600.0316900.100.880.0229900.100.840.06411000.980.02171300.200.780.02301200.200.780.0251300.080.860.06181200.080.860.063110000.940.0661100.200.780.02191100.10.880.0232220.070.400.500.0379000.940.0620310.250.400.320.03331300.200.780.028900.230.730.04211400.230.730.0434700.100.840.0691400.200.780.0222900.10.840.06351100.100.840.061011000.940.0623800.100.90036800.230.730.04111000.200.780.0224290.250.300.420.0337900.200.780.02121000.200.780.02251100.100.840.06381500.200.780.0213800.10.880.02261000.080.860.06

3.1 求解作业元素分配和缓冲区配置方案

在MATLAB2010b中编制求解程序，遗传算法参数设定为：种群规模z=200，精英选择概率Ps=0.2，交叉率Pc=0.3，变异率Pm=0.5，遗传迭代次数N=300，算法迭代收敛过程如图8所示，得到最优作业元素分配和缓冲区配置方案1如表2所示.优化后节拍C1=63 s，利用仿真和式(6)～式(8)得到装配线分装线生产率为R1=46.964 3 h-1，复杂度均衡指数G1=2.224 9，工位标准操作时间均衡指数M1=6.782 3，缓冲区总容量为20.

图8 算法迭代收敛曲线

表2 作业元素分配与缓冲区容量配置方案1

Tab. 2 Operation assignment & buffer configuration 1

工位工位作业元素标准操作时间复杂度缓冲区容量1[1,3,2,4]594.911 012[10,5,6,11,14]615.374 153[7,13,8,9,16,18]615.223 014[12,15,17,19,21]625.269 135[20,22,23,25]593.629 656[24,26,27,29]634.846 537[28,35,30,32]614.921 028[33,31,34,36,38,37]625.522 3/

3.2 考虑工位复杂度均衡与否的方案对比分析

对于随机型装配线平衡问题，常用的解决办法是假设操作时间服从正态分布，在装配线工位满足一定完工率的条件下，使平衡率最高、工位平均操作时间均衡[5].为了说明本文方法的有效性，利用随机数发生器产生的随机操作时间，对所得方案1进行仿真，仿真得到装配线完工率为0.94.将实例中的作业元素操作时间拟合成正态分布，利用文献[5]中的方法，以平衡率最高、工位平均操作时间均衡为目标，对模型进行求解，得到最优作业元素分配与缓冲区配置方案2.计算方案2的工位标准操作时间和复杂度，如表3所示.

该方案中，节拍C2=63 s，整线生产率R2=45.285 4 h-1，复杂度均衡指数g2=2.991 9，工位标准操作时间均衡指数m2=7.348 5，缓冲区总容量为24.方案1和方案2各工位标准操作时间分布对比如图9所示，各工位复杂度分布对比如图10所示.方案2与方案1相比，工位2、3、4的标准操作时间差异较大，与之对应，工位2、3、4的复杂度也不如方案1平稳，即整个分装线的2、3、4工位的操作时间不确定性更高，波动程度更大.考虑工位复杂度进行装配线平衡，各工位复杂性均衡程度明显提升，所得方案1比方案2提高25.64%.工位复杂度均衡表明各工位操作时间不确定性较为均衡，超载和空闲时间相差不大，减少不确定因素对装配线的影响，使装配过程更加平稳.与此同时，装配线生产率保持R1=46.964 3 h-1，工位标准操作时间均衡程度同样达到了较高水平，比方案2进一步改善了7.70%.同时，缓冲区配置的总量从24下降到20，优化率达到16.67%，因此，方案1在工位复杂度均衡、缓冲区总数量等方面均有较大优势.

表3 作业元素分配与缓冲区容量配置方案2

图9 各工位标准操作时间分布对比

图10 各工位复杂度分布对比

由此可见，两种优化方法得到的平衡方案整线生产率水平接近，标准操作时间均衡程度相差相对较小，整线工位复杂性均衡程度明显提升，相比方案2，方案1的优化效果如表4所示.

表4 方案1优化效果

3.3 集成优化与串行优化对比分析

为了验证集成优化方法的有效性，将集成优化与串行优化方法进行对比.在串行优化中，线平衡问题和缓冲区配置问题被拆分成两个问题，传统的线平衡问题首先以平衡率为目标进行线平衡优化，然后在线平衡的最优结果上再进行缓冲区的配置优化.使用所提的改进遗传算法，参数设置与集成优化相同，对目标函数进行适当修改，取消缓冲区配置部分，优化结果如表5所示，平衡率结果为96.83%.

表5 串行优化作业元素分配方案

在线平衡的最优方案基础上，再进行缓冲区配置的优化，以生产率最大为优化目标，仍采用之前提到的改进的遗传算法，用仿真方法得到方案的生产率值，算法参数设置与线平衡时相同，缓冲区容量优化结果为3-2-3-5-5-5-2，缓冲区总容量为25，生产率最大为46.639 1 h-1.集成优化和串行优化方案的对比如表6所示.

表6 集成优化和串行优化方案对比

由表6可知，相比串行优化，集成优化不仅可以达到同样的平衡率效果，且在进行线平衡优化的同时就考虑了整线工位复杂性和工位标准操作时间均衡等影响，最终的方案在保持较高的生产率水平的同时，在缓冲区配置的总数量方面有着较大的优势.集成优化可以一次同时得到包括工位操作分配和缓冲区配置的完整设计方案，且避免了串行优化可能因为早熟现象而得不到全局最优解的问题，因此集成优化比串行优化在计算效率和优化结果上均占有较大优势.

4 结语

针对随机装配线规划过程中线平衡和缓冲区配置优化问题，引入装配线工位复杂度均衡目标，并结合工位时间平衡、整线缓冲区总量最小和生产率最大化目标，构建了线平衡和缓冲区配置集成优化模型.通过软件仿真得到设计方案的准确生产率，采用改进的遗传算法进行优化方案求解.实例表明该方法可以在一次优化过程中得到线平衡和缓冲区配置的整体方案，在保持较高的平衡率、生产率的同时，工位复杂性更均衡，缓冲区总容量更小.

在进一步的研究工作中，将考虑装配线专机性能对装配作业元素可分配性的影响，增加操作分配时对专机属性的考虑，另外也将考虑设备布局和物流等的影响，从而扩大算法的适用性，获取更符合实际的优化方案.