考虑拆卸序列的机器人拆卸线平衡优化*

赖冬梅,唐秋华

(武汉科技大学a.冶金装备及其控制教育部重点实验室;b.机械传动与制造工程湖北省重点实验室,武汉 430081)

0 引言

科技的突飞猛进给人类带来了便捷的生活,同时也对自然环境造成了破坏,人类面临着资源短缺和环境污染的巨大挑战。我国经济发展已从高速发展转向高质量发展,传统制造方式已不能满足高质量发展的要求,再制造和绿色制造是实现人与自然协同发展的重要方式。再制造拆卸服务作为再制造服务的重要组成部分,是废旧品再制造资源最大化利用的重要前提,是实现产品多生命周期的必要环节[1]。

目前针对废旧品拆卸规划的研究集中在拆卸序列规划和拆卸线平衡两个方面。拆卸线平衡问题的核心是为拆卸工作站分配拆卸任务,从而使拆卸线系统高效运行。自拆卸线平衡模型[2]建立后,很多学者就拆卸线平衡问题的建模和解决方法展开了丰富的研究,但常规研究专注于不违反废旧品优先关系,缺乏对拆卸序列的考虑。但在实际拆卸过程中,拆卸任务之间可能存在交互,一个零件可能会影响另一零件的基本拆卸时间,即一个零件会阻碍另一零件的拆卸从而需要附加操作,导致产生相应的拆卸作业时间增量,这就是考虑拆卸序列的拆卸线平衡问题。拆卸作业时间增量是拆卸总时间的一部分,它会因为拆卸任务顺序的不同而变化,导致拆卸总时间变化。在拆卸任务分配后,各工作站的拆卸总时间也会因任务的组合不同而变化,从而影响工作站的负载均衡。

随着机器人应用的普及,废旧品拆卸不再局限于手工作业,机器人拆卸在缩短拆卸周期、降低拆卸成本等方面更有优势,机器人拆卸线平衡问题引起了大量学者关注。由于机器人的特殊性,在拆卸过程中的刀具切换时间、方向调整时间和移动时间都不该被忽略。

为此,研究考虑拆卸序列的机器人拆卸线平衡问题是必要的。刘佳等[3]研究了具有多目标且与拆卸顺序相关的拆卸线平衡问题。EMRAH等[4]就拆卸线平衡问题提出混合整数线性规划模型及其扩展模型并进行了排序决策。CHEN等[5]不仅考虑废旧品的优先关系,还考虑拆卸任务交互导致的作业时间增量和机器人拆卸,提出序列相关的机器人拆卸线平衡问题并求解。LIU等[6]同时考虑机器人拆卸序列规划和机器人拆卸线平衡问题的优化目标,提出改进离散蜜蜂算法用于求解所提问题,该算法尽管能得到较优解,但算法稳定性还有待提高,数学模型还有待补充完整。同时,考虑拆卸方向的研究还较少。

针对目前研究的不足之处,在机器人拆卸线平衡问题中考虑拆卸任务之间的序列相关关系,为减少方向调整时间进行方向选择,构建考虑拆卸序列并带有多目标的机器人拆卸线平衡问题数学模型,建立耦合赋权方法并提出一种改进离散粒子群算法,以提高寻找较优解的效率和质量。

1 问题陈述

机器人拆卸线平衡问题的目的在于给机器人拆卸生产线寻找最优拆卸方案,使得整条线上的多个机器人拆卸工作站负载均衡,减少空闲时间,实现基于并行或串行拆卸线的废旧品大量拆卸,从而提高拆卸效率,降低拆卸成本。学者评价拆卸方案质量时采用的指标一般包括节拍时间、平滑指数、各工作站空闲时间、转变方向次数、需求指数[7]等。

在上述基础上,同时考虑拆卸顺序和多个工作站的拆卸任务分配,得到满足拆卸先后约束和序列相关关系的可行拆卸序列,进而将任务均衡地分配在各并行工作站上,使拆卸生产线能按一定顺序连续高效地大量拆卸废旧品,其中拆卸线中每个工作站内的拆卸任务执行顺序都符合可行拆卸序列的顺序。值得注意的是,这里的拆卸总时间不再是简单的基本拆卸时间之和,工作站中拆卸任务之间还存在额外的拆卸时间。基于此建立以工作站数量最小、平滑指数最小和所有工作站中最大作业时间最小为目标的优化模型,同时在排序决策中加入方向选择,从而减少方向调整时间。

