混合算法求解装配线平衡与多技能工分配研究*

张国辉，焦迎涛，孙靖贺，张海军

(郑州航空工业管理学院 a.管理工程学院；b.航空工程学院，郑州 450015)

0 引言

装配线平衡问题旨在满足约束条件的前提下，组合并分配单元作业，以使各工作站工时尽可能相等，最大限度地提高装配线的整体效率[1]。楚克明等[2]运用自适应遗传算法求解混流装配线的排序问题，提高了求解搜索能力和效率。马东升等[3]研究了在考虑需求波动前提下，最小化资源成本和工作站成本的混流装配线资源配置问题。甘雅文等[4]研究了主客观因素交互影响下混合装配线的排序问题，建立以最小化工作站堵塞时间与最小化产品切换次数为目标的交互排序模型并进行了求解。

然而，由于装配线上每个工作站的操作工人存在技能差别，也会影响装配线的节拍和平衡。员工的多种技能能够有效的满足装配线各工位对不同技能的需求，提高装配线的灵活性。Süer G A[5]将熟练程度分为9个类别，根据熟练程度水平，使用标准偏差值计算员工的操作时间。杨红光等[6]考虑人力资源和空间等约束的前提下，构建了以最大化装配线产能和最小化人员成本为优化目标的装配线人员再分配模型。李爱平等[7]针对装配关系复杂性影响工人工作效率进而导致产生瓶颈工位的问题，提出一种考虑装配关系复杂性的改进型多目标装配线平衡优化方法。然而，已有文献中更多关注人力成本约束问题[8]，考虑到员工技能等级和员工技能训练提升等因素，同时将工位分配和装配线平衡集成的研究较少。

本文构建多技能员工分配和装配线平衡集成的数学模型，以装配线的平衡率和员工技能强化训练的收益最大为优化目标，采用混合粒子群遗传算法(Particle swarm optimization and Genetic algorithm，PSOGA)进行求解，并通过实际案例进行不同算法运算结果对比，验证了建立的模型和提出的方法是可行和有效的。

1 问题描述与模型构建

多技能员工分配和装配线平衡问题可描述为：现有m个不同技能的员工和n个工作站(m≥n)，工作站的编号为j(1≤j≤n)，装配的顺序已知，且按照工作站的序号进行。每位员工i(1≤i≤m)完成工作站j作业时间集为Tij。采用最大最小原则确定节拍，对不同工作站中最小的作业时间作比较，选取其中最大作业时间的工作站作为瓶颈工作站，并设定为该装配线的节拍(CT)。员工的技能水平划分为4个技能等级，并对其实际达到的技能状况进行分级评估。按熟练程度由低到高依次分为一级、二级、三级和四级，其中三级员工的作业时间为标准工时。不同工作站需要的技能不同，也就是说有的员工并不能在所有操作站上进行分配。每个工作站上的员工通过从事低技能水平的工作，从而提高技能水平，获得技能训练收益。

本文在进行多技能员工分配时假设条件如下：

1)每个员工同时只能在一个工作站上工作，每个工作站仅能分配一个员工；

2)每个员工的技能范围和水平已知；

3)三级员工的标准工时已知；

4)员工技能水平每提高一个等级作业时间减少10%；

5)技能训练的收益受限于工作站可从事员工数；

6)员工作业时间大于瓶颈工作站的工作时间时，删除该员工技能。

建立两个优化目标：

目标1：装配线的平衡率(LOB)最高，如式(1)。这个目标也相当于最小化装配线的平滑度指标，减少CT和Tij的总偏差。

(1)

目标2：员工技能训练的收益最大，如式(2)。这个目标函数用于提高多技能员工分配所获得训练收益(En)，其中pj表示不具备工作站j所需技能的员工个数。

(2)

采用加权方式对f1和f2合并为目标函数f，如式(3)。w1，w2是表示f1和f2重要程度的参数，其值可以根据对于装配线平衡和技能训练之间的重视程度进行选取。

f=w1×f1+w2×f2

(3)

其中，w1+w2=1。

(4)

目标函数中的变量和约束说明如下：

(5)

(6)

(7)

(8)

式(5)表示节拍的确定；式(6)表示员工是否被分配到相应工作站上的决策变量；式(7)表示员工i仅分配一个工作站；式(8)表示工作站j仅分配一名员工。

图1 PSOGA的算法流程图

2 混合粒子群优化算法

