面向成本的双边装配线平衡和员工分配

邱玉莲，彭婵娟

（武汉科技大学 管理学院，湖北 武汉 430081）

1 引言

装配线广泛存在于制造业中，装配线的平衡与否直接关系到装配线的效率和企业的成本。作为一种特殊的装配线形式，双边装配线以其装配线长度短、搬运成本低等[1]优势广泛应用于汽车、卡车等产品的总装线上。

双边装配线平衡问题根据目标可主要分为两类：第一类问题[2-3]，给定生产节拍，在满足生产线约束条件的前提下最小化工位数量；第二类问题[4-6]，给定工位数量，在满足生产线约束条件的前提下最小化生产节拍。目前国内外主要研究集中于第一类双边装配线平衡问题，已有多种算法[2-3]应用于求解该NP难题。相较于第二类双边装配线平衡问题，目前仅有遗传算法[4]、蚁群算法[5]、粒子群算法[6]等用于求解该问题。由上可知，科研对第二类双边装配线的平衡研究很少，但是第二类双边装配线问题在实际中对于消除瓶颈工位、提高负载均衡有着广泛的应用前景。

以上研究均假设所有员工对相同操作的完成时间相同，但是在实际生产中由于员工技能的差异对相同的操作的完成时间可能不同[7]，例如残疾人完成需要站立的操作耗时巨大，因此在实际生产中需要考虑员工的分配问题。同时在企业的装配成本中，员工工资成本是其支出的主要部分[8]，所以企业越来越关注减少工资支出。由于工资成本的最优化与装配线的平衡可能出现冲突，所以需要采用多目标优化。

针对第II类多目标双边装配线平衡和员工分配问题，提出一种多目标重启模拟退火算法实现平衡和成本的同步优化。设计了新的编码和解码方式以实现工位负载均衡和减少序列相关空闲时间，采用了重启机制以获得分布性更好的前沿解。同时将重启模拟退火算法与快速非支配排序遗传算法进行对比，证明了算法的高效性。

2 双边装配线平衡和员工分配

2.1 问题介绍

在双边装配线上，如图1所示。左右两个工位合称为成对工位，每个工位上均分配有相应操作。第II类双边装配线员工分配和平衡问题可分为两个子问题，即员工分配和装配线平衡问题。在员工分配中，每个工位分配一个员工，其对同一操作的完成时间可能区别于其他员工。在装配线平衡中，每个操作在满足有限关系约束、方向约束的情况下被分配到对应的工位。

图1 双边装配线工位布置Fig.1 Task Assignment of Two-Sided Assembly Line

图2 操作数为12的优先关系图Fig.2 Precedence Diagram for 12-Task Problem

对应图1分配方案的优先关系图，如图2所示。图2中，共有3类不同操作，分别为：操作方向为左边的操作（L），操作方向为右边的操作（R）和操作方向为任意方向的操作（E）。图中，圆圈内的数字代表操作，圆圈上的标签代表操作的作业时间和操作的方向。圆圈间的箭头代表操作间的优先关系，以操作1和4间的箭头为例，其代表操作1是操作4的前序。

2.2 问题模型

为同步优化工资成本和负载平衡，分别设计了如下两个目标，如式（1）、式（2）所示。依次对应工资成本和负载均衡。为简化起见，以下主要说明两个目标函数，其它优先关系、员工分配等约束请参考相关文献[3，7]。

式中：i—操作；j—成对工位；k—成对工位的左右两边；J—成对工位集合；wi—单位时间内操作i的工资；CT—节拍；SFjk—工位（j，k）最后一个操作的完成时间；STjk—工位（j，k）分别的操作的加工时间总和；xijk判断操作i是否分配到工位（j，k），如果分配到工位（j，k）取值1，否则取值为0。

式（1）中工资成本设置文献[8]，其中单位时间内每个操作的工资水平由操作的难度决定，整个工位的单位工资水平由分配到该工位的最难的操作对应的单位工资水平决定。式（2）的前半部分最小化工位最后完成时间的偏差，后半部分最小化工位实际分配负载的偏差。

3 重启模拟退火算法

模拟退火算法广泛应用于各类优化问题，例如装配线平衡问题[2]。模拟退火算法是基于邻域的局部搜索算法，由于所研究的问题为多目标问题，设计了新的接受准则和重启机制。