简而言之,本文研究的拆卸线平衡问题是考虑拆卸序列和机器人拆卸场景的并行工作站直线型单产品拆卸线平衡问题。

2 数学模型构建

在拆卸过程中,拆卸任务是不可再分的最小自然单位,一个拆卸任务仅能在一个工作站上进行,且每个拆卸任务之间相互独立[8]。为便于研究,提出以下假设:①每个拆卸工作站仅有一个拆卸机器人;②构成废旧品的所有零件均须完全拆卸;③每个零件只能由一个机器人工作站进行拆卸;④每个工作站总拆卸时间小等于拆卸线节拍;⑤每个零件基本拆卸时间固定不变,不考虑准备时间及切换时间等的影响;⑥拆卸过程中机器人末端执行器沿着预定的路径进行拆卸;⑦废旧品零件除了受拆卸顺序优先关系约束以外,没有其他的约束限制[8]。

2.1 符号定义

表1 符号定义

2.2 优化模型构建

根据上述问题描述可建立数学模型如下:

Minφ=w1F1+w2F2+w3F3

(1)

f1=|S|

(2)

(3)

(4)

Fi=(fi-min(fi))/(max(fi)-min(fi))

(5)

s.t. ∑tXp,t=1,∀p

(6)

∑pXp,t=1,∀t

(7)

∑tt·Xp,t≤∑tt·Xj,t,∀p,j,p∈Hj

(8)

∑pXp,t+1≤∑pXp,t,∀t<|P|

(9)

∑s∑cYp,s,c=1,∀p

(10)

∑pYp,s,c+1≤∑pYp,s,c,∀s,c<|C|

(11)

∑pYp,s,c≤1,∀s,c

(12)

∑s∑c(|S|·s+c)·Yp,s,c-∑s∑c(|S|·s+c)·
Yj,s,c≤M·(2-Xp,t-Xj,t+1),∀p,j,t,t<|P|

(13)

Lp,s≥btp-M·(1-Yp,s,1),∀p,s

(14)

Lp,s≤btp+M·(1-Yp,s,1),∀p,s

(15)

Lj,s≥btj+ttp,j+dtp,j+mtp,j-
M·(2-Yp,s,c-Yj,s,c+1),∀p,j,s,c<|C|

(16)

Lj,s≤btj+ttp,j+dtp,j+mtp,j-
M·(2-Yp,s,c-Yj,s,c+1),∀p,j,s,c<|C|

(17)

(18)

(19)

(20)

(21)

∑d∈DpZp,d=1,∀p

(22)

dtp,j≥∑d∈Dp∑d′∈Djatdd′·Zp,d·Zj,d′-
M·(2-Yp,s,c-Yj,s,c+1),∀p,j,s,c<|C|

(23)

dtp,j≤∑d∈Dp∑d′∈Djatdd′·Zp,d·Zj,d′+
M·(2-Yp,s,c-Yj,s,c+1),∀p,j,s,c<|C|

(24)

式(2)～式(4)表示优化目标,工作站数量最少即拆卸线成本最低,最小化平滑指数有利于工作站负载均衡。在满足节拍的前提下最小化所有工作站中的最大作业时间,有利于减少闲置时间。为更好地构建目标函数,用式(5)对目标进行归一化处理,消除它们的量纲从而变成无量纲表达式,再为各目标赋予权重得到目标函数式(1)。

拆卸序列约束:式(6)～式(7)表示每个零件都必须被拆卸且每次只拆一个零件;式(8)表示零件p先于零件j拆卸;式(9)表示紧前零件拆卸后才能进行紧后零件的拆卸。

任务分配约束:式(10)表示每个零件只能分配到一个工作站上;式(11)表示在每个工作站的拆卸序列中,必须先分前面的位置再分后面的位置;式(12)表示每个工作站中的每个零件最多进行一次拆卸;式(13)表示零件p先于零件j被分配在工作站s上。

