0 引言
科技的飞速发展推动着各类电子电器产品的更新换代,使得废旧产品日益增多.资源节约型制造模式成为可持续发展的主要方向之一,废旧产品的回收再利用成为绿色制造的重要组成部分.为减少废旧产品中有害物质对生态环境的影响,同时实现资源的循环再利用,及时、高效、合理的拆卸任务规划具有重要现实意义.与传统的拆卸方式相比,拆卸生产线(简称拆卸线)具有高效率、低成本、低污染和低能耗等特征[1].因此,拆卸线被视为大规模废旧产品的最佳拆卸方式,已广泛应用于大型拆卸企业.拆卸线平衡问题(disassembly line balancing problem,DLBP)致力于改善生产线效率,提高经济效益,自该问题被提出以来便受到国内外学者的广泛关注[2].
拆卸线的布局形式主要包括直线型、U型、双边、并行和混合型.相较于直线型布局[3],U型、双边[4]和并行拆卸线具有更高的拆卸效率.混流拆卸线可以在同一条生产线上拆卸多种结构相似的产品,能够提高拆卸线的利用率.针对拆卸过程中的不确定性,Zheng等[5]建立了随机任务处理时间的拆卸线平衡问题无分布模型,Bentaha等[6]将拆卸时间处理为服从正态分布的随机数,Kalayci等[7]和Zhang等[8]均采用三角模糊数来描述不确定性作业时间.这些文献均只是从拆卸时间上描述了拆卸过程的不确定性,并未分析拆卸过程中因不确定性因素导致的零部件的不可拆性.
在实际拆卸过程中,废旧产品可能存在零部件腐蚀、损坏等情况,部分零部件可能存在着形变严重、生锈等问题,而常规拆卸模式却无法解除这类约束.因此,对某些因锈蚀等情况导致的无法正常拆卸的零部件,可直接使用工具破坏其连接以解除强约束,这种拆卸方式被称为破坏性拆卸.如Song等[9]在拆卸序列规划中提出对部分连接件进行破坏性拆卸,能够快速获得目标拆卸体.
在现有拆卸线平衡研究文献中,尚未有对破坏性拆卸线平衡问题的公开报道,本文首次将破坏性拆卸模式引入到拆卸线中.需要指出的是,并非所有的零部件都适用于破坏性拆卸模式,有危害和再利用价值的零部件只能采用常规拆卸方式,而其他零部件可以采用常规拆卸方式或破坏性拆卸方式.因此,可以将常规拆卸方式和破坏性拆卸方式相结合,建立部分破坏性拆卸线平衡模型.
现有拆卸线平衡问题的优化目标主要是最小化工作站数和均衡工作站负荷. Pistolesi等[10]提出包括优化工作站数、拆卸利润、拆卸深度的多目标模型. Ren等[11]构建了以利润为导向的拆卸线模型,综合考虑工作站数、节拍、拆卸任务对利润的影响. Wang等[12]在此基础上分析了有危害的零件对拆卸利润的影响.节能减排政策要求在拆卸过程中降低能耗,因此拆卸能耗也是衡量拆卸线性能的主要指标之一[13].由上分析可知,评价拆卸线性能时需要综合考虑生产效率、生产成本、环境影响等多项指标.
拆卸线平衡问题因约束较复杂,其求解难度较大,学术界解决该问题的出发点是探索高效求解方法[14].多种启发式方法相继被应用于优化该问题,如Kazancoglu等[15]采用混合MCDM结构模糊层次分析法对各任务进行排序. Avikal等[16]运用层次分析法并结合多种启发式算法求解拆卸线平衡问题,实验表明所提方法能够得到较优解.为提高求解精度,Altekin等[17]通过数学规划法求解了以利润为导向的拆卸线平衡问题,但精确方法只适用于小规模问题.因拆卸线平衡问题是典型的NP完全问题[18],其求解时间随问题规模的增加而呈几何级增长.近年来,以群体智能优化算法为代表的元启发式方法因其良好的求解性能而被广泛应用于拆卸线平衡问题的求解,如遗传算法[19-20]、蚁群算法[21]、粒子群算法[22]、人工鱼群算法[23]等,在求解不同规模、不同类型的拆卸线平衡问题中均取得了较优的结果.因此,元启发式方法是优化拆卸线平衡问题的较优途径[24].
遗传模拟退火(genetic simulated annealing,GSA)算法结合了遗传算法的全局搜索能力和模拟退火算法的局部寻优能力,实现了两种算法的优势互补,在求解物流网络设计[25]和车间调度[26]等问题中具有较好的搜索能力.该算法能有效提高搜索精度,是求解组合优化问题的有效方法,因此可以采用遗传模拟退火算法优化拆卸线平衡问题.
鉴于现有研究的不足,本文考虑将部分破坏性拆卸模式引入到拆卸线中,建立以工作站数、作业负荷均衡、拆卸利润和能耗为优化目标的多目标部分破坏性拆卸线平衡模型,构造基于支配关系的遗传模拟退火算法对问题进行优化,并通过多个拆卸实例来验证模型和算法的性能.
1 部分破坏性拆卸线平衡问题 1.1 问题描述实际拆卸过程中,根据零部件质量和形态的不确定性,选择不同的拆卸模式进行拆卸,以提高整体拆卸收益和效率.零部件采用不同的拆卸模式时,其拆卸时间、成本、收益和能耗均不同.
拆卸后的零部件通常会采用不同形式进行回收再利用,如直接使用、再制造或粉碎回收原料等,这一系列操作均会产生一定的收益.参考文[27]对零部件价值的处理方式,用w表示各零件的价值率,即拆卸后的零件价值占实际价值的比率,w∈[0, 1].若零件的原始价值为p,则拆卸后的实际价值为p·w.
拆卸任务选择不同的拆卸模式将直接关系到拆卸利润的大小,因此需要尽可能选择利润高的拆卸模式.需从多个角度对部分破坏性拆卸线平衡问题进行数学描述.为便于描述该问题,参考文[19, 22, 28],本文给出如下已知条件:
1) 拆卸节拍已知;
2) 待拆卸产品的零部件齐全,数量充足;
3) 拆卸任务间的优先关系已知;
4) 各零部件的危害和需求已知;
5) 不同拆卸模式下各零部件的拆卸时间、原始价值、价值率、成本和能耗已知;
6) 产品拆卸过程为单一产品拆卸.
1.2 数学模型针对部分破坏性拆卸线平衡问题的特点,建立了该问题的数学模型,其目标函数和约束条件分别为:
(1) |
(2) |
(3) |
(4) |
(5) |
(6) |
(7) |
(8) |
(9) |
(10) |
(11) |
(12) |
目标函数中,式(1)表示最小化开启的工作站数.式(2)表示均衡工作站的负荷.式(3)表示最大化拆卸线利润.式(4)表示最小化拆卸线能耗.
约束条件中:式(5)表示每个任务都必须被拆卸;式(6)表示拆卸任务的进行必须满足优先关系约束;式(7)表示工作站数约束,开启的工作站数不小于理论工作站数,且不超过总拆卸任务数,即开启的每个工作站都必须至少分配一个任务;式(8)表示各工作站的实际拆卸时间应不超过节拍上限;式(9)表示实际生产节拍取各工作站作业时间的最大值;式(10)表示无危害或无需求的拆卸任务可选择常规或破坏性拆卸模式;式(11)和式(12)分别表示有危害的拆卸任务和有需求的拆卸任务只能选择常规拆卸模式.
2 Pareto遗传模拟退火算法遗传模拟退火算法结合了遗传算法的全局搜索能力和模拟退火算法的局部寻优能力,具有良好的求解性能.拆卸线平衡问题是典型的NP完全问题,随着任务规模增加其求解时间呈指数增长.部分破坏性拆卸线平衡问题相较于传统拆卸线平衡问题更加复杂,约束条件更多,其求解难度也更大,而遗传模拟退火算法具有较优的求解性能,故根据问题特征设计了多目标遗传模拟退火算法求解该问题.
2.1 初始可行序列生成生成初始可行序列即算法的编码过程,需要根据任务的优先约束来构造可行解.传统拆卸线平衡是直接将拆卸任务分配到工作站.部分破坏性拆卸线平衡问题更加复杂,需要先判断每个任务的拆卸模式,确定每个任务的拆卸时间后再将拆卸任务分配至各个工作站.因此,建立一种双向量X=[X1;X2]来表示编码序列,其中X1表示拆卸任务向量,X2表示拆卸任务对应的拆卸模式向量. X2中只含0和1两种变量,其中1表示拆卸任务采用常规拆卸模式,0表示拆卸任务采用破坏性拆卸模式.
基于优先关系矩阵进行编码可以确保编码结果均为可行解.以文[12]中10项拆卸任务为例阐述编码过程.拆卸任务优先关系图如图 1所示,圆圈表示各拆卸任务,圈内数字表示拆卸任务编号,箭头表示拆卸优先关系.如任务4和7是任务8的紧前任务,只有任务4和7都拆卸完成后才能拆卸任务8.每个任务对应一种拆卸模式,若任务满足约束条件(11)或(12),则只能采用常规拆卸模式.
根据拆卸优先关系图建立优先关系矩阵,如图 2所示.所构建的拆卸任务间的优先关系矩阵用Y表示,Y=[yik]N×N,其中N表示拆卸任务数,矩阵中的元素yik为0-1变量.若任务i是任务k的直接紧前任务,则yik=1,否则yik=0.
根据优先关系矩阵Y对任务进行编码,具体步骤如下:
1) 从矩阵Y中挑选列均为0的任务添加到候选任务集Z中,去除Z中已被分配的任务,更新Z.如根据图 2可得拆卸序列中第一个位置处的任务集Z={1,4,5,6,9,10}.
2) 随机挑选Z中任务i作为当前任务分配至位置n.
3) 将已分配的任务i的相关约束解除,更新优先关系矩阵Y,即∀k∈{1,2,…,N},令yik=0,yki=0.即此处若i=9,则任务9所在的行和列上的y9k=0,yk9=0.
4) 继续分配下一个位置n+1处的任务,重复步骤1) ~3),至所有任务被分配完.
通过上述步骤可产生一个任务向量X1=[6,9,10,1,4,5,7,8,3,2].每个任务对应一种拆卸模式,若此处拆卸任务9和5满足约束条件(11)或(12),则任务9和5对应的拆卸模式只能是常规拆卸,对应位置在向量X2中为1,其余拆卸任务即可选择常规拆卸模式或破坏性拆卸模式.此时拆卸任务向量X1相对应的拆卸模式向量X2 =[0,1,0,0,1,1,0,1,0,1],则最终编码序列X=[X1;X2]=[6,9,10,1,4,5,7,8,3,2;0,1,0,0,1,1,0,1,0,1],如图 3所示.
2.2 解码解码就是在满足节拍约束条件下,将编码序列中的任务分配至工作站中,并确定每个工作站中任务的顺序.在部分破坏性拆卸线平衡问题中,不同的拆卸模式使得任务的拆卸时间不同,从而影响任务的分配.具体的解码流程如图 4所示.图中i表示任务编号,X2(i)表示任务i对应于编码向量X2中的值,m表示工作站编号,Sm表示已分配到工作站m的任务集.
2.3 多目标处理方法在多目标问题中是通过解之间的支配关系来确定解的优劣,对于任意的两个可行解X1、X2,若X1和X2满足下式:
(13) |
则称X1 Pareto占优于X2,或X1支配X2,记为X1≺X2. X1被称为Pareto非劣解或非支配解.可行解X1与X2之间存在三种关系:支配、被支配以及互不支配.多目标优化问题通常会有多个非劣解,即非劣解集.非劣解集所对应的目标空间集合即为Pareto前沿.
在算法迭代过程中,对比所得的新解与外部档案解集,通过支配关系剔除被支配的解,增加支配和互不支配的解,实现外部档案的更新[29].
为避免外部档案容量过大对算法效率产生不利影响,引入NSGA-II拥挤距离机制[12]进行非劣解的评价筛选.先将每个子目标函数值按升序进行排列,然后计算子拥挤距离,每个非劣解的拥挤距离为所有子拥挤距离之和,其表达式为
(14) |
式中,k表示非劣解的个数,定义边界个体的拥挤距离为无穷大,fmi+1、fmi-1分别为第i+1、i-1个非劣解的第m个目标函数值,fmmax、fmmin分别为第m个目标函数值的最大值和最小值.
2.4 Pareto解集评价非劣解之间的支配关系只是反映了解之间的优劣,无法对Pareto解集的质量进行评价,为此引入Hypervolume指标[12]对算法迭代过程中求得的Pareto解集进行评价. Hypervolume指标表示求得的各非劣解与参考点在目标空间内的超体积.如图 5所示,在求最小值的双目标(f1和f2)优化问题中,共有五个非劣解,即x1、x2、x3、x4、x5.则Hypervolume值为非劣解x1、x2、x3、x4、x5与参考点R之间所围成的二维阴影面积.
在算法迭代过程中,Hypervolume值会随着解集不断接近问题的真实Pareto前沿而不断增大,直至算法收敛时,Hypervolume值达到最大.因此可以通过Hypervolume来评价解集的质量.
2.5 选择操作在单目标问题中,一般通过个体适应度值大小来确定选择概率,而多目标问题则无法通过适应度值大小来确定选择概率.多目标问题中各个目标函数值即为适应度函数值,无法根据某个目标函数值来确定选择概率.根据适应度值越大被选中概率越大的原则,外部档案中各非劣解均为优质个体.因此可以从外部档案中随机选择两个个体作为算法下一步操作的个体.
2.6 交叉操作虽然随机交叉操作可以增加种群个体的多样性,但拆卸线平衡问题中存在优先关系约束,随机交叉操作极易产生无法满足该约束的不可行解.为确保交叉操作后的个体满足优先关系约束,根据优先特征构建两点映射交叉方式.
选择X1,X2作为父代进行两点交叉操作,每个父代均带有两个属性向量.以图 6所示X1为例,X1上方序列表示拆卸序列,下方序列表示拆卸模式属性.随机生成一组维度与任务数等同的数组,选择其中的最大值和最小值作为两个交叉点.如图 6所示,此处分别选择1.0和0.1作为两交叉点,对应的任务1和7作为两个交叉点.保持X1序列中任务1之前的序列{6,9,10}及其对应的拆卸模式{0,1,0}不变,且保持任务7之后的序列{8,3,2}及其对应拆卸模式{1,0,1}不变.两交叉点之间的序列{1,4,5,7}及其对应的拆卸模式{0,1,1,0}通过X2映射得到,变为{1,5,7,4},X2中序列{1,5,7,4}对应的拆卸模式属性为{0,1,0,1},则可以得到新的子代Xnew1 ={6,9,10,1,5,7,4,8,3,2;0,1,0,0,1,0,1,1,0,1}.同理可以生成子代个体Xnew2={1,5,9,6,4,7,8,10,2,3;0,1,1,0,1,0,1,0,1,0}.
交叉点1前的序列和交叉点2后的序列均满足优先关系约束,两交叉点间的序列通过另一父代映射得到,该序列在另一父代中也满足优先关系约束,则组成的子代必然满足优先关系约束.
2.7 变异操作同理,随机变异操作后的序列可能不满足拆卸优先关系约束,因此可以采用基于优先关系约束的单点插入变异和双点交换变异操作.
如图 7所示,单点插入变异操作中,随机生成一组维度与任务数等同的数组,选择其中最大值作为变异点,即任务7.找到任务7的紧前任务6和5,紧后任务8.距离任务7最近的紧前任务为任务5,最近的紧后任务为任务8,则任务7可选择插在任务5和8之间,即任务7可插入任务4之后.此时通过单点变异后生成一个新的子代Xnew={6,9,10,1,5,4,7,8,3,2;0,1,0,0,1,1,0,1,0,1}.
双点交换变异操作如图 8所示,随机选取两点作为变异点,分别寻找两点的可插入位置.若两点分别为彼此的可插入点,则两点可交换位置组成新的序列满足优先关系顺序.若两点不是彼此的插入点,则交换后不能满足优先关系顺序,需重新选择变异点.
图 8中随机生成一组维度和任务数相同的数组,分别选择数组中最大值和最小值对应的点8和10作为两变异点.类似于单点变异操作,分别判断任务8和10的紧前紧后任务,找到8和10的全部可插入点.此处任务8的可插入位置是在任务10之后;任务10的可插入位置是在任务8、7、4、6、9、5、1之后.对比任务8和任务10的可插入点可知,彼此互为可插入点,故可交换任务8和任务10位置,构成新的子代Xnew={1,5,9,6,4,7,10,8,2,3;0,1,1,0,1,0,0,1,1,0}.
2.8 算法流程Step 1 参数初始化,设置种群规模Cn,最大迭代次数为Dg,初始温度T0,终止温度Tend,外部档案规模Nmax,降温系数τ,链长L,Hypervolume参考点R,节拍CT等.
Step 2 通过优先关系矩阵Y产生初始种群,设外部档案Q=ϕ.
Step 3 计算目标函数值,筛选非劣解更新外部档案Q.
Step 4 执行遗传操作中的选择、交叉、变异等操作,在变异操作中随机产生一个[0, 1]之间的随机数r,若r < 0.5,则进行单点插入变异操作,否则进行双点交换变异操作.
Step 5 模拟退火操作.
Step 5.1 当前温度T=T0,生成初始解X0,计算适应度值f(X0).
Step 5.2 开启计数器l=1.设当前解XC=X0,当前适应度值fC=f (X0);最优解XB=X0,最优解的适应度值fB=f(X0).
Step 5.3 根据当前解XC产生领域解XN,计算适应度值fN=f(XN).
Step 5.4 若XN < XC,则接受XN作为当前新解,设XC=XN,fC=f(XN)转Step 5.7.
Step 5.5 若XC < XN,则生成[0, 1]间的随机数rand;若rand < exp(-∏(fN- fC)/T),则接受XN作为当前新解,设XC=XN,fC=f(XN);否则,保持当前解XC不变,转Step 5.7.
Step 5.6 若当前解XC和XN互不占优,则两个解均被保留XC={XC,XN}.
Step 5.7 若XC < XB,则更新最优解,设XB=XC,fB=fC;否则保持最优解XB不变.
Step 5.8 若l>L,则转Step 6,否则l=l+1,转Step 5.3.
Step 6 比较Step 5所得结果与外部档案中每一个非劣解,更新外部档案Q.
Step 7 更新种群:将外部档案中的非劣解作为种群个体.计算外部档案中非劣解个数为NQ,若NQ > Cn时,则选取Cn个拥挤距离较大的非劣解作为种群个体;否则,按双点交换变异操作生成Cn-NQ个新个体,与NQ个非劣解一起作为种群个体.
Step 8 筛选非劣解,当NQ>Nmax时,保留Nmax个拥挤距离较大的非劣解留在外部档案Q中,实现外部档案的更新;否则,直接进入下一步.
Step 9 计算解集的Hypervolume值.
Step 10 若T>Tend,则执行降温操作,令T=τ×T,转Step 4;否则,进入下一步.
Step 11 算法终止,输出外部档案中的非劣解集,得到较优拆卸序列.
3 算法验证为验证所提算法的有效性,采用Matlab R2019a软件编写算法程序,运行环境为Windows 7系统,配置为Intel Core i5-3337U CPU@1.80 GHz 2.00 GB RAM.现有文献尚未有关于部分破坏性拆卸线平衡问题的实例报道,无法通过该类问题进行算法验证.但不同类型的拆线线平衡问题的本质相同,只需根据问题特征设置不同的编码和解码操作,而算法的主体结构不变.因此可采用其他类型的拆卸线平衡问题算例对所提算法的性能进行验证.
文[4]采用蝙蝠算法(bat algorithm,BA)求解了25个拆卸任务的双边电冰箱拆卸实例,该实例共4个优化指标,分别为最小化工作站数F1、空闲时间指标F2、需求指标F3、危害指标F4.根据该问题的特点编码,采用所提GSA对该算例进行求解,参照该文献的参数设置,设置种群规模为Cn=200,最大迭代次数为Dg =220. BA以及所提GSA求解结果如表 1所示.其中,编号1~8的目标值为BA的求解结果,编号9-16的目标值为GSA的求解结果.
算法 | No. | F1 | F2 | F3 | F4 |
BA | 1 | 6 | 5 907 | 461 | 42 |
2 | 6 | 6 359 | 445 | 42 | |
3 | 6 | 8 757 | 445 | 36 | |
4 | 7 | 16 859 | 454 | 34 | |
5 | 7 | 19 675 | 481 | 26 | |
6 | 8 | 28 533 | 485 | 24 | |
7 | 9 | 48 711 | 433 | 34 | |
8 | 9 | 51 679 | 435 | 30 | |
GSA | 9 | 6 | 5 845 | 473 | 33 |
10 | 6 | 5 845 | 480 | 32 | |
11 | 6 | 6 693 | 485 | 24 | |
12 | 6 | 5 881 | 459 | 32 | |
13 | 6 | 5 881 | 469 | 30 | |
14 | 6 | 5 889 | 479 | 28 | |
15 | 8 | 28 057 | 429 | 28 | |
16 | 8 | 36 821 | 441 | 23 |
分别对比GSA的每个非劣解与BA所有非劣解,统计支配关系和各单目标极值,并计算占优比,即支配解个数(n)占求解结果中的非劣解总数的比例(Δ).具体对比结果如表 2所示,表中还包括GSA的每个非劣解优于或等于BA结果的单目标最好值,分别记为g1、g2、g3、g4.
No. | 支配解 | 互不支配解 | n | Δ | g1 | g2 | g3 | g4 |
9 | 1,2,3,4,5,6,7 | 8 | 7 | 87.5% | 6 | 5 845 | — | — |
10 | 1,2,3,4,5,6,7 | 8 | 7 | 87.5% | 6 | 5 845 | — | — |
11 | 3,4,5,6,7,8 | 1,2 | 6 | 75.0% | 6 | — | — | 24 |
12 | 1,2,3,4,5,6,7 | 8 | 7 | 87.5% | 6 | 5 881 | — | — |
13 | 1,2,3,4,5,6,7,8 | — | 8 | 100.0% | 6 | 5 881 | — | — |
14 | 1,2,3,4,5,6,7,8 | — | 8 | 100.0% | 6 | 5 889 | — | — |
15 | 6,7,8 | 1,2,3,4 | 3 | 37.5% | — | — | 423 | — |
16 | 6,7,8 | 1,2,3,4,5 | 3 | 37.5% | — | — | — | 23 |
分析表 2中的结果可知,GSA的每一个非劣解均能支配多个BA的解,特别是GSA的解13和14能够支配所有的BA的解,表明GSA的求解结果优于BA的结果.此外,在单目标已知最好值上,GSA能求解出各单目标已知最好值均优于BA的求解结果.从而验证了在求解小规模问题上GSA的性能较BA具有较大优势.
对于不完全拆卸线平衡问题,文[22]和文[30]分别采用改进粒子群算法(improved particle swarm optimization,IPSO)和离散布谷鸟算法(discrete cuckoo search,DCS)求解了55个打印机拆卸实例,该实例共含4个优化目标:最小化拆卸任务数F1、最小化工作站数F2、最小化空闲时间指标F3、最小化拆卸成本F4.针对该实例,采用所提GSA进行求解,共得到5个非劣解.各算法的求解结果对比如表 3所示.
算法 | No. | F1 | F2 | F3 | F4 |
DCS | 1 | 38 | 3 | 0 | 3.902 4 |
2 | 37 | 3 | 1 | 4.037 9 | |
3 | 38 | 3 | 1 | 3.848 2 | |
4 | 37 | 3 | 4 | 3.902 4 | |
5 | 36 | 3 | 10 | 4.037 9 | |
6 | 37 | 3 | 10 | 3.848 2 | |
7 | 36 | 3 | 13 | 3.902 4 | |
8 | 36 | 3 | 37 | 3.848 2 | |
9 | 35 | 3 | 197 | 3.848 2 | |
IPSO | 1 | 47 | 4 | 0 | 5.497 8 |
2 | 48 | 4 | 2 | 5.416 8 | |
3 | 47 | 4 | 18 | 5.394 0 | |
GSA | 1 | 35 | 3 | 4 | 3.685 6 |
2 | 34 | 3 | 13 | 3.685 6 | |
3 | 36 | 3 | 2 | 3.712 7 | |
4 | 35 | 3 | 1 | 3.794 0 | |
5 | 36 | 3 | 0 | 3.739 8 |
将GSA结果与DCS和IPSO结果在4个目标上进行对比,分别比较最大值(max)、最小值(min)和平均值(avg),如图 9所示.
由图 9可知,GSA结果在4个目标上的最大值、最小值和平均值上均优于IPSO、DCS的结果.在目标F1上,GSA取得最小拆卸任务数34;在目标F2上,GSA和DCS均求得3个工作站;GSA的空闲指标F3最小值都为0,但其平均值小于IPSO和DCS;在拆卸成本上,GSA能达到最小值3.685 6,其均值比IPSO、DCS分别提高了31.5%和4.7%.对比结果验证了GSA在求解大规模问题上比IPSO、DCS更具优越性.
4 实例应用为验证模型和算法在实际工程中的应用情况,本课题组调研了某拆卸企业现场,得到废旧电视机相关拆卸数据.以该废旧电视机为例,构造部分破坏性拆卸线,并用所提GSA进行求解.该实例含27个零部件,具体拆卸信息如表 4所示.表中给出了每项任务的在不同拆卸模式下的拆卸时间(tir /s)、回收价值(pi /元)、成本(cir /元)、能耗(eir /kJ)和价值率wir,以及需求性(di)和危害性(hi).拆卸优先关系图如图 10所示.
序号 | 零件 | pi | r=1 (常规拆卸) | r=0 (破坏拆卸) | hi | di | |||||||
tir | cir | hi | eir | tir | cir | hi | eir | ||||||
1 | A型螺钉 | 0.55 | 9.2 | 1.00 | 0.36 | 3.22 | 6.8 | 0.24 | 0.32 | 1.34 | 0 | 0 | |
2 | 后盖 | 0.42 | 8.7 | 0.88 | 0.46 | 3.05 | 5.3 | 0.88 | 0.42 | 1.51 | 0 | 0 | |
3 | 天线 | 0.11 | 2.7 | 1.00 | 0.15 | 0.95 | 2.4 | 1.00 | 0.13 | 0.33 | 0 | 0 | |
4 | 喇叭 | 1.62 | 6.4 | 0.98 | 1.06 | 2.24 | 3.3 | 0.14 | 0.54 | 1.15 | 0 | 1 | |
5 | 电线 | 0.56 | 8.5 | 0.50 | 0.37 | 2.98 | 2.6 | 0.50 | 0.21 | 0.92 | 0 | 1 | |
6 | 主电路板 | 1.83 | 3.0 | 1.00 | 0.61 | 1.05 | 1.1 | 0.38 | 0.23 | 0.40 | 1 | 1 | |
7 | 电源线 | 0.10 | 9.1 | 1.00 | 0.20 | 3.19 | 6.9 | 1.00 | 0.16 | 1.00 | 0 | 0 | |
8 | 偏转线圈 | 1.50 | 8.6 | 0.85 | 0.64 | 3.01 | 2.8 | 0.28 | 0.21 | 0.99 | 0 | 1 | |
9 | 偏光调节圈 | 1.00 | 3.4 | 0.94 | 0.62 | 1.19 | 1.9 | 0.51 | 0.34 | 0.65 | 0 | 1 | |
10 | 高压帽 | 3.00 | 4.6 | 0.84 | 1.01 | 1.61 | 2.3 | 0.19 | 0.51 | 0.82 | 0 | 1 | |
11 | 消磁线圈 | 1.00 | 3.4 | 0.80 | 0.37 | 1.19 | 1.3 | 0.32 | 0.15 | 0.47 | 0 | 1 | |
12 | 接地线 | 0.13 | 3.8 | 1.00 | 0.26 | 1.33 | 3.5 | 1.00 | 0.23 | 0.78 | 0 | 0 | |
13 | 变压器 | 1.00 | 4.3 | 0.93 | 0.37 | 1.51 | 1.3 | 0.29 | 0.15 | 0.47 | 0 | 1 | |
14 | 高频头 | 3.50 | 4.6 | 0.97 | 0.96 | 1.61 | 2.0 | 0.19 | 0.41 | 0.69 | 0 | 1 | |
15 | 电子枪端电路板 | 5.00 | 5.2 | 0.85 | 1.22 | 1.82 | 2.2 | 0.12 | 0.51 | 0.75 | 1 | 1 | |
16 | 玻璃管 | 1.20 | 4.3 | 1.00 | 1.00 | 1.51 | 3.5 | 1.00 | 0.76 | 0.80 | 0 | 0 | |
17 | 电子枪 | 3.50 | 4.0 | 0.94 | 1.43 | 1.40 | 2.2 | 0.22 | 0.77 | 0.75 | 0 | 1 | |
18 | 防爆带 | 1.00 | 4.6 | 0.81 | 0.54 | 1.61 | 1.6 | 0.29 | 0.19 | 0.57 | 0 | 1 | |
19 | B型螺钉 | 0.34 | 5.1 | 1.00 | 0.23 | 1.79 | 4.6 | 1.00 | 0.22 | 0.80 | 0 | 0 | |
20 | 前壳 | 0.16 | 4.8 | 1.00 | 0.20 | 1.68 | 4.1 | 1.00 | 0.19 | 0.73 | 0 | 0 | |
21 | CRT | 2.80 | 6.7 | 0.94 | 1.75 | 2.35 | 3.3 | 0.19 | 0.86 | 1.16 | 1 | 1 | |
22 | 锥玻璃 | 0.66 | 3.3 | 1.00 | 1.10 | 1.16 | 1.7 | 1.00 | 0.56 | 0.59 | 1 | 1 | |
23 | 荧光粉 | 0.50 | 3.9 | 0.82 | 1.35 | 1.37 | 3.4 | 0.46 | 0.71 | 0.72 | 0 | 0 | |
24 | 销钉 | 0.60 | 1.4 | 0.95 | 0.35 | 0.49 | 1.2 | 0.25 | 0.29 | 0.19 | 0 | 0 | |
25 | 阳极帽 | 1.00 | 2.3 | 0.93 | 0.62 | 0.81 | 1.8 | 0.26 | 0.54 | 0.41 | 0 | 0 | |
26 | 阴极罩 | 0.80 | 2.6 | 0.83 | 0.41 | 0.91 | 2.2 | 0.40 | 0.38 | 0.45 | 0 | 0 | |
27 | 屏玻璃 | 0.30 | 2.7 | 1.00 | 0.34 | 0.95 | 2.3 | 1.00 | 0.28 | 0.33 | 0 | 0 |
根据算法特点及问题实际情况,参照文[12]设置算法参数如下:Cn=200,Dg=100,T0=100,Tend=1,Nmax=300,τ=0.985,L=10,CT=32 s,cα=0.03元/s,cβ=0.01元/s,eα=0.12 kJ/s,eβ=0.03 kJ/s.计算Hypervolume值的参考点R设为(10,2000,0,100).算法独立运行20次,取其中一次较优的结果,分析其Hypervolume值随迭代次数的变化,如图 11所示.该结果中共求得22个非劣解,所有解的目标f1均为4,因此只需对比目标f2、f3、f4,如图 12所示.
由图 11可知,算法在迭代46次时即收敛,此时Hypervolume=5.756 3×106.所得的22个非劣解在各个目标上各有侧重,决策者可根据不同侧重点选择不同的方案. 图 12中标示出了3个方案S2、S3、S4,分别在目标f2、f3、f4上取到了最好值,各方案的结果信息如表 5所示.各工作站的时间为T,利用率Δ=T/AT×100%.
No. | f1 | f2 | f3 | f4 | AT | m | Sequence | r=0 | T | Δ /% |
S2 | 4 | 0 | 8.78 | 52.41 | 29.9 | 1 | 1-2-7-3-5 | 1,2,7,3 | 29.9 | 100.0 |
2 | 19-10-15-9-8-16 | 19,16 | 29.9 | 100.0 | ||||||
3 | 4-18-11-12-20-14-6 | 20 | 29.9 | 100.0 | ||||||
4 | 13-21-22-25-23-24-27-17-26 | 23,27,26 | 29.9 | 100.0 | ||||||
S3 | 4 | 0.27 | 9.68 | 53.74 | 30.7 | 1 | 1-2-7-3-4 | 2,7,3 | 30.2 | 98.4 |
2 | 5-10-18-19-13-20 | 19,20 | 30.7 | 100.0 | ||||||
3 | 6-15-9-12-11-8-16 | 12,16 | 30.6 | 99.7 | ||||||
4 | 21-22-14-24-25-23-26-27-17 | 23,27 | 30.6 | 99.7 | ||||||
S4 | 4 | 0.34 | 8.15 | 50.27 | 29.9 | 1 | 1-2-7-3-5 | 1,2,7,3 | 29.9 | 100.0 |
2 | 6-10-15-4-12-9-11 | 12 | 29.5 | 98.7 | ||||||
3 | 19-8-13-17-18-16 | 19,16 | 29.6 | 99.0 | ||||||
4 | 20-21-22-14-23-25-24-27-26 | 20,23,25,24,27,26 | 29.6 | 99.0 |
由表 5可以看出,三种方案的目标f1相同,均为4;在目标f2,f3,f4上各方案均各有侧重点.所有方案的各工作站利用率均比较高,均超过98.4%,部分可达100%.特别是方案S2中所有的工作站均无空闲时间.每种方案的实际节拍均未超过节拍上限32,表明自适应节拍可以减少工作站的空闲时间.此外,方案S3取得最大利润9.68,破坏性任务数为9,而方案S4取得最小能耗50.27,破坏性任务数为13.两个方案在利润和能耗上各有侧重,其结果表明较多的零部件采用破坏性拆卸模式虽然可以降低能耗,但也使零部件的价值降低了,因此是否采用破坏性拆卸模式需要根据决策指标进行权衡.
每种拆卸方案的甘特图如图 13所示.图中矩形内的数字为任务编号,括号内的数字为拆卸时间,矩形的长度也表示拆卸时间,红色虚线框表示破坏性拆卸的任务.决策者可根据实际情况选择不同的方案.若决策者侧重于负荷平滑性,方案S2是最佳选项;若决策者关注利润,可选方案S3;若决策者重点考虑能耗,可选方案S4.决策者也可以同时关注某几项指标,图 12中的22个拆卸方案均为可选方案.
为了验证部分破坏性拆卸模式的有效性,增加两种对比拆卸模式,即完全常规拆卸模式和完全破坏性拆卸模式,分别计算不同拆卸模式下表 5中三种拆卸方案的四个目标函数值,如表 6所示.
No. | 完全常规拆卸模式 | 完全破坏性拆卸模式 | 部分破坏性拆卸模式 | |||||||||||
f1 | f2 | f3 | f4 | f1 | f2 | f3 | f4 | f1 | f2 | f3 | f4 | |||
S2 | 5 | 297.11 | 7.78 | 66.51 | 4 | 0.58 | 7.86 | 51.16 | 4 | 0 | 8.78 | 52.41 | ||
S3 | 10 | 416.24 | 2.50 | 87.03 | 9 | 392.21 | 2.77 | 70.90 | 4 | 0.27 | 9.68 | 53.74 | ||
S4 | 15 | 1 034.00 | -2.79 | 107.56 | 13 | 155.83 | -1.71 | 87.94 | 4 | 0.34 | 8.15 | 50.27 |
对比表 6可知,部分破坏性拆卸模式下3个方案的目标值均优于其他两种拆卸模式.计算表 6中方案S2,S3,S4采用部分破坏性拆卸模式时相较于另外两种模式在四个目标值上的改进率,分别记为Δf1、Δf2、Δf3和Δf4,结果如表 7所示.
No. | 完全常规拆卸模式 | 完全破坏性拆卸模式 | |||||||
Δf1 | Δf2 | Δf3 | Δf4 | Δf1 | Δf2 | Δf3 | Δf4 | ||
S2 | 20.00% | 100.00% | 12.85% | 21.20% | 0.00% | 100.00% | 11.70% | 2.44% | |
S3 | 60.00% | 99.93% | 287.20% | 38.25% | 55.56% | 99.93% | 249.46% | 24.20% | |
S4 | 73.30% | 99.97% | 392.11% | 53.26% | 69.23% | 99.78% | 576.61% | 42.84% |
由表 7可知,相较于完全常规拆卸模式和完全破坏性拆卸模式,部分破坏性拆卸模式除了方案S2中的目标f1与完全破坏性拆卸模式相同,其他目标下均有较大幅度的提升,最大改进率达到了576.61%.因此,部分破坏性拆卸模式比完全常规拆卸模式和完全破坏性拆卸模式的性能更优.
5 结论针对废旧产品质量和拆卸环境的不确定性,本文将破坏性拆卸模式引入到拆卸线中,构造了部分破坏性拆卸线平衡模型.提出了一种新的多目标遗传模拟退火算法优化该模型.在编码和解码过程中考虑了任务排序和拆卸模式两个变量.为保证结果的可行性,设计了基于优先关系的交叉和变异操作,并将遗传算法和模拟退火算法相结合.在两个经典算例中,所提算法的性能明显优于蝙蝠算法、改进粒子群算法和离散布谷鸟算法.在电视机拆卸线实例中,所提算法能够得到多种优质拆卸方案,验证了模型的适用性和优越性.
在未来研究中,可以将所提算法应用于其他类型的装配/拆卸线平衡问题,如U型、并行装配/拆卸线平衡问题,也可以将所提算法应该于求解其他类型的组合优化问题,如旅行商问题、车间调度问题、车辆路径优化问题等.
[1] | Gungor A, Gupta S M. Disassembly line in product recovery[J]. International Journal of Production Research, 2002, 40(11): 2569–2589. DOI:10.1080/00207540210135622 |
[2] |
张则强, 蔡宁, 曾艳清, 等.
面向再制造的拆卸线平衡问题建模理论及求解方法综述[J]. 中国机械工程, 2018, 29(21): 2636–2645.
Zhang Z Q, Cai N, Zeng Y Q, et al. Review of modeling theory and solution method for disassembly line balancing problems for remanufacturing[J]. China Mechaical Engineering, 2018, 29(21): 2636–2645. DOI:10.3969/j.issn.1004-132X.2018.21.017 |
[3] | Pistolesi F, Lazzerini B, Mura M D, et al. Emoga:A hybrid genetic algorithm with extremal optimization core for multiobjective disassembly line balancing[J]. IEEE Transactions on Industrial Informatics, 2018, 14(3): 1089–1098. DOI:10.1109/TII.2017.2778223 |
[4] |
邹宾森, 张则强, 李六柯, 等.
双边拆卸线平衡问题建模与优化[J]. 中国机械工程, 2018, 29(9): 1090–1097, 1107.
Zou B S, Zhang Z Q, Li L K, et al. Modeling and optimization for two-sided disassembly line balancing problems[J]. China Mechaical Engineering, 2018, 29(9): 1090–1097, 1107. DOI:10.3969/j.issn.1004-132X.2018.09.013 |
[5] | Zheng F, He J, Chu F, et al. A new distribution-free model for disassembly line balancing problem with stochastic task processing times[J]. International Journal of Production Research, 2018, 56(24): 7341–7353. DOI:10.1080/00207543.2018.1430909 |
[6] | Bentaha M L, Battaia O, Dolgui A, et al. Second order conic approximation for disassembly line design with joint probabilistic constraints[J]. European Journal of Operational Research, 2015, 247(3): 957–967. DOI:10.1016/j.ejor.2015.06.019 |
[7] | Kalayci C B, Hancilar A, Gungor A, et al. Multi-objective fuzzy disassembly line balancing using a hybrid discrete artificial bee colony algorithm[J]. Journal of Manufacturing Systems, 2015, 37: 672–682. DOI:10.1016/j.jmsy.2014.11.015 |
[8] | Zhang Z, Wang K, Zhu L, et al. A pareto improved artificial fish swarm algorithm for solving a multi-objective fuzzy disassembly line balancing problem[J]. Expert Systems with Applications, 2017, 86: 165–176. DOI:10.1016/j.eswa.2017.05.053 |
[9] | Song X, Zhou W, Pan X, et al. Disassembly sequence planning for electro-mechanical products under a partial destructive mode[J]. Assembly Automation, 2014, 34(1): 106–114. DOI:10.1108/AA-01-2013-006 |
[10] | Pistolesi F, Lazzerini B, Dalle M M, et al. Emoga:A hybrid genetic algorithm with extremal optimization core for multiobjective disassembly line balancing[J]. IEEE Transactions on Industrial Informatics, 2017, 14(3): 1089–1098. |
[11] | Ren Y, Yu D, Zhang C, et al. An improved gravitational search algorithm for profit-oriented partial disassembly line balancing problem[J]. International Journal of Production Research, 2017, 55(24): 7302–7316. DOI:10.1080/00207543.2017.1341066 |
[12] | Wang K, Li X, Gao L. Modeling and optimization of multi-objective partial disassembly line balancing problem considering hazard and profit[J]. Journal of Cleaner Production, 2019, 211: 115–133. DOI:10.1016/j.jclepro.2018.11.114 |
[13] |
蔡宁, 张则强, 朱立夏, 等.
多约束能耗拆卸线平衡问题的改进果蝇模糊优化[J]. 信息与控制, 2018, 47(6): 702–712.
Cai N, Zhang Z Q, Zhu L X, et al. Improved fruit-fly fuzzy optimization algorithm for multi-constrained disassembly-line balancing problem considering energy consumption[J]. Information and Control, 2018, 47(6): 702–712. |
[14] | Fang Y, Liu Q, Li M, et al. Evolutionary many-objective optimization for mixed-model disassembly line balancing with multi-robotic workstations[J]. European Journal of Operational Research, 2019, 276(1): 160–174. |
[15] | Kazancoglu Y, Ozturkoglu Y. Integrated framework of disassembly line balancing with green and business objectives using a mixed mcdm[J]. Journal of Cleaner Production, 2018, 191: 179–191. DOI:10.1016/j.jclepro.2018.04.189 |
[16] | Avikal S, Mishra P, Jain R. A fuzzy ahp and promethee method-based heuristic for disassembly line balancing problems[J]. International Journal of Production Research, 2014, 52(5): 1306–1317. DOI:10.1080/00207543.2013.831999 |
[17] | Altekin F T, Kandiller L, Ozdemirel N E. Profit-oriented disassembly-line balancing[J]. International Journal of Production Research, 2008, 46(10): 2675–2693. DOI:10.1080/00207540601137207 |
[18] | Deniz N, Ozcelik F. An extended review on disassembly line balancing with bibliometric & social network and future study realization analysis[J]. Journal of Cleaner Production, 2019, 225: 697–715. DOI:10.1016/j.jclepro.2019.03.188 |
[19] | Mcgovern S M, Gupta S M. A balancing method and genetic algorithm for disassembly line balancing[J]. European journal of operational research, 2007, 179(3): 692–708. DOI:10.1016/j.ejor.2005.03.055 |
[20] |
李六柯, 张则强, 邹宾森, 等.
免疫机制协作遗传算法的多目标拆卸线平衡优化[J]. 信息与控制, 2018, 47(6): 671–679.
Li L K, Zhang Z Q, Zou B S, et al. Optimization of multi-objective disassembly line balancing problem using immune mechanism cooperative genetic algorithm[J]. Information and Control, 2018, 47(6): 671–679. |
[21] |
丁力平, 谭建荣, 冯毅雄, 等.
基于Pareto蚁群算法的拆卸线平衡多目标优化[J]. 计算机集成制造系统, 2009, 15(7): 1406–1413, 1429.
Ding L P, Tan J R, Feng Y X, et al. Multiobjective optimation for disassembly line balancing based on Pareto ant colony algorithm[J]. Computcr Lntegrated Manufacturing Systems, 2009, 15(7): 1406–1413, 1429. |
[22] |
李六柯, 张则强, 朱立夏, 等.
多目标不完全拆卸线平衡问题的建模与优化[J]. 机械工程学报, 2018, 54(3): 125–136.
Li L K, Zhang Z Q, Zhu L X, et al. Modeling and optimizing for multi-objective partial disassembly line balancing problem[J]. Journal of Mechanical Engineering, 2018, 54(3): 125–136. |
[23] |
汪开普, 张则强, 毛丽丽, 等.
多目标拆卸线平衡问题的Pareto人工鱼群算法[J]. 中国机械工程, 2017, 28(2): 183–190.
Wang K P, Zhang Z Q, Mao L L, et al. Pareto artificial fish swarm algorithm for multi-objective disassembly line balancing problems[J]. China Mechaical Engineering, 2017, 28(2): 183–190. DOI:10.3969/j.issn.1004-132X.2017.02.010 |
[24] | Mete S, Çil Z A, Celik E, et al. Supply-driven rebalancing of disassembly lines:A novel mathematical model approach[J]. Journal of Cleaner Production, 2019, 213: 1157–1164. DOI:10.1016/j.jclepro.2018.12.265 |
[25] | Yadegari E, Zandieh M, Najmi H. A hybrid spanning tree-based genetic/simulated annealing algorithm for a closed-loop logistics network design problem[J]. International Journal of Applied Decision Sciences, 2015, 8(4): 400–426. DOI:10.1504/IJADS.2015.074612 |
[26] | Dai M, Tang D, Giret A, et al. Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm[J]. Robotics and Computer-Integrated Manufacturing, 2013, 29(5): 418–429. DOI:10.1016/j.rcim.2013.04.001 |
[27] |
陈弋文, 陈伟达.
基于收益概率的不确定环境下的产品拆卸序列优化[J]. 计算机集成制造系统, 2014, 20(4): 793–798.
Chen Y W, Chen W D. Product disassembly sequence optimization based on profit-probability under uncertain environment[J]. Computer Integrated Manufacturing Systems, 2014, 20(4): 793–798. |
[28] | Agrawal S, Tiwari M. A collaborative ant colony algorithm to stochastic mixed-model u-shaped disassembly line balancing and sequencing problem[J]. International Journal of Production Research, 2008, 46(6): 1405–1429. DOI:10.1080/00207540600943985 |
[29] |
邹宾森, 张则强, 李六柯, 等.
基于Pareto改进猫群优化算法的多目标拆卸线平衡问题[J]. 信息与控制, 2017, 46(4): 503–512.
Zou B S, Zhang Z Q, :i L K, et al. Multi-objective disassembly line balancing problem based on pareto improved cat swarm optimization algorithm[J]. Iformation and Control, 2017, 46(4): 503–512. |
[30] |
李六柯, 张则强, 管超, 等.
目标驱动离散布谷鸟搜索算法的不完全拆卸线平衡多目标优化[J]. 计算机辅助设计与图形学学报, 2018, 30(4): 681–694.
Li L K, Zhang Z Q, Guan C, et al. Multi-objective optimization for partial disassembly line balancing with goal-driven discrete cuckoo search[J]. Journal of Computer-Aided Design & Computer Graphics, 2018, 30(4): 681–694. |