装配线平衡问题(assembly line balancing problem, ALBP)是求解装配线上作业元素在各工作站的分配方案，使装配线在满足作业先后顺序约束的同时，各工作站单件作业时间接近, 且不超过生产节拍，达到装配线利用率最大。装配线的平衡质量直接影响生产效率、生产成本和产品质量^[1-3]。根据装配线上作业人员的操作方位，装配线可分为单边装配线和双边装配线两大类。双边装配线主要用于满足大型产品(例如汽车、冰箱等)的装配需求，与传统的单边装配线相比，双边装配线具有能缩短装配线长度，减少产品的下线时间，降低工装、夹具及物料处理的成本等优点^[4]。因此，双边装配线平衡问题(two-sided assembly line balancing problem, TALBP)的研究越来越得到学术界和企业界的关注。

文献[4]首次提出了双边装配线平衡问题(TALBP)。双边装配线平衡问题比单边装配线平衡问题要复杂，因为对于双边装配线，在将作业元素分配到各工作站时，需要考虑作业元素在装配线上的操作方位约束以及装配线两侧工作站组(装配线两侧相对的工作站)之间由于作业先后顺序约束所引起的不可避免的等待时间。随着国内外学术界对双边装配线平衡问题研究的不断深入，涌现出一些有关双边装配线平衡问题的建模与求解方法的研究成果。文献[5]提出一种基于工位编码的遗传算法来解决双边装配线平衡问题，但该方法不能搜索整个可行解空间，只能得到局部最优解。文献[6]针对装配任务的相关度及任务安排上的松弛度的平衡问题，釆用多个启发式算法，以提高任务之间的相关度和不同工作站任务之间的松弛度。文献[7]提出一种基于“序列组合”(作业序列和作业方位组合)编码方法的遗传算法，提高了可行解的搜索效率。上述研究成果均是针对单一品种双边装配线平衡问题进行的研究。为了适应市场需求的多样化，多种产品混流生产成为主要生产模式。为了解决多种产品混流生产的问题，文献[8]提出了双边混流装配线平衡的第一类问题，以工作站组数目、生产节拍、工作站数目最少为目标，构建了多目标函数，并对双边混流装配线平衡的多目标优化问题进行了研究。文献[9]针对双边混流装配线平衡问题的特点，提出了一种改进蚁群算法，得到了作业分配方案。文献[10]考虑了并发操作的情况，建立了具有并发操作约束条件的双边混流装配线数学模型，并给出了遗传算法求解过程。文献[8, 10]均假定装配作业时间为常数，而在实际生产环境下，特别是以手工作业为主的装配线，作业时间具有随机性，文献[11]在考虑双边装配线平衡特点的前提下，提出了一种具有操作方位约束的任务优先分配的启发式算法，得到不同的平衡方案，取得了较好的效果，但该研究是针对单一品种装配线进行的。

文献[12]针对混合装配线存在的不确定性问题，基于数学模型对不确定性因素进行了分析，并采用eM-Plant建模，通过系统仿真研究不确定性因素对混合装配线平衡的影响；文献[13]考虑随机混流装配线的特点，提出了一种混合粒子群算法来求解随机混流装配线平衡问题；文献[14]提出了一种基于集束搜索的算法来解决随机型混流装配线平衡问题。

文献[12-14]均是针对单边混流装配线平衡所做的研究，目前针对随机型双边混流装配线平衡问题的研究成果很少，而在企业生产实际中，双边混流装配线平衡问题普遍存在，特别是作业时间的不确定性对双边混流装配线平衡的影响不容忽视，因此对于随机型双边混流装配线平衡问题(stochastic two-sided mixed-model assembly line balancing problem, STMALBP)的研究更具有实际意义和研究价值。

1 STMALBP描述与数学建模 1.1 STMALBP描述