拆卸时长约束:式(14)～式(15)表示若p是工作站s上第一个被拆卸的零件,实际拆卸时长等于基本拆卸时长;式(16)～式(17)表示若j是工作站s上位于中间被拆卸的零件,实际拆卸时长等于基本拆卸时长加上其他操作时间。

拆卸节拍约束:式(18)表示任给定工作站的总作业时间不得超过节拍时间。

拆卸时序约束:式(19)表示每个零件的拆卸开始时间和结束时间的关系;式(20)表示当零件p和j存在优先干涉关系时,零件p的拆卸结束时间在零件j的拆卸开始时间之前;式(21)表示在拆卸完前一零件后,完成其他操作后才能继续进行下一零件的拆卸。

拆卸方向约束:式(22)表示零件p可从d方向拆卸;式(23)～式(24)表示先后拆卸零件p和j所需的方向调整时间。

3 改进离散粒子群算法

粒子群算法(particle swarm optimization,PSO)是一种模拟鸟类觅食飞行中基本规律的进化算法[9]。标准的粒子群算法一般用来求解连续优化问题,很少用于求解离散优化问题。为更好地解决拆卸线平衡这种复杂的、离散的组合优化问题。采用能够解决上述问题的离散粒子群算法[10],并融合遗传算法中交叉与变异算子,不仅结合了粒子群算法和遗传算法解决离散NP问题时的优势,还增强了全局搜索能力,避免陷入局部最优。同时针对拆卸顺序有约束的特性还设计了两个有效的改进算子,即位移算子和变向算子,增加算法的寻优能力。

3.1 编码及解码

采用两段式编码,包括拆卸序列段和拆卸方向段,其中拆卸序列用来表达拆卸任务的顺序,且两段编码长度均为|P|(|P|指待拆卸废旧品的零件总数)。第一行为拆卸序列段,表示废旧品零件的可行拆卸序列,第二行为拆卸方向段,表示所有零件的拆卸方向,包括X+,X-,Y+,Y-,Z+,Z-。若废旧品零件数为6个,编码格式为2×6,如图1的编码部分:{1,6,4,5,3,2;1,4,3,2,5,6}表示依次拆卸零件1/6/4/5/3/2,它们的拆卸方向分别为X+/Y-/Y+/X-/Z+/Z-。

图1 拆卸编码及解码

基于上述编码,解码思路为:

(1)为表达废旧品各零件间拆卸的优先关系和阻碍关系,需要建立改进空间干涉矩阵[11],并进行干涉矩阵分析[12],产生初始可行拆卸序列和可行拆卸方向。拆卸一个废旧品可有多个可行的拆卸序列,一个可行的拆卸序列也可能有多个可行的拆卸方向。

(2)采用机器人工作站分配法[12]将零件分配到相应工作站上,从第一个被拆卸的零件开始,比较其拆卸总时间与节拍时间的大小,若此零件与其所在工作站的所有零件的拆卸总时间大于节拍时间,则将该零件分配到下一个工作站。拆卸总时间为基本拆卸时间、刀具切换时间、方向调整时间与移动时间的总和,其中方向调整为0°、90°和180°时的方向调整时间分别为1、2和3。

(3)直至所有零件都分配到工作站上即完成拆卸任务的分配,最后输出工作站的数量和拆卸任务的分配情况,如图1的解码部分。

3.2 粒子速度和位置更新

标准粒子群算法中的速度和位置更新公式不再适用于组合优化问题,文献[13]在粒子群算法中引入交换子和交换序的概念,基于此重新定义原有速度和位置更新公式为:

(25)

(26)

式中:“⊕”表示速度之间的加法,两个交换序列合并后形成一个新的交换序列;“-”为位置之间的减法,即由多个交换序列组成的集合;“+”为位置和速度之间的加法,即粒子根据速度大小进行位置的更新从而得到一个新的拆卸序列;α,β为[0,1]的随机数,α(pij-xij)和β(pgj-xij)分别表示基本交换序列(pij-xij)和(pgj-xij)中的所有交换子分别以概率α和β保留,概率值越大则保留的交换子就越多。

3.3 改进算子设计

为避免算法陷入局部最优困境,融入交叉、变异算子,增设位移算子,增加种群的多样性并尽可能保留有益序列组合。同时,为有效减少拆卸总时间,就最大作业时间的机器人工作站中的任务设计变向算子,达到增强算法寻优能力目的。