粒子群优化算法是模拟鸟类觅食行为的一种群智能优化算法，因其操作简单、易于实现而得到广泛应用于解决连续和离散优化问题[9-10]。本文将粒子群优化算法和遗传算法进行结合，提出混合粒子群优化算法，算法流程框架如图1所示。为了能够更好地平衡算法求解过程中的全局搜索和局部搜索能力，并且提高算法的运算效率和解的质量，设计了定向变异和局部搜索算子。

2.1 编码

好的编码方式容易在后续操作中产生可行的解决方案，避免不可行的解决方案带来的补救措施，能够提高效率。

PSOGA中编码采用员工编号的十进制编码方法。n个工作站分配m(m≥n)个员工，每个工作站一个员工。分配给n个工作站员工的粒子表示为P=(π1,...,πj,...,πn)。其中j为1～n的排列，πj由1～n的随机非重复序列表示，如图2所示π6=5，表示工作站6由5号员工承担。

图2 编码方法

2.2 位置更新和速度更新

粒子群算法通过速度更新和位置更新实现粒子更新，主要用于求解连续无约束优化问题。PSOGA由于员工分配问题的离散性与传统的粒子速度和位置更新方式不同。员工分配问题中粒子速度Vt(Vt是行为工作站数m，列为粒子数的矩阵，即为交换序1)，t是目前迭代次数，初始所有粒子的速度V1为随机生成矩阵，矩阵数值上限为n，下限为0。Vt+1是Vt中的数值以概率z(z为惯性系数，随迭代次数增加而递减)保留，未保留的数值将变为0。交换序2表示Pbest(个体最优粒子)对粒子位置的影响。交换序3为Gbest(全局最优粒子)对粒子位置的影响。交换序2和交换序3的确定方式为，从Pbest中取出元素i，然后从个体中取出元素k，如果两个元素值相同且k≠i，则计交换序2的第i个元素值为k。同理确定交换序3。交换序2和交换序3的数值分别以概率c1和概率c2保留，未保留的数值将变为0。交换序1、2、3分别和粒子群中的每一个粒子进行交换即通过粒子速度、Pbest、Gbest实现粒子位置更新。具体更新方式为：如图3找到粒子中与交换序第1个元素对应数值5相同数值所在的元素5，将粒子元素5的数值和元素1的数值进行交换。当交换序中数值为零则不发生交换，同理执行其他元素的交换。

图3 位置更新

通过将粒子当前位置Xt和交换序1、2、3依次发生交换后实现粒子位置更新Xt+1，其中z的值随着迭代次数(Iteration)的增加而减少服从公式(9)，其中maxInteration为最大迭代次数。

z=0.96-Iteration/maxIteration

(9)

2.3 粒子交叉

粒子交叉操作是随机选中一段粒子片段与Gbest的相同位置片段进行交叉，保留粒子交叉前后的最优粒子。由于交叉后会存在相同元素值，而模型和算法本身不允许存在相同元素值，删除个体中元素值相同的元素，保留交叉前后最优值作为更新后的粒子。生成随机数r1，r2，使得r1≠r2，如图4所示。假设r1=6，r2=4，对于个体粒子P1=[1 6 5 7 3 8 4 2 9]选取第4～6元素的数值F1=[7 3 8]和全局最优粒子G1=[7 3 1 8 6 9 2 4 5]的第4～6元素的数值F2=[8 6 9]交换。由于交叉后会存在相同元素，而模型和算法本身不允许存在相同元素，删除个体P1中与F2中元素值相同的元素得到F3=[1 5 7 3 4 2]，将交叉片段F2插入到F3中第r(r=min(r1，r2))个位置。更新后的个体P2=[1 5 7 8 6 9 3 4 2]，计算P1和P2的适应度值，保留交叉前后最优值作为更新后的粒子。

图4 粒子交叉

2.4 粒子变异

为了提高种群的多样性，避免过早收敛的发生，采用随机变异和定向变异两种方法。

(1)随机变异

为了保证粒子群的多样性，避免陷入局部最优。将群体中80%的个体进行随机变异，随机选择两个元素进行交换，并且计算交换前后的适应度值，保留变异前后最优适应度值的粒子作为更新后的粒子。

(2)定向变异