双边装配线是指在装配线的左右两边都设有作业工作站的装配线，装配线左右两边相对的两个工作站成对称分布，这一对工作站称为工作站组(mated-station)，而同一工作站组中的两个工作站互称为对方的伴随工作站(companion)^[4]，如图 1所示，该双边装配线包含5个工作站组。

假设双边装配线上有M种产品需要装配，这些产品的结构相似，工艺相近，每种产品的装配由若干个作业元素组成，各作业元素之间满足一定的先后顺序关系。D_m为计划期T内对产品m(m = 1, 2, 3, …, M)的需求量，全部产品的总需求量=D。在STMALBP中，各作业元素的作业时间服从某一随机分布(一般熟练工的作业时间满足正态分布)，假定产品m的作业元素i的作业时间t_mi服从正态分布，t_mi~N(μ_mi, σ_mi²)，其中μ_mi、σ_mi²分别表示产品m的作业元素i的作业时间期望值和方差。基于上述假设，研究STMALBP，根据节拍和作业先后顺序约束把各作业元素分配到各个工作站中，使得工作站组数目最小。

在双边装配线中，分配到同一工作站组的两个工作站中的作业元素可能由于作业先后顺序关系的约束，导致产生不可避免的“等待时间”，如图 2所示。

图 2中，如果作业元素3是7的先行作业元素，装配线右边工作站在完成作业元素2后不能马上开始元素7的作业，而需要等元素3完成后才可以开始，从而产生了与作业元素3相关的“等待时间”。因此，双边装配线平衡问题与单边装配线平衡问题不同，在计算工作站作业时间时，不可以把分配到该工作站所有作业元素的作业时间直接相加，而需要把“等待时间”作为该工作站作业时间一部分，即工作站的作业时间等于所有作业元素时间与该工作站的“等待时间”之和。

在随机型双边混流装配线平衡问题中，由于不可避免的“等待时间”的存在，增加了问题的建模与求解的复杂性，为此本文提出一种将遗传算法和仿真分析相结合的两阶段求解方法，以简化问题的建模与求解过程。遗传算法具有良好的搜索能力和优化特性，能够有效寻找出装配线平衡问题的较优解。由于遗传算法是基于简化模型进行搜索的，搜索方向可以确定，但不能保证解的质量，因此，遗传算法所得到的解只能作为备选解。仿真方法是分析和求解随机性问题的有效方法，通过仿真分析，对备选解进行筛选，从而获得满足约束条件的随机型双边混流装配线平衡问题的最优解(或次优解)。

1.2 不考虑等待时间的STMALBP数学建模

双边装配线平衡问题是将产品的作业元素分别分配到装配线左、右两边工作站中，在满足作业元素先后顺序关系约束和节拍要求的前提下，使得工作站组的数目最小。如前文所述，当考虑同一工作站组左右两个工作站之间作业元素先后顺序关系约束的情况时，可能产生不可避免的“等待时间”，增加了数学规划模型的复杂性，因此，暂时不考虑“等待时间”。

基于如下假设条件建立问题的简化数学规划模型：1)问题所有输入参数均为已知；2)各个作业元素作业时间t_mi之间互相独立，各个工作站之间互不影响；3)混合排产生产的产品结构相似，工艺相近；4)不考虑并行操作和作业“等待时间”的情况。

对于一般熟练操作工，其作业时间满足正态分布，为此假设作业时间t_mi服从正态分布，即t_mi~N(μ_mi, σ_mi²)，其他相关变量说明如下：

C表示装配线节拍(指连续相同的两个产品的下线时间间隔)；

I表示双边装配线上所有作业元素集合，I = {1, 2, …, i}；

P(i)表示作业元素i的先行作业元素的集合；

A_L、A_R表示分别分配到双边装配线左边、右边的作业元素的集合，A_L、A_R∈I；

A_E表示既可以分配到左边又可以分配到右边的作业元素的集合，A_E∈I；

t_mi、μ_mi、σ_mi²分别表示m型号产品作业元素i的作业时间、作业时间的期望值和方差；

N表示双边装配线上工作站组数目；