交叉算子采取遗传算法中的两点交叉方式,即在个体编码串中随机设置两个交叉点,然后根据交叉概率Pc=0.7进行交叉点之间基因片段的交换,从而形成新的个体。

变异算子选用遗传算法中传统的基本位变异方法,对粒子的编码以一定的变异概率Pm=0.5随机指定拆卸序列中某一位置的值并做变异运算。

位移算子与常见的插入算子类似,不同点在于任意截取的是基因片段。任意截取随机长度的基因片段,在满足干涉约束的前提下随机选择新的插入点将基因片段插入,从而形成新的拆卸序列。

总作业时间最长的机器人工作站往往是影响拆卸总时间长短的关键,考虑设计变向算子,减少拆卸总时间。以图1所示的包含6个零件的废旧品拆卸为例,工作站2的总作业时间最长,对分配至工作站2的拆卸任务“4、5”随机选择一个进行拆卸方向调整。

3.4 算法流程

改进离散粒子群算法(improved discrete PSO,IDPSO)的伪代码如表2所示。

表2 IDPSO伪代码

4 实验及案例分析

为便于分析与评价所提IDPSO算法性能,与文献[6]中的改进离散蜂群算法(IDBA)、遗传算法(GA)以及离散粒子群算法(DPSO)设计了对比实验。上述算法均用MATLAB语言编写,并在搭载AMD Ryzen 5 4600 U with Radeon Graphics 2.10 GHz处理器和16.0 GB机带RAM的计算机上MATLAB R2019b平台上运行。表3为案例的部分信息。

表3 12个案例的部分信息

4.1 目标权重确定及算法评价方法

为量化3个目标的权重系数,同时采用网络分析法(ANP)及熵权法。网络分析法需要决策者对目标的重要性进行两两比较,实质上是一种主观赋权法,因此考虑在其基础上引入熵权概念,综合考虑主观性和客观性。

ANP法和层次分析法 (AHP)在大致步骤上是相同的,它们的基本思想都是逐层归纳、先分后总地解决复杂问题[14-15],不同的是ANP法还需在判断矩阵被接受后,建立加权超矩阵并取幂计算直到矩阵收敛,得到极限超矩阵,最终得到权重Vj(j=1,2,3)。

熵权法是一种客观赋权方法,它利用信息熵理论,根据各目标的变异程度计算其熵权,熵权大小本质上由目标间的差异大小所决定,通过熵权修正各目标的权重,从而对专家打分进行客观赋权[16],根据信息熵,各项目标的权重Hj可以表示为式(27):

(27)

式中:n表示目标数量,即n=1,2,3。

Vj和Hj具有差异性,其各自对建立的评价体系又具有不同的影响,考虑将两者耦合起来[16-18],形成修正赋权组合式(28):

(28)

Wj兼顾了主观和客观因素,结合了ANP和熵权法两种方法的优点,使得目标函数里各目标的权重更加准确合理。

利用相对百分比偏差(relative percentage deviation,RPD)来评价算法对比实验的结果,RPD值越小表示算法的性能越好,相对百分偏差由式(29)表示:

(29)

式中:φsome表示某个案例在给定算法下在一次运行中解的适应度值,φbest表示某个案例在所有算法下多次求解的最好解的适应度值。

最小相对百分偏差值(MinRPD)和平均相对百分偏差值(AvgRPD)的计算公式由式(30)和式(31)表示:

(30)

(31)

式中:φmin表示某个案例在给定情形下运行20次中求解的最小适应度值,φavg表示某个案例在给定情形下运行20次中求解的平均适应度值,其中,若算法得到的MinRPD和AvgRPD越小,则表示算法的性能越好。

4.2 改进算子性能分析

为证明所提算子改进策略有效,设计对比实验依次进行交叉、变异、位移、变向算子性能分析,包括离散粒子群算法(DPSO)、仅带交叉算子的离散粒子群算法(DPSO-C)、仅带变异算子的离散粒子群算法(DPSO-M)、仅带位移算子的离散粒子群算法(DPSO-D)、仅带变向算子的离散粒子群算法(DPSO-T)与所提的带有4种算子的改进离散粒子群算法(IDPSO)。实验运行时间相同并设置为N×N×10 s,N表示各案例的拆卸任务总数,12个案例在上述6种情形下各运行20次得到的结果如图2所示。