3.1 编码及解码

由于考虑的问题涉及到装配线平衡和员工分配两个问题，所以采用了3个数组进行编码，分别为员工分配数组，操作分配数组和操作排序数组.以下以一个案例说明编码和解码情况，如图3所示。其中，员工分配数组中第一个位置的3表示，第一个成对工位的左边分配的员工编号为3.操作分配决定操作分配的成对工位，操作排序数组决定操作分配的优先级。为获得每个工位的详细分配的方案，采用文献[6]中解码方式获得满足优先关系约束和方向约束的分配方案。需要指明，以上解码可作为文献[4]中的解码的一种改进方式，其通过工位选择策略实现成对工位内部的负载均衡，通过操作选择策略有效减少工位上的空闲时间。

图3 编码及解码Fig.3 Encoding and Decoding Procedure

3.2 邻域结构设计

由于解码中涉及了3个数组，所以设计了3种不同的领域结构，介绍如下：（1）针对员工分配的领域结构：采用交换操作。（2）针对操作分配的邻域结构：采用随机选择交换操作和变异操作两个方式中的一种。变异操作随机选择一个操作，将其对应的成对工位变成其他成对工位。（3）针对操作排序的邻域结构：采用插入操作。在邻域结构的选择中，对应每个数组，随机产生一个0到1之间的小数，如果小于1/3，则对该数据进行变动。以上邻域选择方式允许变动多个数组，有效增大搜索空间。

3.3 帕累托解集更新及接受准则

当使用邻域结构产生一个新解后，如果该解没被其他任何解支配，则该解被添加到帕累托前沿解集，同时移除前沿解集中被支配的解。更新完帕累托前沿解集后，新产生的解替换原来的解S，即S←S′。当新解被前沿中的某个解支配，采用多项概率密度函数[9]从2个优化目标中选取一个以判断是否接受该解。在目标概率密度函数中，每个目标被选择的概率设定为0.5.假设选择其中一个目标f（*），则目标值的变化为Δ，Δ=f（S′）-f（S）。如果Δ≤0，则新解被接受并替代当前解。否则，按照exp-Δ/（T×f（S））的概率接受该新解，式中：T—温度参数。

3.4 重启机制

为增强算法跳出局部最优的能力，设计了一种重启机制以获取更多的前沿解，如图4所示。如果连续dn次迭代均不能发现新的前沿解，则从当前前沿解集中选择一个解作为代替当前解。改进聚集距离[10]做了如下改进：

（1）极值解的距离设定为1，而非原来的无穷大。

（2）将选择的次数融入到聚集距离中，且前沿解的聚集距离随着被选择次数的增加而逐渐减少。

图4 重启机制流程图Fig.4 The Procedure of Restart Mechanism

3.5 算法流程

在重启模拟退火算法中，连续执行NS次后邻域搜索后，对温度系数T按照T=αT进行更新，式中：α—冷却系数。详细算法流程，如图5所示。

图5 重启模拟退火算法流程图Fig.5 The Procedure of Restarted Simulated Annealing

4 实验结果与分析

为验证重启模拟退火算法的性能，生成了总共7组案例（P9，P12，P16，P24，P65，P148以及P205），并将重启模拟退火算法与快速非支配排序遗传算法进行对比[10]。每个员工对操作i的加工时间为［ti×0.8，ti×1.2］之间的随机数，ti为文献[4]中操作 i的加工时间。为比较不同算法的性能，采取了3个评价指标，分别为：非支配率、收敛性和分布性，其详细计算参考文献[3]。一般来说，非支配率的值越大，则该算法获得前沿解越好。收敛性越小，则算法收敛性越好。分布性越小，则算法获得的前沿解的分布性更好。

4.1 算法参数校验

所提出的算法采用多因素方差分析（ANOVA）进行参数校验。初始温度T0设置两个水平，即0.5和1；冷却系数设置3个水平，即0.9，0.95和0.98；每个温度下的迭代次数NS设置3个水平，即500，1000和2000；重启机制的促发次数dn设置为3个水平，即100，200和300.方差分析的结果，如表1所示。由可知α，NS和dn对应的P值均小于0.01，即存在显著性差异。按照P值递增的顺序依次选择每个参数的最优水平，满足95%最小显著差数间隔的置信水平的冷却系数各个取值，如图6所示。