d(i)表示作业元素的作业方位

(n, d)表示工作站组n中的一对工作站，且(n, d₁)和(n, d₂)互为伴随工作站；

W_ind表示分配到工作站(n, d)中的作业元素集合；

x_ind表示作业元素i分配到工作站组n、操作方位为d的工作站中，且当作业元素i被分配到工作站(n, d)时，x_ind的值为1，否则为0；

T_km表示m型号产品被分配到工作站k中的作业元素的作业时间，I_km表示m型号产品被分配到工作站k的作业元素集合；

x_i为决策变量，为作业元素i所分配的工作站的序号。

当作业时间为随机变量时，会导致整个工作站的作业时间成为随机变量，理论上，在确定合理的节拍后，很难保证工作站内作业时间都满足节拍的要求；所以，对于作业时间随机变化性的装配线，工作站作业时间T_km≤C(m=1, 2, 3…M)，只能以一定的概率α(0＜α＜1)来满足节拍的要求，即

，其中m=1, 2, 3, …, M。

令，Z~N(0, 1), 则。

根据标准正态分布函数Φ的性质，有：Φ^-1(α)≤，故而：T_km=+Φ^－1(α)·。

在随机型双边混流装配线平衡问题的第1阶段求解中，由于不考虑“等待时间”，在这种情况下，若仍然以给定的节拍C为工作站时间的约束条件，所求得的备选解可能会在考虑“等待时间”时，成为不可行解(即工作站时间超出节拍C)，为此，在问题的第一阶段求解中，引进一个适当的参数Δ，将节拍暂时调整为C'=C－Δ，STMALBP简化数学模型相关表达式如下。

(1)

(2)

(3)

(4)

(5)

(6)

式(1)表示目标函数，以最小化工作站组数目为目标；式(2)表示作业先后顺序关系约束，在式(2)中，a∈P(i)，b∈I-P(i)；式(3)表示操作方位的约束；式(4)表示所有作业元素被分配到工作站；式(5)表示每个作业元素只能分配给一个工作站；式(6)表示各个工作站的作业时间小于调整节拍C'，其中m=1, 2, 3, …, M，对于任一分配到各个工作站的k的产品的所有作业元素而言，它们都必须在调整节拍内完成作业。

2 STMALBP简化模型遗传算法求解

由于STMALBP问题的复杂性，本文采用两阶段求解方法。第1阶段采用遗传算法求解STMALBP简化模型。遗传算法求解装配线平衡问题主要有3种编码方式：基于作业序列号、基于工位号、基于序列组合的编码。在双边装配线平衡问题中，不仅要考虑作业元素分配的工作站，还要考虑该元素的作业方位。基于序列号的编码方式无法满足双边装配线平衡对作业元素操作方位的要求，而基于工位号的编码方式中需要对作业元素的装配顺序进行排序，增加了问题的复杂性。因此，基于序列组合的编码方式更适合双边装配线平衡问题。

2.1 基于序列组合编码方式

在基于序列组合的编码方式中，染色体各个基因由两部分组成：作业元素的序列号和相应的作业方位^[7]。即按照作业元素分配到工作站的先后顺序，将作业元素排成1列，染色体长度等于作业数，每个作业元素对应1个基因，其取值为作业元素i和其分配的方位d(d=L、R、E)的组合(i, d)。以P16问题^[11]为例，一条染色体的编码形式如图 3所示。

2.2 解码

解码时，将染色体从左至右依次进行解码，具体过程如下。

1) 开启第1个工作站组n(n=1)，根据染色体第i个基因代码d的值，判断第i个基因位对应的作业元素的作业方位，并将作业元素i分配到相应工作站当中(d=R，即分配到相应位置的右边工作站；d=L，则分配到左边工作站；d=E则随机分配到任意一边)。