(a) MinRPD (b) AvgRPD

从图2a和图2b可知,未改进的DPSO算法在实验运行中求得的MinRPD值和AvgRPD值普遍偏大,求解结果明显不够稳定,优越性不好。分别引入交叉、变异、位移、变向算子后所求得的MinRPD值和AvgRPD明显减小,但算法稳定性欠佳。但当同时引入各算子后,所求解的MinRPD值和AvgRPD值明显减小,算法稳定性和求解性能得到明显改善,证明所提算子改进策略有效。

4.3 算法性能分析

为更好地分析所提算法的综合性能,将所提算法IDPSO与DPSO、GA以及IDBA进行对比实验,在不同算法下将12个案例在相同时间内分别运行20次,得到的结果如图3所示。

(a) MinRPD (b) AvgRPD

从图3a和图3b可知,所提算法IDPSO求得的MinRPD值和AvgRPD值明显优于其他3种算法,说明相较于对比算法,IDPSO算法求解结果更好,算法求解稳定性更好。综合图2和图3分析可知,在相同的运行时间下,IDPSO算法的综合性能更优。

4.4 工程实例结果分析

为验证文章所提方法的有效性,在相同时间用不同算法在AHP、ANP、熵权法、AHP-熵权法和ANP-熵权法5种赋权法下运行20次输出最优拆卸方案,以案例2为例,结果如表4所示,“(9-14)”表示拆卸任务“9、14”在同一个工作站;“目标值/适应度值”一栏数值依次为3个目标值和适应度值。

表4 对比实验中案例2的拆卸结果展示

就算法而言,从表4可知,在相同的时间限制和实验条件下,无论采用哪种赋权法,IDPSO相比其他算法的求解质量更高,依次为IDBA和DPSO,而GA求解质量最差,尽管IDBA也能找到比较好的解,但稳定性较IDPSO较差。同时,IDPSO均能找到最优的工作站数量为8,求解到最短的工作站最大作业时间为15.333 3 s,说明给定案例2的节拍时间22 s可以优化至15.333 3 s,从而减小平滑指数和适应度值。

就赋权法而言,不同方法下优化目标的权重不同,就会影响解的质量。相同算法中,AHP法下的适应度值最小,这可能是目标一的值小而权重相对较大造成的,但该方法并未考虑目标之间的相关关系。相较于此,ANP法考虑到目标之间是相互影响的,更适用于所研究的组合优化问题,但由于该方法更主观,因此考虑将熵权法与之耦合,可以看到ANP-熵权法下的求解质量也是比较好的。总的来说,采用不同评估方法得到的评价结果是不一样的,在实际拆卸过程中,优化目标的选择应适合现场情况,才能达到解决实际拆卸难点的目的。经过完备的对比实验,验证了所提方法可以有效地求解所提优化问题。

5 结束语

为解决人工拆卸效率低下和拆卸成本高等问题,考虑用机器人进行废旧品拆卸,在当前研究的基础上,进一步考虑拆卸任务间的交互对拆卸顺序及拆卸作业时间的影响。根据问题特征构建多目标优化模型,提出ANP-熵权法建立耦合的定量评价模型,合理地量化目标权重,为下一步求解提供依据。同时设计一种改进离散粒子群算法来求解,该算法重构了粒子速度和位置更新公式,引入遗传算法中的交叉和变异算子弥补了粒子群算法全局寻优能力较差的缺点,并为契合问题本质还设计了位移和变向改进算子。为验证ANP-熵权法的合理性,设计对比实验与其他方法对比,实验表明该方法在综合考虑了主观性和客观性后得到了更为准确的权重,基于此求解的优化方案贴合实际拆卸生产,也能得到较好的应用。为验证所提算法的性能,将其与遗传算法、离散粒子群算法及改进离散蜂群算法对比,实验表明,所提算法相比其他3种算法可有效求解所提问题,具有明显的性能优势。综上所述,本文研究方法可行且具有应用价值,为优化拆卸线的生产提供了新的解决思路。