为了使变异更有效、变异结果更好，将群体中20%的个体进行定向变异。定向变异通过计算变异点全部可能发生的变异收益，从收益最大的若干个可变异选项中随机选取一项作为变异点的变异结果。对于粒子P1，随机数r5=3，P1的第3个元素π3=5，表示当前工作站3上由5号员工工作，所需时间为T53，由于同一员工操作不同工作站熟练程度和等级不同，所需时间不同。假设3号工作站由4号员工操作，那么如图5所示，工作站3、7的操作时间由T53变为T43，T47变为T57。然后，计算交换变异前工作站和变异后工作站所需时间和的差值Q(b)，其中b为变异点定向交换的工作站序号，Q(b)越大变异收益越大。如图5中，变异点3，定向交换7号工作站，Q(7)=T43+T57-(T53+T47)，同理依次计算剩余可与工作站3上5号员工交换的工作站的Q(b)值。最后，根据不同的Q(b)值，按照下列伪代码选取更新变异后的个体。

图5 定向变异

定向变异的执行伪代码如下所示：

Input:交叉后的粒子1If所有Q(b)<=02 原始粒子P1不进行变异,不更新个体3ElseifQ(b)>0的数目大于34 在排序前三的变异个体中,随机选择一个5Elseif6 选择最大值的变异个体7EndOutput:变异后的粒子

2.5 局部搜索

为了提高PSOGA的搜索能力，在算法中增加了局部搜索。当每一代迭代结束时，将执行局部搜索。每个粒子中随机选择3个工作站，如图6所示，随机选择工作站1、3和4，即交换工作站的工作人员，可形成6个邻域解。

图6 邻域解的产生

3 实例验证与结果分析

为测试算法性能，用提出的混合粒子群优化算法(PSOGA)与标准粒子群算法(PSO)、遗传算法(GA)进行对比。算法在Matlab2016软件编程环境，在2.3 GHz、4.00 GB RAM DELL XPS13计算机上执行。如表1所示，参数w1和w2设定了三种组合进行计算。①仅考虑装配线平衡率[1,0]；②同时考虑装配线平衡率和多技能工的技能培训收益[0.5,0.5]；③优先考虑多技能工的技能培训收益能力[0,1]。测试数据来源于断路器装配车间实际生产问题，该装配线包括21名员工，16个工作站，如表2所示，表中“-”表示当前员工的技能不能满足当前工作站的需要，即不能分配到该工作站上。

表1 参数设置

表2 工作站操作时间 (单位：s)

续表

如表3所示，分别采用PSOGA，PSO和GA这3种方法对表2中的数据进行计算得到结果，算法运行10次的平均值。第1列是3种算法，第2列是不同的权重设置，第3列是目标函数平均值，第4列是获得的最优值，第5列是算法运行的时间平均值。从表3中可以看出，PSOGA和GA的计算能力非常好，每次都能找到这个实例的最优解，PSO相对较差；PSOGA在其求解能力与GA相当的同时收敛速度快于GA。PSO在计算时间上约为1.2 s，PSOGA约为2.1 s，GA约为9 s。从计算时间和优化结果综合比较，本文提出的GAPSO算法更有优势。由于表2中的问题规模较小，表3中的实验结果的区分度不够明显，经过大规模问题的实验可以得出本文提出的PSOGA是非常有效的，但是限于篇幅有限，大规模问题数据的验证不再赘述。

表3 不同算法的计算结果

图7显示了这3种算法迭代过程中每代最优个体的适应度结果。红色曲线代表PSO，深色曲线代表PSOGA，浅色曲线代表GA。PSOGA和PSO算法期初波动较大，GA期初波动较小，说明PSOGA期初种群的多样性保持的比较好，不容易陷入局部最优；GA相对较早搜索停滞，不再更新，PSO最后得到算法最优解，PSOGA算法相对其他两种算法得到最优个体。如图8所示，为所得员工分配示意图。

图7 每代最佳个体适应值迭代图

图8 员工分配示意图

4 结束语

本文考虑了多技能员工分配和培训问题的装配线平衡问题。提出了一种混合粒子群优化算法，用于平衡装配线和提高员工技能训练的收益，以期望获得更合理的多技能员工分配方案。本文利用混合粒子群算法、粒子群算法和遗传算法进行了不同规模的实验。计算结果表明，混合粒子群算法在解的质量和时间上优于粒子群算法和遗传算法。同时，验证了混合粒子群算法在解决多技能员工调度问题上的可行性和有效性和稳定性。

对此，后续研究可以更多关注多技能员工的分配对复杂装配系统各个方面的影响；设计更好的算法或调整算法的结构组件，以获得更好的结果；考虑到员工的精神疲劳、学习能力以及多技能员工分配的及时性，希望能够实现更加全面的分配目标。