表1 关于收敛性的多因素方差分析表Tab.1 VNOVA Results for Convergence

图6 冷却系数平均值Fig.6 Mean Plot for Cooling Rate

4.2 算法性能对比

为验证重启模拟退火算法的性能，重启模拟退火算法和快速非支配排序遗传算法分别对7组案例进行10次求解，算法的终止条件统一设定为运行时间t=nt×nt×10ms。算法的平均结果，如表2所示。由表2可知，针对非支配率，重启模拟退火算法在总共39个案例上优于快速非支配排序遗传算法。针对收敛性，重启模拟退火算法有36个案例都优于快速非支配排序遗传算法；针对分布性，重启模拟退火算法有34个案例优于快速非支配排序遗传算法。针对所有的大规模案例，P65，P148和P205，重启模拟退火算法在所有案例上均优于快速非支配排序遗传算法。

表2 算法的平均结果对比Tab.2 Comparison Results for Average Results

5 结语

针对双边装配线的员工分配和平衡问题，设计了最小化成本和最大化负载均衡两个目标，建立相关的多目标的优化模型。为求解以上NP难题，提出了一种重启模拟退火算法。在算法实践中，针对员工分配和平衡问题，分别设计了有效的邻域结构。为避免陷入局部最优，基于改进聚集距离提出了重启机制，以获得分布性更广的前沿解。为验证重启模拟退火算法的性能，生成了7组案例，并与快速非支配排序遗传算法的性能进行对比。试验结果表明，所提出的算法在收敛性和分布性上均优于快速非支配排序遗传算法。下一步研究可将重启模拟退火算法应用于其他多目标优化问题。

［1］J.J.Bartholdi.Balancing two-sided assembly lines：A case study［J］.The International Journal of Production Research，1993，31（10）：2447-2461.

［2］D.Khorasanian，S.R.Hejazi，G.Moslehi.Two-sided assembly line balancing considering the relationships between tasks［J］.Computers&Industrial Engineering，2013，66（4）：1096-1105.

［3］李大双，张超勇，邵新宇.基于多目标殖民竞争算法的随机型双边装配线［J］.计算机集成制造系统，2014，20（11）：2774-2787.（Li Da-shuang，Zhang Chao-yong，Shao Xin-yu.Balancing stochastic twosided assembly line with multi-objective colonial competitive algorithm［J］.Computer Integrated Manufacturing Systems，2014，20（11）：2774-2787.）

［4］Y.K.KIM，W.S.SONG，J.H.KIM.A mathematical model and a genetic algorithm for two-sided assembly line balancing［J］.Computers&Operations Research，2009，36（3）：853-865.

［5］郑巧仙，李明，李元香.求解双边装配线平衡问题的改进蚁群算法［J］.电子学报，2014，42（5）：841-845.（Zheng Qiao-xian，Li Ming，Li Yuan-xiang.An improved ant colony optimization for two-sided assembly line balancing problem［J］.Acta Electronica Sinica，2014，42（5）：841-845.）

［6］李梓响，唐秋华，林斌.第二类双边装配线平衡的混合粒子群算法［J］.机械设计与制造，2015（1）：113-116.（Li Zi-xiang，Tang Qiu-hua，Lin Bin.A hybrid particle swarm optimization for two-sided assembly line balancing problem of type II［J］.Machinery Design&Manufacture，2015（1）：113-116.）

［7］P.Th.Zacharia，Andreas C.Nearchou.A population-based algorithm for the bi-objective assembly line worker assignment and balancing problem［J］.Engineering Applications of Artificial Intelligence，2016（49）：1-9.

［8］A.Roshani，P.Fattahi，A.Roshani，M.Salehi，A.Roshani.cost-oriented twosided assembly line balancing problem：a simulated annealing approach［J］.International Journal of Computer Integrated Manufacturing，2012，25（8）：689-715.

［9］S.Kulturel-Konak，A.E.Smith，B.A.Norman.Multi-objective tabu search using a multinomial probability mass function［J］.European Journal of Operational Research，2006，169（3）：918-931.

［10］K.Deb，A.Pratap，S.Agarwal，T.Meyarivan.A fast and elitist multiobjective genetic algorithm：NSGA-II［J］.IEEE Transactions Evolutionary Computation，2002，6（2）：182-197.