2) 计算当前位置工作站的所有作业元素的作业时间T_km，判断当前工作站所有作业元素的作业时间是否小于或等于C'，如果满足要求(式(6))，分配到当前位置对应工作站。否则，开启下一个工作站组(n=n+1)，分配到对应的工作站中。如此重复前面两个步骤，直到染色体所有的基因解码完毕。同样，以P16为例^[11]，如果给定节拍为19，图 3所示的染色体解码的结果如图 4所示。

2.3 初始化

在遗传算法中，染色体初始化的目的是生成一组可行染色体。采用遗传算法求解双边装配线平衡问题中，染色体初始化是在保证作业元素先后顺序的前提下，通过随机方法产生初始种群：可分配的作业元素和相对应的作业方位序列。具体步骤如下。

1) 在作业元素集I中，找出所有无前序元素或前序作业元素已分配完的作业元素，并且放到集合Y当中。

2) 从Y中随机选择一个作业元素i，并将其跟该元素i在装配线上的作业方位d(L, R, E)相组合，作为染色体的当前基因值(i, d)，例如，(2, R)。

3) 重复前面两个步骤，直到Y中所有作业元素都分配完成为止，即完成一条染色体的初始化。

4) 重复步骤(1)、(2)、(3)X次，可以得到X条可行染色体，X就是初始化种群的大小。

2.4 适应度函数

装配线平衡问题的目的就是使平衡率最大化，因此把装配线的平衡率作为染色体的适应度函数(式(7))，Eval值越大，表明该染色体越优；采用轮盘赌选择操作，来进行选择和淘汰，即适应度值越大的染色体，被选择的概率越大。

(7)

2.5 交叉和变异

1) 交叉又称重组，是按较大的概率从群体中选择两个个体作为父代，通过交换两个父代的某些位上的基因，形成两个不同的子代个体。两点交叉是指在两个父代个体的染色体中设置两个交叉点，根据指定的交叉概率，交换两个交叉点之间的部分基因，图 5为两点交叉示意图。

2) 变异是将染色体中的某些基因进行互相交换，形成一个新的染色体，图 6为变异操作示意图。

2.6 算法终止条件

通常，当最优个体的适应度和群体适应度不再上升时，或者当前进化代数达到预设的代数时，算法终止。本文令当前进化代数达到预设最大遗传代数(例如100代)时，遗传算法终止。

3 考虑等待时间的STMALBP仿真方法

上一节已经完成了两阶段求解的第1步，本节将进行第2步求解，鉴于第1步的结果是在简化模型下完成求解的，该简化模型未考虑“等待时间”，因此本节通过eM-Plant软件建立考虑“等待时间”的仿真模型，对在简化模型下求解的备选结果进行仿真评价与分析，求得问题最终解。

在双边装配线中，由于“等待时间”的存在，因此不能把各个工作站中的作业元素时间之和作为工作站的作业时间，该等待时间关系可以通过下面的数学关系来表示，从而满足节拍要求。

(8)

(9)

式(8)中st_mi表示m型号产品作业元素i的开始操作时间，其中st_mi为m型号产品在工作站(n, d₁)中作业元素i的先行元素l的结束时间t_l以及伴随工作站(n, d₂)中作业元素i的先行元素r的结束时间t_r之间的较大值；式(9)表示对于所有作业元素i都要在节拍内完成(采用一种基于“任务在工位上开始装配时间”的方法^[15])。

eM-Plant软件是一个面向对象的图形化的建模和仿真软件，可以广泛应用于生产系统的仿真、优化^[16]。通过eM-Plant建立仿真模型，在模型中把备选解中所有工作站作业时间相应的“等待时间”考虑进去，图 7为考虑“等待时间”的随机型双边混流装配线的仿真模型示例图。

4 算例分析

以文献[10]中的实例问题进行求解分析，该实例是在某冰箱企业的一条双边装配线上，需要装配A、B、C、D 4种工艺相似的产品，其中箱体某个部分由20个作业元素组成，按照最小循环生产比例投产，设最小循环生产比例为6:6:5:5，4种产品的综合作业先后顺序关系如图 8所示。

