基于改进水波算法的复杂多人共站装配线平衡研究
2024-02-21傅艳霞朱金辉邓率航
张 梅,傅艳霞,朱金辉,邓率航
(1.华南理工大学 自动化科学与工程学院,广东 广州 510641;2.华南理工大学 软件学院,广东 广州 510006;3.华南理工大学 大数据与智能机器人教育部重点实验室,广东 广州 510006)
1 问题的描述
装配线平衡问题是在满足装配任务约束的条件下,将所有作业任务(工序)分配到各个工作站上,同时在保证整条装配线连续生产的情况下,尽可能使每个工作站在节拍时间内的生产效率达到最大[1]。当前装配线平衡问题的研究主要集中在简单装配线[2-4],其特点是单个工作站只能容纳一个工人,且只能对单一类型的产品进行大批量流水装配作业,难以降低装配线的生产周期[5]。在实际装配过程中,由于产品体积过大或装配复杂度较高,形成了单个工作站在同一时间段内需要多个工人并行加工多道工序的多人共站装配线,其实现了装配线线长与生产周期更短、柔性更高,提高了装配线的空间利用率,如图1所示。类似于简单装配线平衡问题(Simple Assembly Line Balance Problem,SALBP),多人共站的装配线平衡问题(Multi-manned Assembly Line Balance Problem,MALBP)根据已知条件、优化目标的不同,可大致分为4类:第Ⅰ类多人共站装配线平衡问题(MALBP-Ⅰ)为给定生产节拍,最小化工作站数目;第Ⅱ类多人共站装配线平衡问题(MALBP-Ⅱ)为给定工作站数目,最小化生产节拍;第SI类多人共站装配线平衡问题(MALBP-SI)为给定生产节拍和工作站数目,最小化平滑指数;第E类多人共站装配线平衡问题(MALBP-E)为给定生产节拍或工作站数目,最大化装配线的线效率。相比于SALBP,MALBP研究较少,但在近几年来逐渐引起了人们的关注。DIMITRIADIS[5]最先提出了MALBP的概念,采用启发式算法对该问题进行求解。FATTAHI等[6]根据多人共站装配线的特点建立了MALBP的数学模型,并提出一种改进的蚁群算法用于解决该类问题。钱雄文[7]提出一种第II类多人共站装配线平衡问题,在给定工作站数量的前提下,最小化节拍时间。FANG等[8]针对飞机总装线中具有多阶段工作站的灵活工人分配问题,建立了以工作站节拍时间最小化、工作站和工人负载均衡为目标的整数规划模型,并提出一种改进的非主导排序遗传算法(NSGA-Ⅳ)求解了该问题的实例。还有一些文献在研究多人共站装配线平衡问题的基础上,考虑了工人负载均衡[9]、复杂约束[10-11]、生产成本最小化[12]以及柔性工作站[13]等因素。
图1 多人共站装配线示意图
上述文献涉及的多人共站装配线平衡问题一般都是考虑每道工序所需的工人数量相同的情况,而在实际生产中,不同工序装配的复杂程度不同,所需的工人数量也不同,对于复杂的工序,如大型设备的装配工序,需要分配较多数量的工人以工作组的形式共同协作完成;而对于简单的工序,则分配较少数量的工人完成。因此,对于这类问题,还需要考虑工作站内工作组间的工人调度,从而在装配线生产能力不变的前提下,尽可能地保持装配线平衡,优化装配线的生产成本。针对这类问题,本文提出一种复杂多人共站装配线,如图2所示,装配线上的工序沿着箭头方向顺序装配,不同颜色表示不同类型的工人,每道工序由一个或多个工人协同装配,需要根据工序的复杂程度,将工人以成组形式指派到各个工作站上,在每个工作站内,实线框内的工序为已装配的工序,虚线框内的工序为待装配工序,工作站内待装配工序所需的工人组根据以下原则进行指派:①待装配工序与已装配工序所需工人类型和工人数量一致,则工作组不需拆分,将其直接指派给待装配工序,如工作站1所示,将已装配工序1和工序2的工人直接重组并指派给待装配工序3;②待装配工序与已装配工序所需工人类型一致,而所需工人组的人数多于已装配工序,则需由工作组外工人(优先考虑工作站内其他被拆分工作组的工人,如不满足人数要求再从工人池中新增工人)补充进工作组,再指派给待装配工序,如工作站2所示,将工序4的工人与从工人池中新增的工人重新组合并指派给待装配工序6;③待装配工序与已装配工序所需工人类型一致,而所需工人组的人数少于已装配工序的工人数,则可将已完成装配的工人组拆成多组进行指派或在当前工作站中等待指派给后续待装配工序,如工作站3所示,将已装配工序7的工人组拆分为两组,其中一组1人指派给待装配工序9,另一组2人在工作站中等待指派;④待装配工序与已装配工序所需工人类型不一致时,则需按照待装配工序所需的工人数量和类型,从工人池中新增工人组,再指派给待装配工序,如工作站4所示,从工人池中新增一个工人组并指派给待装配工序12。
图2 复杂多人共站装配线示意图
水波优化(Water Wave Optimization,WWO)[14]算法是一种求解连续优化问题的新型智能优化算法,受浅水波模型的启发,WWO算法利用传播、碎浪、折射操作实现了解空间中的有效搜索,具有可调参数少、操作简单、易于实现等优点。近年,有研究者对该算法进行改进,用于解决实际车间调度[15]和车辆路径[16]等离散问题。王文艳等[15]利用块最优插入、交叉操作、多邻域搜索策略分别对基本水波优化算法的算子进行了改进,加入替换差解操作以协调水波优化算法的局部和全局搜索的能力,提高了算法的收敛速度,并与其他4种算法进行了对比,验证了离散水波优化算法在车间调度问题上的求解性能。张春苗等[16]针对车辆路径问题生成一个初始概率矩阵,基于该初始概率矩阵完成了初始化、传播、折射、碎浪操作,同时引入insert-opt与cross-opt等算子进行局部优化,最后通过标准测试用例实验验证了算法的性能。
综上,本文提出一种复杂多人共站装配线平衡问题(Complex Multi-manned Assembly Line Balancing Problem,CMALBP),考虑了实际生产中需要根据装配工序的复杂程度指派不同规模和类型的工人组协同装配工序的情况。此外,由于CMALBP相对于MALBP具有更加复杂的约束和任务分配限制,属于NP-hard问题,而精确算法难以求解大规模问题[17-18],因此,本文提出一种改进的离散水波优化(Discrete Water Wave Optimization,DWWO)算法,采用了基于拓扑排序的编码方案和启发式解码方案,并分别对传播、碎浪、折射算子进行了离散化改造,同时引入扰动个体和路径重连的搜索策略,提高种群的多样性,最后设计实验验证了DWWO算法求解CMALBP的有效性,并与其他算法进行了对比,进一步验证了DWWO算法的优良性能,同时基于实际动车装配线的生产数据给出了一个实例,从而验证所建模型的有效性。
2 问题分析与模型建立
2.1 问题分析
复杂多人共站装配线平衡问题(CMALBP)是一个复杂的组合优化问题,在MALBP的基础上,本文所研究的CMALBP考虑了以下两种特殊情况:
(1)多人协同装配一道工序 在装配过程中,由于某些工序所需的零部件体积过大或工序的装配复杂度过高,无法由一个工人独立完成,在为工序指派工人之前,需要考虑工序的复杂程度,在装配过程中指派工序所需类型和数量的工人,从而协作完成一道工序的装配,同时,已指派的工人组只能在工作站内调度,不在工作站之间流动。
(2)工人能力约束 工人类型由工人的技能来确定,装配某道工序的工人必须与该工序所需的工人类型相匹配,即每一类工人只能完成与其技能相匹配的工序的装配任务,同时假设掌握同一种技能的工人之间无能力差异,且每一道工序都只需要某一种类型的工人完成装配。
解决CMALBP的关键在于寻求一种最优的装配线平衡方案,在满足工序之间优先关系约束的前提下,合理地将工序分配到工作站上,使得每个工作站上的工序都能够在节拍时间内完成,同时,为每道工序指派一组合适的工人,在不超过每个工作站所能容纳的最大工人数量的前提下,使工人的工时利用率达到最大,从而减小装配线上的总工人数量与工人的空闲时间,进一步提高装配线的线效率,降低平滑指数。
2.2 数学建模
针对CMALBP问题的研究目的,本文在满足问题约束的前提下,建立以最小化工作站数量和工人数量为综合优化目标的数学模型,模型中涉及的符号定义如表1所示。
表1 符号含义
问题的模型如下:
(1)
(2)
∀i,k∈N,i≠k,(i,k)∈G;
(3)
ci+tk≤ck+B(1-oik),
∀i,k∈N,i≠k;
(4)
ti≤ci≤CT,∀i∈N;
(5)
(6)
∀(i,k)∈N,i≠k,∀l∈P;
(7)
∀(i,k)∈N,i≠k,∀l∈P;
(8)
(9)
eiyil=ekykl,∀i,k∈N,∀l∈P;
(10)
∀i,k∈N,i≠k,∀l∈P;
(11)
oik+oki≥yil+ykl-1,
∀i,k∈N,i≠k,∀l∈P;
(12)
oik+oki≤1,∀i,k∈N,i≠k;
(13)
qijl≥xij+yil-1,
∀i∈N,∀j∈St,∀l∈P;
(14)
∀i∈N,∀j∈St,∀l∈P;
(15)
(16)
zlj≥xij+yil-1,
∀i∈N,∀j∈St,∀l∈P。
(17)
式(1)中目标函数的第一项为最小化工作站数量,第二项为最小化工人数量,通过加权系数w1和w2将多目标问题转化为以最小化综合成本C为目标函数的单目标问题来求解。考虑到在实际装配线的生产过程中,增加一个工作站的成本远比增加一个工人的成本要大,因此,在建立目标函数时,需要更多地考虑工作站成本对目标函数的影响。基于以上分析,本文在求解CMALBP时,取工作站成本的权重系数w1=0.8,工人成本的权重系数w2=0.2。式(2)为任务分配约束,表示任意一道工序必须且只能分配到一个工作站上。式(3)和式(4)为工序的装配顺序约束和工人的流动约束,其中∀i,j∈N,i≠k,(i,k)∈G表示工序i和工序k为任意两道不同的工序,且工序i必须在工序k之前完成装配;当工序i和工序k分配给同一个工作站上的同一个工人时,xij=1,xkj=1,oik=1,此时式(3)和式(4)均等价于ci≤ck-tk,即工序k的开始时刻不能早于其前序工序i的结束时刻;当工序i和工序k分配给同一个工作站上的不同工人时,xij=1,xkj=1,oik=0,此时式(4)恒成立,式(3)等价于ci≤ck-tk;当工序i和工序k分配给不同的工作站时,工人不在工作站之间流动,oik=0,此时式(4)恒成立,仅当工序i的工作站索引小于工序k的工作站索引时,式(3)成立,即优先分配工序k的前序工序i。式(5)为节拍约束,表示工序i的结束时刻既不能早于工序的装配时间,也不能超过节拍时间。式(6)为多人协同装配的约束,表示工序i需要pi个工人同时装配。式(7)和式(8)为工序指派约束,表示所有指派给同一个工人的工序必须分配到同一个工作站上。式(9)为工人数量约束,表示一个工作站上的工人数量不能超过Pmax。式(10)为工人能力约束,表示分配给同一个工人的工序所需的工人类别必须相同。由于模型中涉及的决策变量较多,且决策变量之间存在一定的相关性,因此式(11)～式(17)对决策变量oik、qijl、zlj进行了逻辑上的一致性约束。其中式(11)～式(13)约束了oik的取值:当工序i和工序k分配给同一个工人时,yil=1,ykl=1,此时若工序i在工序k之前装配,则oik=1,oki=0;否则oki=1,oik=0;当工序i和工序k分配给不同工人时,oik=0且oki=0。式(14)～式(17)约束了qijl、zlj的取值:当工序i分配给工人l,且工序i分配给工作站j时,yil=1,xij=1,此时qijl=1且zlj=1;否则qijl=0且zlj=0。
3 改进的离散水波优化算法
多人共站装配线平衡问题(MALBP)是一个组合优化问题,具有离散性、多约束性、多目标性以及求解复杂等特点,常采用遗传算法、模拟退火算法、蚁群算法等启发式算法来求解。采用元启发式算法虽然能够获得较好的求解效果,但存在建模效率低、邻域结构设计复杂、收敛精度不高等问题。而水波优化算法是近些年提出的智能进化算法,具有算法框架简单、容易实现、搜索能力强等优点,且适用于求解实际生产调度中的大规模问题[15],因此,本文考虑采用改进的水波优化算法以解决CMALBP。
3.1 基本水波优化算法
水波算法是由ZHENG[14]提出的一种智能进化算法,主要针对连续优化问题进行求解,具有搜索能力强、流程简单且易于实现的优点。水波算法从浅水波模型获得灵感,将海床模拟为解空间,将海床上的水波模拟为一个解,海床深度反比于该解的适应度值。在初始化时,需要将每个个体(解)的高度设置为Hmax,波长设置为λ0。在寻优过程中,种群中的个体依次进行传播、折射和碎浪3种算子操作。
3.1.1 算法流程图
基本水波优化算法的流程图如图3所示。
图3 基本水波优化算法流程图
3.1.2 传播算子
传播算子通过对个体的每一维进行搜索,得到一个新的解,传播算子如式(18)所示。
x′(d)=x(d)+rand(-1,1)λL(d)。
(18)
其中:rand(-1,1)表示区间(-1,1)内的随机数,L(d)为解空间第d维的长度。在每一次迭代过程中,个体的波长λ按照式(19)迭代。
(19)
其中:α为衰减系数,通常取大于1的常数;f(x)为当前解的适应度值;fmax、fmin为当前所有个体适应度值的最大值和最小值,ε为一个接近0的正数。
3.1.3 碎浪算子
碎浪算子是对个体的某一维进行如式(20)所示的搜索。
x′(d)=x(d)+N(0,1)βL(d)。
(20)
其中:N(0,1)是满足均值为0,标准差为1的高斯分布的随机数;β为碎浪系数,β∈[0.01,0.2]。
碎浪过程中,随机选择个体x的k个维度,使用式(20)产生k个子代个体,若k个子代个体中有较个体x更优的个体,则从中选择最优的个体替换x,否则保留个体x。
3.1.4 折射算子
当个体的高度为0时,对个体进行折射算子操作,折射算子如下:
(21)
3.2 改进的离散水波优化算法
基本水波优化(WWO)算法主要由算法框架和算子操作组成,适用于求解连续函数优化问题,而复杂多人共站装配线平衡问题(CMALBP)是一个离散的组合优化问题,且约束条件较为复杂,因此,本文提出一种改进的离散水波优化(DWWO)算法,算法的流程与基本水波优化算法相同,但在算法性能方面做出了如下改善:
(1)对于CMALBP中的复杂约束,设计了基于拓扑排序的编码方案和一种启发式的解码方案;
(2)针对CMALBP的离散化特点,以基本水波优化算法的框架为基础,对3种算子进行离散化改造;
(3)在传播操作中,采用自适应的片段长度控制算子的搜索范围,增强算法的全局搜索性能;
(4)在折射操作中,引入扰动个体和路径重连的搜索策略,增加种群的多样性,使得算法在后期收敛时能够跳出局部最优。
3.2.1 基于拓扑排序的编码方案
本文基于图论中有向无环图的拓扑排序思想,采用考虑工序优先关系约束的编码方案,编码形式如图4所示,编码以工序为基本单位,个体中的每一位代表工序的编号,每道工序在个体中的位置必须在其所有紧前工序之后,采用该编码方案进行个体初始化的基本步骤为:
图4 工序优先关系图
步骤1在工序优先关系图中选择一个入度为0的工序节点i加入个体,其中入度为0的节点是指没有前驱节点的节点;
步骤2在工序优先关系图中删除工序节点i和所有以i为起点的边;
步骤3若工序优先关系图上所有的节点都被删除,则输出个体;否则转步骤1。
以如图4所示的工序优先关系图为例,采用上述基于拓扑排序的编码方案,得到一种可能的个体编码序列,如图5所示。
图5 可能的个体编码序列之一
3.2.2 启发式解码方案
解码是将个体编码序列转化为CMALBP平衡方案的过程,即将所有工序合理地分配到工作站上以及为所有工序指派合适的工人组。本文提出一种启发式解码方法,按照个体编码序列中工序出现的先后顺序考虑每一道工序的分配方案,从而确定每一道工序对应的工作站和工人组,此方法在不增加工人数量的情况下,尽可能地将工序分配到当前工作站上,当无法继续分配工序时,再新增工人,使得当前工作站上工人的时间利用率达到最大。工作站j上工人的时间利用率urj的定义如式(22)所示。工人的时间利用率越高,工作站上所需要的工人数量越少,对应的装配线平衡方案更优。
(22)
其中:Sj为所有分配到工作站j上的工序集合,ti为工序i的所需的装配时间,pi为工序i所需要的工人数量,CT为节拍时间,mj为被分配到工作站j上的工人数量。具体的解码过程如下:
步骤1初始化参数。设当前工作站的编号j=0,当前工作站上的工人数量m=0。
步骤2判断终止条件。若仍有工序没有确定分配信息,使得j自增1,即开辟新的工作站,使得工作站上的工人数量m=0;否则输出所有工序的分配信息,并结束解码过程。
步骤3确定预分配工序。按照工序在个体编码序列中出现的顺序确定需要预分配的工序i。
步骤4为预分配工序指派工人。预分配工序i到工作站j上,即在工作站j上已有的工人中指派一组工人装配工序i。若预分配成功,计算此时工作站的时间利用率,转步骤3;否则转步骤5。
步骤5增加与工序所需工人类型相匹配的工人。若工作站j上的工人数量小于工作站所允许的最大工人数量,即m 步骤6确定预分配工序的分配信息。搜索工作站j上所有已经预分配的工序,找出一道工序k使得预分配完工序k时工作站j的时间利用率最高,确定所有在工序k之前完成预分配的工序(包含工序k)的分配信息,在工序k之后完成预分配的工序需要继续分配到后续工作站上;转步骤2。 在为工序分配工人时,若有多组工人都满足条件,则优先选择开始装配时间最早的一组工人。这种启发式解码方式可以使得每个工人的平均空闲时间最小,最终达到装配线负载均衡的目的。 3.2.3 自适应长度的传播算子 离散传播算子主要是进行邻域搜索,为保证搜索过程中不破坏个体的编码约束,引入多段交叉的思想设计传播算子,算子的操作过程为:随机选择当前个体X1的一个片段,并使用轮盘赌[19]的方法选择种群中的另外一个个体X2,将X1中所选片段的所有工序按照它们在X2中出现的相对顺序重新排列,用重新排列后的新片段代替X1中的原片段,从而得到一个新个体X′。在如图6所示的传播算子示例中,选择X1的一个片段[1,3,4,6],按照它们在X2中出现的相对顺序重新排列得到新片段[1,4,3,6],将新片段代替X1中的原片段,得到新个体X′。 图6 传播算子示意图 由于复杂多人共站装配线平衡问题(CMALBP)是离散优化问题,因此,对传播算子进行重新设计,如式(23)所示: (23) 式(23)中,两个个体进行多段交叉操作的片段长度由参数PL自适应调整,从而控制传播算子的搜索范围,PL的计算公式如式(24)所示: PL=2+randInt(λ·(L-2))。 (24) 其中,为了保证搜索的有效性,设定片段长度PL的最小值为2,randInt(x)为不超过x的随机正整数,L为个体的长度,且L>2。 3.2.4 离散碎浪算子 离散碎浪算子主要是对个体进行小范围的邻域搜索,为了保证搜索过程中不破坏个体的编码约束,引入拓扑排序方法来控制搜索方向,算子的操作过程为:随机选择当前个体中的一个片段,考虑片段内工序的优先关系约束,采用拓扑排序的方法产生一个新的片段,并将得到的新片段代替原片段。如图7所示的碎浪算子示例中,选择个体X0的一个片段[1,3,4],然后根据该片段中所包含的工序的优先关系图,随机选取入度为0的工序节点加入新片段,并将被选择的工序节点从优先关系图中删除,当所有工序选取完毕时,用最终产生的新片段[1,4,3]代替原片段得到个体Xb,优先关系图的变化过程如图8所示。 图7 碎浪算子示意图 图8 碎浪算子中工序优先关系图变化过程示意图 与传播算子相同,在基本水波算法中,碎浪算子的搜索范围取决于碎浪系数β,因此,对碎浪算子进行离散化改造,算子搜索的片段长度BL如式(25)所示: BL=2+randInt(β·(L-2))。 (25) 其中:BL为碎浪算子的搜索长度,β为碎浪系数,其他参数与式(24)相同。 3.2.5 引入扰动个体的折射算子 在基本水波优化算法中,折射算子操作容易导致种群过早收敛,因此,在执行离散折射算子时,以pn的概率引入一个扰动个体X′,扰动个体X′通过拓扑排序的方式产生,同时,引入路径重连[20]的思想,以1-pn的概率搜索初始个体X和最优个体X*之间的解空间,从而增加种群的多样性,进一步提高算法的全局搜索性能。 初始个体X和最优个体X*之间的搜索过程为:以当前种群中的最优个体X*为导向,按照一组随机生成的序列依次交换初始个体X中两道工序的位置,直到初始个体X与最优个体X*完全相同;在交换过程中会产生与初始个体X和最优个体X*都不相同的中间个体,从所有中间个体中选择适应度值最大的个体作为最终输出的个体X′。 在搜索中间个体的过程中,可能会破坏个体编码序列的优先关系约束,导致算法的寻优效率下降,因此,采用拓扑排序的方法对中间个体进行修正。在修正过程中,若有多个工序节点入度为0,则优先选择最先出现的工序节点。 如图9所示的离散折射算子示例中,对初始个体X0使用离散折射算子,通过3次工序位置交换后得到最优个体X*,同时产生了两个中间个体X1、X2,由于X2中片段[3,1]不符合个体编码序列的优先关系约束,因此采用拓扑排序方法将其修正为[1,3,2,4,5,6,7],最后,从X1和X2中选择适应度值最大的个体作为最终输出的个体X′。 图9 离散折射算子示意图 4.1.1 测试用例 本文所研究的复杂多人共站装配线平衡问题(CMALBP)是以实际动车装配线为背景提炼出来的,由于动车是大型装配产品,在实际调度过程中,装配工序的数量多、复杂程度不同,装配任务需要由不同数量和类型的工人协作完成。与多人共站装配线平衡问题(MALBP)相比,CMALBP更注重于研究具有多工种的并行装配任务优化,因此,针对该类装配线平衡问题的优化,在平衡工作站负载以减少工作站数量和提高生产效率的同时,需考虑指派不同规模和类型的工人组完成装配任务,尽可能地减少工人数量并提高工人的工作效率,从而降低企业的劳动力成本。 由于当前难以找到CMALBP的标准测试用例,为了验证算法的有效性,结合动车装配线的实际生产情况,生成了考虑以下3个因素的测试用例: (1)装配工序所需的工人类别不同; (2)装配工序的复杂程度不同,不同工序由数量不同的工人协作完成; (3)实际装配空间有限,工作站内所能容纳的工人数量存在上限值。 同时,为了说明算法对不同规模的CMALBP的求解能力,设定不同工序数量的测试用例来说明实际装配线中不同规模的问题,并将每一组测试用例的节拍时间分别设置为16、24、32、40,CMALBP测试用例的基本信息如表2所示。 表2 CMALBP测试用例信息 4.1.2 参数设置实验 本文所提出的改进离散水波优化(DWWO)算法有几个重要的参数,分别为:波长衰减系数α、碎浪系数β、初始波长λ0、最大高度Hmax以及折射算子中的扰动概率pn,取α=1.001、β=0.2。DWWO算法的搜索效率主要取决于参数λ0、Hmax和pn的取值,如果搜索的精度不够高,将会导致当前解偏离全局最优解的方向,进而影响整个算法的寻优性能,因此设计实验确定最优的参数组合。 实验采用不同参数组合下的DWWO算法分别求解如表2所示的测试用例,算法在每个测试用例上独立运行20次,选择使算法性能最优的参数组合作为后续实验的参数。在实验中,λ0分别设置为0.5、0.75、1.0,Hmax分别设置为4、6、8、10,pn分别设置为0.0、0.25、0.5、0.75、1.0,参数组合共有3×4×5=60种可能的情况,记录算法在不同参数组合下的实验结果,并使用平均相对偏移量(APRD)来评估算法的性能,APRDt表示算法在测试用例t上的平均相对偏移量,APRDt越小,则说明算法在测试用例t上的结果越好。APRDt的计算公式如式(26)所示: (26) 其中:t为测试用例的编号,Ctr为算法在测试用例t上第r次运行所得结果,R为算法的独立运行次数,Ctmin为算法在第t个测试用例上的不同参数组合下所能找到的最优值。 由于APRDt只能用来评估采用某种参数组合的算法求解测试用例t的结果优劣,而无法判断该参数组合对算法整体性能的影响,计算总偏移量(SRD)来评价每种参数组合的优劣。SRD的计算公式如式(27)所示: (27) 其中n为测试用例总数,其他符号含义与式(26)相同。由相对偏移量和总偏移量的关系可知,SRD越小,算法的整体性能越好。 算法在每种参数组合下的SRD的计算结果如图10所示,在60种参数组合所得的实验结果中,采用第22种参数组合的算法的总偏移量之和最小,此时的参数组合为λ0=1、Hmax=6、pn=0.25,即在该参数组合下,算法的整体性能最优。 图10 60种参数组合作用下的SRD 为了进一步分析3个参数单独作用时对算法整体性能的影响,对算法在不同参数组合下的总偏移量进行统计分析,如图11所示。图11a表示在λ0取值分别为0.5、0.75、1时,对应的Hmax和pn的20种可能组合下的总偏移量之和;图11b表示Hmax取值分别为4、6、8、10时,对应的λ0和pn的15种可能组合下的总偏移量之和;图11c表示pn取值分别为0、0.25、0.5、0.75、1时,对应的λ0和Hmax的12种可能组合下的总偏移量之和。可以看出,在λ0、Hmax、pn单独作用下所对应的总偏移量之和最小时的取值分别为1、6、0.25,与3个参数的最优组合取值一样,也就是说,当每个参数取值最优时,算法的整体性能最好。因此,选择λ0=1,Hmax=6,pn=0.25,此时算法效果最好。 图11 3个参数单独作用时的SRD 4.2.1MALBP标准测试用例实验 为了测试算法的精度以及算法对不同规模问题的求解能力,分别从文献[6]中不同规模的MALBP标准测试用例中选择了工序数量N≤30的11个小规模测试用例、工序数量30 表3 算法在MALBP标准测试用例上的实验结果 由表3可得,在29个不同规模大小的标准测试用例中,DWWO算法可在27个用例中(占93.1%)获得最优的平均值,较ACO算法(17个用例,占58.6%)和EMBO算法(10个用例,占34.5%)有更好的整体寻优性能。虽然文献[21]没有提供SA算法对应的平均值和标准差数据,但DWWO算法较SA算法在更多的测试用例上获得更好的最优值;而DWWO算法在未求得最优值的两个测试用例上,其工作站数量较ACO算法和SA算法大大减少,即所得平衡方案对应的装配线线长更短,这说明DWWO算法在优化工作站数量上性能更优。同时,4种算法对于小、中规模测试用例的求解效果没有明显差异,但在大规模测试用例上,DWWO算法均求得了最优的平均值和最好值,这说明DWWO算法对于大规模问题的求解更有优势。 为了进一步分析算法对于MALBP中工人数量的优化性能,引入文献[21]中使用的线效率(LE)和平滑指数(SI)两个装配线平衡性度量指标对求解方案的优劣进行评估,LE和SI的计算公式分别如式(28)和式(29)所示: (28) (29) 其中:ti为第i道工序的装配时间,N为装配线的总工序数量,NM为优化后的总工人数量,CT为节拍时间,Tl为第l位工人的总装配时间。 由式(28)可得,对于同一个测试用例,工序的总装配时间和工作站的节拍时间相同,则线效率与优化所得调度方案的总工人数量成反比,即总工人数量越少,线效率的值就越大,装配线的平衡性越好。由式(29)可得,对于同一个测试用例,工作站的节拍时间相同,每个工人的总装配时间与节拍时间的差即为该工人的空闲时间,则平滑指数与优化所得调度方案中工人的空闲时间以及总工人数量有关,当总工人数量一样时,工人的空闲时间越小,平滑指数的值就越小,装配线上工人之间的负载差异越小。 由于文献[6]没有提供ACO算法优化所得平衡方案对应的LE和SI,因此只计算表3中DWWO算法和EMBO算法在5组测试用例的不同节拍时间下所得的最优平衡方案对应的平均线效率和平滑指数,记为LE(AVG)和SI(AVG),并与文献[21]中SA算法所得数据进行对比,用粗体标明LE(AVG)和SI(AVG)最优的结果,如表4所示。 由表4可知,SA算法对应的平均线效率性能最优,DWWO算法对应的平均平滑指数性能最优,说明SA算法所得平衡方案有利于降低装配线上的劳动力成本,而DWWO算法所得平衡方案有利于降低工人之间的负载差异,提高工人的利用率。 4.2.2 CMALBP测试用例实验 表5 算法在CMALBP测试用例上的实验结果 由表5可得,在20个测试用例中,从优化所得的平均值(AVG)来看,DWWO算法可得到15个用例(占75%)的最好结果,SA算法可得到4个用例(占20%)的最好结果,EMBO算法可得到9个用例(占45%)的最好结果;就最优值(BEST)而言,DWWO算法在18个用例(占90%)上获得了最好结果,SA算法和EMBO算法分别在9个用例(占45%)上获得了最好结果;这说明DWWO算法较另外两种算法所得的装配线平衡方案更优。由于DWWO算法在测试用例5(工序数>100)的大规模测试用例上均取得了最好的平均值和最优值,较其他算法优势更加明显,再次证明了DWWO算法更适用于求解大规模问题。 为了分析算法在优化工人数量和工作站数量上的性能,计算3种算法在20个测试用例上求得的工人数量平均相对偏移量(APRD-W)和工作站数量平均相对偏移量(APRD-S)。APRD-W和APRD-S的计算方法与式(26)相同,但是目标函数值分别替换为最小工人数量和最小工作站数量。3种算法在20个测试用例上的APRD-W和APRD-S可以用箱线图表示,如图12和图13所示。 图12 3种算法对应的APRD-W箱线图 图13 3种算法对应的APRD-S箱线图 由图12可知,DWWO算法的APRD-W整体较另外两种算法都小,说明DWWO算法在优化工人数量方面较另外两种算法性能更好。由图13可知,DWWO算法在APRD-S上其整体性能优于SA算法,而与EMBO算法相比,其所得中位数和最大值更大,但其在上四分位数值较EMBO算法更小,而且经过计算得到的平均值也较EMBO算法略小,说明DWWO算法与EMBO算法在APRD-S上性能接近。 同样地,采用线效率(LE)和平滑指数(SI)来评估不同算法所得CMALBP平衡方案的优劣。与MALBP不同的是,CMALBP中一道工序需要由多个工人协同装配,而工序的实际总装配时间等于工序的装配时间乘以该道工序所需的工人数量,此时LE的计算公式(28)将不再适用于CMALBP,因此,重新设计LE的计算公式,如式(30)所示,而SI的计算公式中不涉及工序的装配时间,可直接使用MALBP中的式(29)计算。 (30) 其中pi为第i道工序所需的工人数量,其他参数与式(28)相同。 分别计算3种算法在表5中5组CMALBP测试用例的不同节拍时间下所得的最优平衡方案对应的LE(AVG)和SI(AVG),并用粗体标明最优值,结果如表6所示。 表6 算法在CMALBP测试用例上的平衡性度量指标的计算结果 由表6可知,DWWO算法对应的平均线效率和平滑指数的性能均为最优,说明DWWO算法相对于SA算法和EMBO算法来说,更适用于求解CMALBP。 4.2.3 动车装配线平衡优化 动车总装是动车生产过程中的重要一环,由于动车体积庞大、结构复杂、工序繁琐,其生产线较长,且总装过程需要大量的工人参与,因此,合理地分配工序以及调度工人是维持动车生产平衡的关键。本文对实际生产中的动车装配线进行平衡优化,从而验证所构建的复杂多人共站装配线平衡问题模型的有效性。 装配线上一共有249道工序,3种类型的工人,每种类型的工人数量不限,每天的工作时长不能超过8 h。工序的装配时间、所需的工人类型及数量如表7所示,工序之间的优先约束关系如表8所示。另外,由于装配线上的空间有限,每个工作站内可容纳的最大工人数量为25,根据最长工序路径计算所得理论最优工作站数量为18个。 表7 装配工序信息 表8 工序优先约束关系 以最小化工作站数量和工人数量为目标,建立该实例的CMALBP数学模型,并采用DWWO算法进行求解,最终得到装配线上的工序分配方案以及工人指派方案。由于文章篇幅有限,图14仅给出工作站1的工人装配甘特图,其中,横坐标为工人的工作时长,纵坐标为工作站编号-工人编号,绿色、蓝色、黄色分别表示类型1、类型2、类型3的工人,甘特图中标明的数字为工序的编号。最终优化所得的工人数量为454,工作站数量为19个,根据式(29)和式(30)分别计算得到装配线的平滑指数(SI)为0.149、线效率(LE)为0.945,与现有的装配线方案相比有较好的提高。 图14 工作站1的工人装配甘特图 本文提出一种复杂多人共站的装配线平衡问题(CMALBP),该问题考虑了多人协同装配一道工序和工人技能差异等特殊情况,将装配线所需要的工作站数量和工人数量的加权和作为目标函数,优化装配线平衡方案使得总成本最小。针对该组合优化问题,提出一种离散水波优化(DWWO)算法求解,设计了考虑工序优先关系约束的编码方案和启发式的解码方案,并针对编码方案的特点设计了3种离散算子。同时,在MALBP标准测试用例上,将DWWO与ACO、SA、EMBO算法的实验结果进行对比,通过计算线效率和平滑指数两个平衡性度量指标,验证了DWWO算法的求解精度。最后,结合动车装配线的实际生产情况,分别采用DWWO、SA和EMBO算法求解CMALBP测试用例,验证了DWWO算法的适用性以及在求解大规模问题上的优越性,并通过实例求解验证了所建模型的有效性。后续可以针对实际装配过程中的动态因素进行更深入的研究,以提高模型的适用范围和DWWO算法的鲁棒性。
4 实验分析
4.1 算法参数设置
4.2 测试用例分析
5 结束语