A、B、C、D 4种产品的不同作业元素的作业时间如表 1所示。由于原问题没有考虑到作业时间的随机性，给出的是确定作业时间；对于一般熟练工而言，作业时间方差范围为1.2~2。因此，本文对参考文献中的作业时间作一些调整，取随机型模型中各个作业时间的均值为表 1中各个作业时间，方差为1.5(时间单位为s)。

鉴于遗传算法求解的是备选解，因此需要求得多组解，下面通过改变不同遗传代数来求一组(求解10次)备选解。在随机型模型中，预设概率与Φ^－1(α)的取值有关，如果Φ^－1(α)=1.280，则不超过节拍的概率为90%；如果Φ^－1(α)=1.960，则不超过节拍的概率为97.5%。根据以上条件，采用前面的STMALBP简化模型和遗传算法在Matlab中来寻找一组较优解。算法输入参数为，预设种群大小X=50，交叉概率P_c=0.7，变异率M_u=0.1，输入不同的最大遗传代数(取50~100之间)，当节拍C=20，Δ=0.1×C=2，在Φ^－1(α)=1.960时，求得结果如表 2所示。

为了进一步从上述分配结果中筛选出最优解，通过eM-Plant软件对上述备选解进行建模仿真分析。在仿真模型中，考虑作业“等待时间”，对10组备选分配结果进行仿真，通过修改模型中的随机数流，多次运行(每组运行10次)，得到的各个备选方案的平均平衡率如表 2所示。以第1个解为例，1{1L2E5L;3R4R11E}表示第1组工作站，工作站组1的左边分配的作业元素为：1、2、5，右边的作业元素为3、4、11。从表 2中可以看出，当不考虑作业等待时，第1个解的平衡率79%最高，工作站组数目4也是最小，理论上为最优解。通过eM-Plant建模，加入“等待时间”之后运行结果如图 9所示，第4个工作站组作业时间超过了节拍20，故而该解对应的分配方案淘汰。通过对所有的候选解进行多次仿真之后，各个备选解的平均平衡率统计结果如表 2所示，比较各个备选解在仿真模型多次运行下的平均平衡率，可知最优解为第6个，该解对应的工作站组数目为5，平均平衡率为92.7%。

由于离散事件系统固有的随机性，每一次仿真运行仅仅是系统模型输出的一次随机抽样，所得到的结果与系统“正真”的解可能有一定的差异，因此需要对仿真结果进行仿真输出数据分析。对模型独立运行多次，可以采用终止型仿真，并用固定样本长度仿真分析方法来分析仿真运行的结果。固定样本长度法是假定每次运行结果X₁, X₂, X₃，…，X_n除了满足独立同分布的条件外，还得是正态随机量，则随机变量X的期望值E(X)的估计值μ为^[17]：

(10)

(11)

其中，α为置信水平，n为仿真运行的次数。为了验证可行方案和仿真模型输出数据的可信度，对上述最优解对应的方案6进行终止型仿真分析，该模型在不同随机数情况下的输出统计结果(平衡率)，如图 10所示。

验证所输出的数据是否以一定的置信度(90%)在式(10)、(11)所计算的置信区间内，通过计算，结果如表 3所示，在α=0.1时，可以认为仿真模型输出结果以置信度为90%位于置信区间[0.891，0.963]上。

通过以上实例表明，本文所提出的基于遗传算法和仿真分析相结合的两阶段求解方法能够有效解决随机型双边混流装配线第1类平衡问题。

5 结论

本文针对双边混流装配线平衡问题，提出了基于遗传算法和仿真分析相结合的随机型双边混流装配线平衡问题的两阶段求解方法，并通过算例分析表明，该方法可以降低问题建模与求解的复杂性。本文只是对随机型双边混流装配线第1类平衡问题进行了研究，可以进一步研究第2类平衡问题；其次，在混流装配线中，往往不能以最小循环生产比例投产，还需要考虑投产排序给生产带来的影响，这些都将是后续研究的方向。