文章快速检索  
  高级检索
考虑零件分类的U型拆卸线平衡问题与改进烟花算法求解
张则强1,2, 张颖1,2, 蒋晋1,2, 朱立夏1,2     
1. 西南交通大学机械工程学院, 四川 成都 610031;
2. 轨道交通运维技术与装备四川省重点实验室, 四川 成都 610031
摘要: 针对拆卸生产线中存在的不确定性和零件复杂性,构建以最小化工作站数、空闲指标、拆卸成本及零件分类指标的多目标数学模型并采用一种改进烟花算法对所提模型进行求解.首先,考虑所求解问题的特性对烟花算法进行离散化处理,重新定义了爆炸操作和变异操作,烟花个体产生爆炸火花和变异火花之后引入Pareto解集思想和NSGA-II拥挤距离机制对可行解进行筛选并更新烟花个体.其次,将所提烟花算法分别应用于求解中规模直线型和大规模U型拆卸线平衡问题算例中,并与其它算法的求解结果对比,验证改进烟花算法在直线型和U型拆卸线上的求解性能.最后,将所建模型和算法应用到打印机拆卸线中,并与直线型求解结果进行对比,对比结果表明所提方法有效可行.
关键词: U型拆卸线平衡     多目标优化     改进烟花算法     零件分类     Pareto解集    
An Improved Fireworks Algorithm for U-shaped Disassembly Line Balancing Problem Concerning Parts Classification
ZHANG Zeqiang1,2, ZHANG Ying1,2, JIANG Jin1,2, ZHU Lixia1,2     
1. School of Mechanical Engineering, Southwest Jiaotong University, Chengdu 610031, China;
2. Technology and Equipment of Rail Transit Operation and Maintenance Key Laboratory of Sichuan Province, Chengdu 610031, China
Abstract: In view of the uncertainties and the complexity of parts in the disassembly line, we build a multi-objective mathematics model that includes minimizing the number of workstations, idle index, disassembly cost, and the classification index and present an improved fireworks algorithm to solve it. First, we discretize the fireworks algorithm considering the characteristics of the problem to be solved and redefine the explosion operation and mutation operation. After the explosion and mutation sparks are generated by the fireworks individual, we use Pareto solution set and NSGA-Ⅱ congestion distance mechanism to screen the feasible solution and update individual fireworks. Second, we use the proposed fireworks algorithm on the disassembly-line balancing problem of linear medium-scale and U-shaped large-scale examples and verify the performance of the improved fireworks algorithm by comparing it with other algorithms. Finally, we apply the model and algorithm to the printer disassembly line. The proposed mathematics model and algorithm are more effective and feasible than linear solutions.
Keywords: U-shaped disassembly line balancing     multi-objective optimization     improved fireworks algorithm     parts classification     Pareto solution set    

0 引言

随着科技的进步,常用的机电产品更新换代的速度不断加快,在电子产品中尤为常见,处理废旧电器电子产品也将面临严峻考验.再制造具有节能和对环境影响低等特点,其主要是把消费者使用后的废旧品进行回收、拆解和修复,并用于新产品生产的过程[1].拆解是再制造的关键步骤,因为它有利于控制从报废产品中不断增加的废物.为了规范废旧电器电子产品回收处理活动,促进综合资源利用与循环经济的发展,我国政府积极调控市场,废旧电器电子产品应当由有资质的处理企业进行回收处理,学习欧洲实行的生产者和销售者需承担废旧电器电子产品的回收责任制,扶持正规回收企业,加强监管,提高正规回收企业的竞争力[2].回收的废旧电器电子产品需要进行有效的处理才能进入循环经济之中,不同的零件处理方式不同.因此,需要将拆卸下来的零件进行分类整理,但每个工作站分配的零件过于繁杂,容易增加工人的视觉搜索时间和场地面积,所以,拆卸现场零件的分类管理有待进一步优化.

拆卸线平衡问题(disassembly line balancing problem,DLBP)自2001年提出以来[3],一直受到关注与研究,具有广泛的应用前景;特别是面对当前日趋严峻的资源环境问题,研究DLBP更具有特殊重要的意义.求解DLBP的方法包括启发式算法[4]、数学规划方法[5]和智能算法[6-10]. DLBP需考虑多个目标协同优化,但启发式算法和数学规划方法都只能转化为单目标进行求解,适用范围受限.因此,衍生出适用于求解属于NP完全问题[11]的DLBP的智能算法,包括蚁群算法[7]、禁忌搜索算法[8]、粒子群优化算法[9]、模拟退火算法[10]、变邻域搜索[11]等,但这些方法实质依然是转化为单目标进行求解.文[12]提出求解多目标的DLBP问题,运用Pareto解集思想保留互不占优的解,解的多样性得以保留.

在Pareto多目标的问题研究中,李六柯等[13]提出了一种基于Pareto解集的多目标免疫机制协作遗传算法,解决拆卸线上工作站负荷不均衡问题;Wang等[14]在大型废品的拆解中引入双边布置,建立随机双边拆卸线平衡数学模型,并运用离散花朵授粉算法进行优化;邹宾森等[15]建立了包含最小化工具更换次数的多目标DLBP数学模型,克服了忽略拆卸工具的不足;Liu等[16]考虑拆卸优先关系和顺序相依拆卸时间增量,提出多目标顺序相依DLBP优化模型并验证模型的合理性和有效性.

以上文献研究的DLBP布局形式均为传统的直线型,但U型布局具有占地面积少、物流路径短等优点[17]. U型布局生产线上的工作站相距较近,具有柔性高,选择作业范围更广等特点,任务分配效果一般比直线型布局更好[18].文[19]基于混流U型拆卸线平衡问题的排序问题,考虑拆卸时间的不确定性,进行了随机混流U型的拆卸线平衡排序问题研究.目前暂未有在拆卸线研究中考虑零件分类的情况,而对拆卸下来的零件进行分类存储是库存管理的必要条件. Li等[20]认为备件分类规则对库存管理具有重要意义,制定备件分类规则是库存管理的必要条件,这对于拆卸下来的零件也同样适用,做好已拆卸零件的分类工作可减轻后续工作;文[21]认为不同的材料具有不同的质量相关属性,提出了一种考虑材料质量特性、质量成本和材质影响的材料分类体系.由于废旧产品属于回收物品,零件的质量和成本均受到影响,所以在对废旧零件进行分类的时候,主要考虑零件的材料质量特性,建立考虑零件分类条件下的数学模型.

烟花算法(FireWorks Algorithm,FWA)是一种具有爆炸式搜索机制的新型群体智能算法[22],具有结构简单,寻优能力强,适用于求解复杂问题等特点,在连续性问题[23]和离散型问题上[24]均表现出良好的求解性能,鉴于拆卸线平衡问题属于离散型问题,本文选用烟花算法对拆卸线平衡问题进行研究.

由于拆卸线上涉及的零件种类繁多、材质和性能不一等因素,在每个拆卸工作站上需要放置不同的零件暂存装置,降低零件暂存装置的个数可以提高工人的操作熟练度,因此,本文提出考虑零件分类的拆卸线平衡问题(parts classification disassembly line balancing problem,PCDLBP),建立考虑零件暂存区的多目标数学模型,运用改进烟花算法(Improved FireWorks Algorithm,IFWA)求解所提模型,重新定义烟花算法的爆炸操作和变异操作,并引入Pareto解集思想[12]和拥挤距离机制[25]处理本文的多目标问题.

1 考虑零件分类的DLBP数学模型 1.1 问题描述

拆卸生产线是废旧产品回收利用重要环节,一个废旧产品的组成部分不一,各种零件的形状、规格、材质也不同,如果不将拆卸下来的零件加以分类,会增加拆卸完成之后的零件分类整理工作.因此,在拆卸过程中便对待拆卸产品的零件进行合理的分类,并且使同一类零部件尽量分配在相同工作站,减轻后续零件的分类整理工作.以图 1中的U型布局为例,暂存装置颜色相同的表示零件属性相近,零件的处理方式相同,拆卸下来可以放在一起.工作站1和工作站4有相同的零件,如果把这类零件的两个操作放在同一个工作站可减少一个零件暂存装置.同理,工作站1和工作站2、工作站3、工作站4分别有属性相同的零件,可将这类零件的操作合并.

图 1 带有零件暂存装置的U型拆卸线示意图 Fig.1 Diagram of U-shaped disassembly line with part temporary storage device
1.2 数学模型

问题假设:1)待拆卸产品的所有零件类别已知,每个零件不可再分;2)待拆卸产品的零部件完好无损;3)拆卸产品单一;4)拆卸时间已知,无流转时间;5)各零件规格尺寸、材质已知;6)待拆卸产品无限供应;7)拆卸线为U型布局;8)工人熟练度一致;9)工作中无突发情况.

决策变量:

文中参数说明:I为待拆卸零件总数;J为拆卸过程中允许开启的最多工作站数目,无特殊情况下J= Ij为工作站编号,j =1,2,…,Jil为任务编号,il =1,2,…,Iu为零件种类编号,u =1,2,…,Uxij为第i个任务与第j个工作站入口侧的关系;yij为第i个任务与第j个工作站出口侧的关系;CT为工作站生产节拍;ti为第i个任务的操作时间;UTi为第i个任务的单位时间拆卸成本;STj为完成第j个工作站所有任务的实际时间(单位s);Dj为工作站j实际零件分类总数;S为优先关系集合,若(il)∈S,则任务i为任务l的直接前序,必须完成任务i之后才能完成任务l.

目标函数:

(1)

目标函数F1为开启工作站总数,每开启一个工作站需要投入一定的固定成本:

(2)

目标函数F2为工作站空闲时间均衡指标,该目标尽可能小能避免出现生产线闲忙不均的现象:

(3)

其中,

(4)

目标函数F3为拆卸成本,将拆卸成本高的拆卸任务尽可能分配在同一工作站能降低拆卸成本:

(5)

目标函数F4为零件分类存储区,将同一类零件的任务分配到同一个工作站:

(6)

其中,

(7)

约束条件:

(8)
(9)
(10)
(11)
(12)

式(8)表示开启工作站总数的取值范围;式(9)表示开启的工作站实际操作时间不超过节拍时间;式(10)表示每个任务必须分配在U型拆卸线的入口侧或出口侧进行操作;式(11)表示零件分类存储区个数介于零件种类和任务总数之间;式(12)表示U型拆卸线上的任务必须满足拆卸优先约束关系.

2 求解PCDLBP的IFWA

烟花算法主要由爆炸算子、变异算子、映射规则及选择策略四个部分构成,根据本文问题的特性,需要对烟花算法操作重新进行离散化定义.

2.1 初始解的产生

设待拆卸产品的零件个数为I,任务i=1,2,…,I表示拆卸对应零件的拆卸任务,如图 2所示的任务优先约束中,优先约束矩阵为B=[bil]n×n,若任务i为任务l的直接紧前任务,则bil为1,否则为0.初始解的产生流程如图 3所示.

图 2 任务优先关系图 Fig.2 Task priority relation schema
图 3 初始解的产生 Fig.3 Generation of the initial solutions
2.2 Pareto解集评价

对于多目标的可行解中,以最小化M个子目标为例,解空间中的任意可行解Y1Y2满足式(13),则称Y1Pareto支配Y2,解空间中所有不被支配的解称为非劣解,对应的目标函数称为近似Pareto最优前沿.

(13)

当非劣解个数N0超过外部档案规模NQ时,需淘汰一部分非劣解,引入NSGA-II的拥挤距离机制对烟花适应度值进行排序.对每一个非劣解的子目标进行升序排列,m∈{1,2,…,M},fm的两个边界解拥挤距离为1,其余子目标拥挤距离为

(14)
(15)

其中,i∈{2,…,NQ-1},NQ为外部档案个数,wim表示在第i个解在第m个子目标上的拥挤距离,Wi为第i个解的拥挤距离,fmminfmmax和分别为第m个子目标的最小值和最大值.

2.3 爆炸算子

在烟花种群中,设定烟花的质量一致,因此规定烟花的爆炸半径相同,产生随机数组定义每个烟花的爆炸火花数目,每个烟花在爆炸半径内产生爆炸火花.产生爆炸火花的步骤为:

Step 1  计算烟花种群的烟花个数,输入爆炸半径R,产生c=randperm(YH_num)的数列.

Step 2  第i个烟花的爆炸烟花数目Zi=c(i).

Step 3  令j=1.

Step 4  在烟花Yjn-R位置内寻找随机d0.

Step 5  根据爆炸半径R寻找爆炸终点位置de=d0+R.

Step 6  爆炸半径内的任务修改优先关系约束矩阵B得到新的优先关系矩阵B*,解除爆炸半径之外任务的紧前紧后约束,令其对自身的优先关系约束为1.在此操作之后,对爆炸半径之内每个任务的紧前紧后约束进行修改.在爆炸半径内的任务,若其紧前任务位置在整个爆炸半径位置之后,令其紧前任务对其的约束为1;若其紧后任务位置在整个爆炸半径位置之前,修改其对紧后任务的约束为1.

Step 7  爆炸生成新的拆卸序列.

Step 8  产生第i个烟花的第j个爆炸火花Yij.

Step 9  若j < Zi,令j=j+1,返回Step 4;否则,执行Step 10.

Step 10  计算爆炸火花的适应度值,保留非劣解和与之对应的爆炸火花.

Step 11  若i < YH_num,令i=i+1,返回Step 2;否则,执行Step 12.

Step 12  终止爆炸操作.

爆炸操作如图 4所示.

图 4 爆炸操作示意图 Fig.4 Schematic diagram of the explosion operation
2.4 变异算子

烟花进行爆炸操作之后,通过Pareto解集保留非劣解,为使种群保持多样性,对爆炸火花的较优解进行变异操作,产生变异火花.先将拆卸序列上出口侧和入口侧的任务用符号区分开来,出口侧的任务前添加符号“-”表示.当所选任务在入口侧拆卸时,在拆卸序列中寻找该任务最近的入口侧紧前任务作为其紧前任务,该任务最近的入口侧紧后任务作为其紧后任务;当所选任务在出口侧拆卸时,即标号为“-x”形式的任务,选取该任务在出口侧最近的紧后任务作为其紧前任务,该任务在出口侧最近的紧前任务作为其紧后任务.任务的变异插入点在紧前任务和紧后任务的位置之间,无紧前任务则将序列的始端作为紧前位置,若无紧后则选择拆卸序列末端作为紧后位置,每个可插入的位置产生一个新的火花,变异操作如图 5所示.

图 5 变异操作示意图 Fig.5 Schematic diagram of mutation operation
2.5 个体更新策略

在对烟花进行爆炸操作和变异操作之后,采用Pareto解集思想和拥挤距离机制对烟花、爆炸操作产生的爆炸火花和变异操作的变异火花进行非劣解的筛选,更新外部档案,随机挑选外部档案中一个解作为下一代烟花的当代个体.

2.6 算法流程

改进的烟花算法流程如图 6所示.

图 6 改进烟花算法流程图 Fig.6 Flow chart of the improved fireworks algorithm
3 算例验证

为验证所提算法的合理性和优越性,本文在Win 10系统下,硬件配置为Inter(R)Core(TM)i5-7400 CPU @3.00 GHz,4.00 GB内存的计算机上,采用Matlab R2016b开发了所提算法的实验程序,应用到中规模和大规模算例上,验证所提算法的求解性能.

3.1 中规模直线型DLBP算例验证

中规模算例采用文[6]中的移动电话机拆卸实例,该实例具有25个拆卸任务,求解目标为:最小化工作站数目F1,最小化空闲指标F2,最小化需求指标F3及最小化危害指标F4.由于25算例的规模不大,依然采取直线型的求解方式进行求解,将求解结果与变邻域搜索(variable neighborhood search,VNS)[6]、粒子群优化(particle swarm optimization,PSO)算法[9]、模拟退火(simulated annealing,SA)算法[10]、遗传算法(genetic algorithm,GA)[27]、强化学习(reinforcement learning,RL)算法[26]等精确求解结果和文[15]运用猫群模拟退火(cat swarm optimization and simulated annealing,CSOSA)算法的多目标求解结果进行对比,各算法的目标值如表 1所示.

表 1 6种算法求解P25的结果 Tab.1 Results of 6 algorithms for solving P25
序号 算法 F1 F2 F3 F4
1 VNS 9 9 825 76
2 PSO 9 9 857 80
3 SA 9 9 853 81
4 GA 9 9 868 82
5 RL 9 9 862 97
6 9 9 823 77
7 9 9 825 76
8 10 111 900 73
9 CSOSA 10 155 889 72
10 11 395 870 70
11 12 531 807 72
12 12 559 802 72

IFWA对25规模的DLBP求解参数设置为:拆卸节拍CT=18 s,种群规模YH_num=100,最大迭代次数maxcycle=90,爆炸半径R=6,外部档案规模N=8,算法程序在相同环境下循环迭代20次,取其一次结果表示如图 7所示.

图 7 IFWA求解P25结果 Fig.7 IFWA solution for P25

对比表 1图 7可知,IFWA在与序号1~序号5的精确解的对比中,占优于GA、SA、PSO与RL的求解结果,图 7中的方案2与VNS求得的结果相同,因此本文所提多目标IFWA算法求解P25的结果优于精确求解结果.在与求解多目标的CAOSA对比中,IFWA能求得与表 1中序号6、序号7、序号8、序号10、序号12相同解,而方案3、方案4、方案8与表 1中序号9、序号11互不支配.在多目标求解结果中,IFWA能求得4个F1的最优值为9,CSOSA只求得的两个F1的最值,在F2上IFWA和CSOSA都能求得两个最优值9,在F3F4上两种算法都能求得最值.实验结果证明,IFWA在求解中规模拆卸线平衡问题中效果良好,适用于求解中规模的直线型拆卸线平衡问题.

3.2 大规模算例验证

为验证所提的IFWA在大规模算例中的求解性能,以文[12]中的52算例(下文简称P52)为研究对象进行实验求解.为便于比较,P52算例的目标函数仍以文[12]中最小化闲置率FIdle、最大化负荷均衡指标FSmooth、最小化成本指数FCost三个目标作为研究对象.

经过算法参数调试,最终设置P52大规模算例的参数为:拆卸节拍CT=600 s,种群规模YH_num=50,最大迭代次数maxcycle=100,爆炸半径R=10,外部档案规模N=10,算法程序运行20次,如表 2所示为其一次结果表示.

表 2 IFWA求解U型P52的平衡方案 Tab.2 IFWA solving the balance scheme of U-shaped P52
序号 任务分配方案 FIdle FSmooth FCost
1 {29,-43,-26,-5}→{4,33,-6,-18,-42,-48,-52}→{37,-19,-50,-17,-41,-40,28,-16,-39,31,-51,-32}→{-38,36,-27,-21,-20,-23,-45}→{3,-9,-49,-11,-25}→{-30,-44,-46,1,12}→{34,47,15,-10,-2,22,35,7,-13,-14,24,8} 0.057 9 0.999 2 135.078
2 {26,-20,-5}→{29,-19,-42,-18,-44,-52,-48,-27,37}→{-17,-50,-41,-43,-40,-45,28,-16,4,15,31,32,39,-38}→{-21,36,-51,-49,-23,-11,3}→{1,-6,-33,-30}→{-9,-25,12}→{34,-46,-47,-10,-2,22,35,7,-13,-14,24,8} 0.057 9 0.941 4 124.536
3 {26,-5,-20}→{29,33,42,36,18,-19,-52}→{-43,-17,-48,47,37,-44,-50,-41,-40,28,-16,4,15,-38}→{31,32,-51,-49,-45,-27,-23,3}→{21,1,-6,-30}→{-25,12,9}→{34,46,-10,-2,22,35,7,-13,-11,-39,-14,24,8} 0.057 9 0.966 6 124.806
4 {-5,-33,-26}→{29,-43,-19,-17,-52,-44,-48,28,-41,37,-50,-40,-16}→{4,32,-38,-18,-42,-51,-49,-23}→{36,21,-27,-39,-45,-20,-11,3}→{1,31,-6,12}→{25,9,-30,-46}→{34,47,15,-10,-2,22,35,7,-13,-14,24,8} 0.057 9 0.992 1 127.284
5 {26,-5,-20}→{-43,29,33,-19,-42,-52,-17,-18}→{-44,37,-48,-50,-41,-45,-40,-16,4,31,32,39,-38,-51}→{-49,-27,36,21,-23,-11,3}→{28,1,12,-6}→{-30,-46,-9,-25}→{34,47,15,-10,-2,22,35,7,-13,-14,24,8} 0.057 9 0.996 3 130.980
6 {29,-43,-26,-5}→{4,33,-6,-18,-42,-48,-52}→{37,-19,-50,-17,-41,-40,28,-16,-39,31,-51,-32}→{-38,36,-27,-21,3,-23,-49}→{-20,-9,-45,-11,-25}→{-30,-44,-46,1,12}→{34,47,15,-10,-2,22,35,7,-13,-14,24,8} 0.057 9 0.998 7 133.926
7 {29,-43,-26,-5}→{-20,-33,-19,-42,37,18,-52}→{-44,-17,-48,-50,-41,-45,-40,-16,4,31,32,-27,-38}→{-51,-49,-39,36,21,-23,-11,3}→{28,1,12,-6}→{-30,-46,-9,-25}→{34,47,15,-10,-2,22,35,7,-13,-14,24,8} 0.057 9 0.997 3 132.060
8 {-5,-33,-26}→{-43,-19,-17,-52,-44,-48,28,-41,37,39,-50,-40,-16,4}→{32,-38,-18,31,42,-51,-49,29}→{-27,-21,36,-23,-45,-20,-11}→{3,1,-6,-30,-46}→{12,9,25}→{34,47,15,-10,-2,22,35,7,-13,-14,24,8} 0.057 9 0.976 9 125.004
9 {26,-5,-20}→{29,33,-48,-42,36,18,47}→{-17,-52,-43,-19,37,-44,-50,-41,-40,28,-16,4,-38}→{31,39,32,-51,-49,-45,-27,-23,3}→{21,1,-6,-30}→{-25,12,9}→{34,46,15,-10,-2,22,35,7,-13,-11,-14,24,8} 0.057 9 0.973 1 124.914
10 {-5,-33,-26}→{29,-43,-19,-17,-52,-44,-48,28,-41,37,-50,-40,-16}→{4,32,-38,-18,-51,-49,-27,-23}→{-42,-39,36,21,-45,-20,-11,3}→{1,31,-6,-30,-46}→{12,9,25}→{34,47,15,-10,-2,22,35,7,-13,-14,24,8} 0.057 9 0.987 0 125.802

为测试IFWA的性能,将本文所求P52算例的U型拆卸方案与3种直线型的求解方案进行对比,文[28]、文[29]和文[15]中分别采用遗传模拟退火(genetic algorithm and simulated annealing,GASA)算法、细菌觅食算法(bacterial foraging optimization,BFO)和CSOSA求解P52算例,布局形式均为直线型.鉴于4种算法的闲置率均为0.057 9,因此着重比较FSmoothFCost两个指标,对比见图 8. IFWA完全占优于BFO与GASA所求得的解.在与CSOSA求得的结果对比中,IFWA的平滑率均值为98.29%,略低于CSOSA的平滑率均值0.984 2,但能求得平滑率最值为99.92%;在成本指数中,IFWA的成本指数均值为128.439,低于CSOSA的平滑率均值133.625 1且能求得成本最小值为124.536的拆卸方案,对拆卸企业追求低成本拆卸这一指标有益.因此,本文所提算法求解的U型拆卸优于直线型拆卸.

图 8 IFWA与直线型求解P52的结果对比 Fig.8 Comparison of IFWA and linear solution for P52

文[17]采用蚁群遗传算法(ant colony and genetic algorithm,ACGA)求解52规模的U型拆卸线平衡问题,从图 9可看出,对比ACGA和IFWA的求解结果,FIdle指标均为0.057 9,在FSmooth指标上,ACGA所求均值为95.314%,最大值为99.00%,本文所提算法求解均值为98.286%,最大值为99.92%,优于ACGA算法.同理,在成本指数FCost上,IFWA的求解结果也更优. IFWA求解结果支配ACGA所求得的所有结果,证明本文所提的算法适用于U型拆卸平衡问题.

图 9 P52算例U型求解结果FCostFNsmooth对比图 Fig.9 Comparison diagram of FCost and FNsmooth for U-type solution results of P52 examples
4 考虑零件分类的实例应用 4.1 PCDLBP的U型应用

为进一步验证本文所提IFWA的合理性与适用性,将IFWA应用到某型号的打印机拆卸线中,考虑本文所提约束和目标进行求解,该打印机具有55个零件即55个拆卸任务(下文简称P55),P55优先约束关系见图文[15],拆卸信息见表 3,零件分类一列根据零件的材质和处理方式等进行划分,将材质或处理方式相同的零件归为同一类,赋予相同的分类代号.

表 3 P55的拆卸信息表 Tab.3 P55 disassembly information table
任务编号 拆卸时间/s 拆卸成本/(¥/s) 零件分类
1 3 0.002 9 1
2 3 0.002 9 2
3 2 0.002 7 3
4 16 0.005 5 4
5 5 0.003 3 5
6 40 0.010 3 6
7 18 0.005 9 7
8 8 0.003 9 4
9 33 0.008 9 7
10 8 0.003 9 4
11 13 0.004 9 7
12 5 0.003 3 8
13 16 0.005 5 4
14 10 0.004 3 9
15 18 0.005 9 1
16 24 0.007 1 4
17 4 0.003 1 10
18 8 0.003 9 4
19 2 0.002 7 7
20 16 0.005 5 4
21 32 0.008 7 4
22 15 0.005 3 11
23 6 0.003 5 7
24 2 0.002 7 1
25 2 0.002 7 1
26 16 0.005 5 4
27 32 0.008 7 4
28 4 0.003 1 1
29 15 0.005 3 12
30 2 0.002 7 1
31 40 0.010 3 4
32 3 0.002 9 7
33 8 0.003 9 4
34 2 0.002 7 13
35 24 0.007 1 4
36 2 0.002 7 7
37 15 0.005 3 14
38 2 0.002 7 15
39 32 0.008 7 4
40 36 0.009 5 7
41 32 0.008 7 4
42 4 0.003 1 7
43 16 0.005 5 4
44 3 0.002 9 16
45 8 0.003 9 4
46 2 0.002 7 4
47 8 0.003 9 4
48 2 0.002 7 1
49 2 0.002 7 1
50 10 0.004 3 17
51 32 0.008 7 4
52 2 0.002 7 1
53 2 0.002 7 18
54 8 0.003 9 4
55 2 0.002 7 7

P55算例的沿用P52算例的参数设置,算法程序运行20次,取其一次结果如表 4.由IFWA求解本文所提模型的结果可以看出,7个解中,F1均为5;空闲指标F2在1 125~1 129之间;拆卸成本F3在5.835~6.645之间;本文考虑的零件分类暂存区在23~26之间.从表 4可以看出,在考虑零件暂存区个数的情况下,对空闲指标和拆卸成本有不同的影响,表 4中方案7和方案1对比,零件分类暂存区个数减少11.54%,空闲指标和拆卸成本分别增加0.36%和1.4%,说明零件暂存区的个数对空闲指标和拆卸成本的影响不大,但是空闲指标、拆卸成本及零件分类暂存区个数均最小不可兼得.决策者在选择方案时,若考虑空闲指标尽可能小,可以选择表 4中的方案1和方案2;若考虑拆卸成本尽可能小,选择方案5;若零件分类指标比较重要,则选择方案7;若要考虑各个指标均衡则可以选择方案3和方案4.

表 4 U型P55任务分配方案 Tab.4 U-shaped P55 task allocation scheme
方案 任务分配方案 F1 F2 F3 F4
1 {-29,10,-17,12,-26,-53,-42,-23,-44,8,11,33,45,-36,-37,-19,-13}→{-35,-16,-3,4,-51,-41,-46,-2}→{31,9,7,30,6,-55}→{-27,-14,-1,21,24,-43,-18,39}→{20,40,-50,-47,15,52,28,5,-38,-32,-48,-49,-54,25,34,22 5 1 125 6.405 26
2 {-29,10,-17,12,-26,-53,-42,-23,-44,8,11,33,45,-36,-37,-19,-13}→{-35,-16,-3,4,-51,-41,-46,-2}→{31,-14,9,21,7,-55}→{-6,-1,30,24,27,-43,-18,39}→{20,40,-50,-47,15,52,28,5,-38,-32,-48,-49,-54,25,34,22} 5 1 125 6.645 25
3 {-29,10,-17,12,2,-26,-53,-42,-23,8,11,33,45,-36,-37,-13,-34}→{-35,31,6,-51}→{-16,-3,-41,9,4,14,7}→{21,-44,-27,39,40}→{43,1,47,18,15,24,19,30,-50,20,52,28,5,-55,-38,-46,-32,-48,-49,-54,25,22} 5 1 127 6.015 25
4 {-29,-2,10,-17,12,-26,-53,-3,-42,-23,-44,8,11,-38,-34,35,-55,-37}→{9,36,45,-19,-51,-33,-41,7}→{13,27,-16,39,21}→{6,40,31,-32,47,18}→{43,15,46,-50,-14,-30,25,4,52,28,5,24,1,48,49,-54,-22,-20} 5 1 127 6.135 24
5 {-29,10,-17,12,-26,-53,-3,-42,-23,-44,8,11,-38,-55,33,34,-37,-19,-36,-13}→{-35,-16,-27,-32,9,7}→{21,41,45,-51,39}→{6,40,31,15,25}→{4,30,43,52,47,-50,-18,-14,-46,28,5,24,1,48,49,-54,-22,-20,-2} 5 1 129 5.835 25
6 {-29,10,-17,12,-26,-53,-3,-42,-23,-44,8,11,-38,-55,33,34,-37,-19,-36,-13}→{-35,-16,-27,-32,9,7}→{21,41,45,-51,39}→{6,40,31,14,47}→{15,30,4,-50,-18,-52,43,25,46,28,5,24,1,48,49,-54,-22,-20,-2} 5 1 129 5.895 24
7 {-29,-2,10,12,-26,-53,-3,-42,-23,-44,8,11,-38,45,9,-19,-55,-36}→{-35,21,-51,33,41,34,-17}→{31,6,-16,-27}→{-37,-32,-13,7,39,40,47,18}→{43,15,46,-50,-14,-30,25,4,52,28,5,24,1,48,49,-54,-22,-20} 5 1 129 6.495 23
4.2 PCDLBP的直线型应用

为与U型的PCDLBP进行比较,在相同的参数设置下,仍然采用本文所提IFWA对P55算例进行直线型求解,求得10个解于表 5中.在直线型的PCDLBP中,每个解开启的工作站数同样为5,空闲指标F2在1 127~1 551之间,拆卸成本在5.895~7.125之间,零件分类暂存区个数在23~27之间.为便于更直观的比较,在图 10中表示出IFWA求解直线型和U型布局的PCDLBP结果,其中编号1~10为直线型的求解结果,编号11~17是本文模型求解的U型结果.直线型求解的空闲指标、成本指数和零件分类指标三个目标的均值分别为1 253.8、6.5、24.8,U型求解的3个目标均值分别为1 127.3、6.2、24.6.可以看出,在U型拆卸中3个目标均比直线型求解更优,空闲指标F2比直线型降低10.09%,成本指数F3降低4.62%,零件分类指标F4降低1%,这可能是在零件种类比较细致,但仍能表明U型拆卸具有更大的优化空间.

图 10 P55算例直线型拆卸和U型拆卸对比 Fig.10 Comparison of linear disassembly and U-shaped disassembly for P55 example
5 结论

1) 本文在传统的U型拆卸线中协同考虑了零件分类等指标,根据零件的属性将同一类的零件赋予相同的分类编号,构建了PCDLBP数学模型,并运用改进烟花算法进行求解.

2) 考虑PCDLBP的多目标离散型问题特征,重新定义了烟花算法的爆炸操作和变异操作,通过Pareto机制筛选出非劣解,烟花个体产生的火花采用Pareto解集思想和拥挤距离机制进行筛选、更新外部档案.将所提算法运用到直线型的P25算例和U型的P52算例中,均表明IFWA在求解DLBP中更具优势.

3) 将IFWA应用到本文所提U型PCDLBP中,求解得到7个方案,为决策者提供了多样化的选择,求解直线型的PCDLBP得到10个解,结果表明本文所提算法和数学模型具有合理性.

4) 在政府加大对废旧电子产品的支持力度的情况下,各回收企业应做好回收再制造的枢纽工作未来可以在零件的仓储物流等方面进行结合.

表 5 求解直线型的PCDLBP结果 Tab.5 Solving PCDLBP results of linear shaped
方案 任务分配方案 F1 F2 F3 F4
1 {2,27,4,10,41,13,8,18,3}→{9,11,19,7,39,40}→{6,31,21,26,20}→{15,28,45,30,35,36,24,25,22,54,23,32,55,47,42,1,48,52,29,49,37}→{50,51,33,38,43,44,34,53,12,14,5,16,46,17} 5 1 551 6.645 23
2 {8,27,9,41,3,42,21}→{18,10,28,11,12,25,1,15,7,33,14,34,23,20,19,30,24}→{39,40,6,31}→{13,52,32,22,4,5,49,2,26,29,45,54,55,48,37}→{16,17,47,50,38,43,51,46,53,44,35,36} 5 1 507 5.895 27
3 {2,27,4,10,41,12,13,8,18,5,3}→{9,15,24,11,7,28,19,1,6}→{35,45,31,26,20,39}→{21,30,36,40,25,22,54,23,32,43,55,49,48,52,38,42}→{29,47,37,44,33,50,34,51,53,14,16,46,17} 5 1 131 7.125 23
4 {3,27,18,4,8,41,9,2}→{15,24,19,10,1,23,13,25,28,12,42,26,11,20,7,30}→{21,35,45,22,33,39,54,34,5,55}→{40,47,31,49,48,6,32,36,52}→{43,37,38,50,51,44,29,53,14,16,46,17} 5 1 127 6.375 26
5 {2,27,4,10,41,13,8,18,3}→{9,15,11,21,35,7}→{6,31,39,40}→{20,19,26,28,45,30,36,24,25,22,54,23,32,55,48,47,42,29,49,1,50,52}→{51,37,33,38,43,44,34,53,12,14,5,16,46,17} 5 1 429 6.315 25
6 {41,12,2,10,27,8,9,11}→{21,28,18,15,1,7,25,42,14,30,39,24}→{13,31,6,19,3,40}→{20,22,4,5,52,33,34,49,26,29,32,45,54,38,37,48}→{16,47,17,50,51,43,46,53,44,23,55,35,36} 5 1 127 6.315 27
7 {2,27,4,10,41,13,8,12,18,3}→{9,19,11,21,7,39}→{31,40,6,35}→{26,20,15,28,45,30,36,24,25,22,54,23,32,55,48,47,42,1,43,52,49}→{50,38,37,29,33,51,44,34,53,14,5,16,46,17} 5 1 237 6.375 24
8 {18,12,3,8,10,19,27,41,9,42}→{15,1,24,13,11,23,4,26,28,7,5,25,20}→{31,6,21,45,22}→{35,54,36,39,33,2,40,55,30,52,48,34,47,32,49}→{37,43,44,50,38,51,29,53,14,16,46,17} 5 1 127 6.495 25
9 {2,27,4,10,41,12,13,8,18,5,3}→{9,15,24,11,7,45,39,28,1,19}→{31,35,6,26,20}→{21,30,36,40,25,22,54,23,32,43,55,49,48,52,38,42}→{29,47,37,44,33,50,34,51,53,14,16,46,17} 5 1 131 6.915 24
10 {2,27,4,10,41,12,13,8,18,5}→{9,3,15,24,11,7,19,1,6}→{39,40,31,21}→{26,20,28,45,35,30,36,25,22,54,23,32,43,55,49,48,52,38,42}→{29,47,37,44,33,50,34,51,53,14,16,46,17} 5 1 171 6.765 24
参考文献
[1] 张桂涛, 胡劲松, 孙浩, 等. 考虑产品寿命次数的多期闭环供应链网络均衡[J]. 信息与控制, 2015, 44(1): 29–37.
Zhang G T, Hu J S, Sun H, et al. The closed-loop supply chain network equilibrium with products lifetime in multi-period planning model[J]. Information and Control, 2015, 44(1): 29–37. DOI:10.13976/j.cnki.xk.2015.0029
[2] Salhofer S, Steuer B, Ramusch R, et al. WEEE management in Europe and China-A comparison[J]. Waste Management, 2016, 57: 27–35. DOI:10.1016/j.wasman.2015.11.014
[3] Gungor A, Gupta S M, Pochampally K. Complications in disassembly line balancing[C]//1st International Conference on Environmentally Conscious Manufacturing. Bellingham, WA, USA: SPIE, 2001: 289-298. 10.1117/12.417274
[4] Mcgovern S M, Gupta S M. 2-opt heuristic for the disassembly line balancing problem[J]. Proceedings of SPIE-The International Society for Optical Engineering, 2003, 5262: 71–84.
[5] Koc A, Sabuncuoglu I, Erel E. Two exact formulations for disassembly line balancing problems with task precedence diagram construction using an and/or graph[J]. ⅡE Transactions, 2009, 41(10): 866–881.
[6] Kalayci C B, Polat O, Gupta S M. A variable neighbourhood search algorithm for disassembly lines[J]. Journal of Manufacturing Technology Management, 2014, 26(2): 182–194.
[7] Mcgovern S M, Gupta S M. Ant colony optimization for disassembly sequencing with multiple objectives[J]. International Journal of Advanced Manufacturing Technology, 2006, 30(5/6): 481–496.
[8] Kalayci C B, Gupta S M. A tabu search algorithm for balancing a sequence-dependent disassembly line[J]. Production Planning & Control, 2014, 25(2): 149–160.
[9] Kalayci C B, Gupta S M. A particle swarm optimization algorithm with neighborhood-based mutation for sequence-dependent disassembly line balancing problem[J]. The International Journal of Advanced Manufacturing Technology, 2013, 69: 1–4. DOI:10.1007/s00170-013-4997-7
[10] Kalayci C B, Gupta S M. Simulated annealing algorithm for solving sequence-dependent disassembly line balancing problem[J]. IFAC Proceedings Volumes, 2013, 46(9): 93–98. DOI:10.3182/20130619-3-RU-3018.00064
[11] 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
[12] 丁力平, 谭建荣, 冯毅雄, 等. 基于Pareto蚁群算法的拆卸线平衡多目标优化[J]. 计算机集成制造系统, 2009, 15(7): 1406–1413.
Ding L P, Tan J R, Feng Y X, et al. Multiobjective optimization for disassembly line balancing based on Pareto ant colony algorithm[J]. Computer Integrated Manufacturing Systems, 2009, 15(7): 1406–1413.
[13] 李六柯, 张则强, 邹宾森, 等. 免疫机制协作遗传算法的多目标拆卸线平衡优化[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. DOI:10.13976/j.cnki.xk.2018.7217
[14] Wang K P, Li X Y, Gao L. A multi-objective discrete flower pollination algorithm for stochastic two-sided partial disassembly line balancing problem[J]. Computers & Industrial Engineering, 2019, 130: 634–649.
[15] 邹宾森, 张则强, 蔡宁, 等. 工具约束下多目标拆卸线平衡问题的猫群模拟退火算法[J]. 计算机集成制造系统, 2018, 24(9): 2210–2222.
Zou B S, Zhang Z Q, Cai N, et al. Cat swarm simulated annealing algorithm for disassembly line balancing problem under tool constraint[J]. Computer Integrated Manufacturing Systems, 2018, 24(9): 2210–2222.
[16] Liu J, Wang S W. A proposed multi-objective optimization model for sequence-dependent disassembly line balancing problem[C]//3rd International Conference on Information Management. Piscataway, NJ, USA: IEEE, 2017, 421-425. 10.1109/INFOMAN.2017.7950420
[17] 张则强, 汪开普, 朱立夏, 等. 多目标U型拆卸线平衡问题的Pareto蚁群遗传算法[J]. 西南交通大学学报, 2018, 53(3): 628–637.
Zhang Z Q, Wang K P, Zhu L X, et al. Pareto hybrid ant colony and genetic algorithm for multi-objective U-shaped disassembly line balancing problem[J]. Journal of Southwest Jiaotong University, 2018, 53(3): 628–637.
[18] 焦玉玲, 邢小翠, 朱春凤, 等. 简单直线和U型装配线平衡中的改进阶位法[J]. 同济大学学报(自然科学版), 2019, 47(1): 143–148.
Jiao Y L, Xing X C, Zhu C F, et al. Modified ranked positional weight technique for assembly line balance of simple line and U-shape[J]. Journal of Tongji University (Natural Science), 2019, 47(1): 143–148.
[19] 谷新军, 郭秀萍. 随机混流U型拆卸线平衡排序问题多目标进化算法优化[J]. 运筹与管理, 2017, 26(9): 52–61.
Gu X J, Guo X P. Multi-objective evolutionary algorithm optimization of stochastic mixed-model U-shaped disassembly line balancing and sequencing problem[J]. Operations Research and Management Science, 2017, 26(9): 52–61.
[20] Li B, Zhang R F. Research on mining classification rules of spare parts based on grey rough set theory[J]. Applied Mechanics & Materials, 2011, 52-54: 1638–1643.
[21] Cai H, Yu T, Xia C. Quality-oriented classification of aircraft material based on SVM[J]. Mathematical Problems in Engineering, 2014.
[22] Tan Y, Zhu Y. Fireworks algorithm for optimization[C]//International Conference on Advances in Swarm Intelligence. Berlin, Germany: Springer-Verlag, 2010: 355-364.
[23] 朱启兵, 王震宇, 黄敏. 带有引力搜索算子的烟花算法[J]. 控制与决策, 2016, 31(10): 1853–1859.
Zhu Q B, Wang Z Y, Huang M. Fireworks algorithm with gravitational search operator[J]. Control and Decision, 2016, 31(10): 1853–1859.
[24] Lu C, Li J. Assembly sequence planning considering the effect of assembly resources with a discrete fireworks algorithm[J]. The International Journal of Advanced Manufacturing Technology, 2017, 93: 9–12.
[25] Bader J, Zitzler E. Hype:An algorithm for fast hypervolume-based many-objective optimization[J]. Evolutionary Computation, 2011, 19(1): 45–76. DOI:10.1162/EVCO_a_00009
[26] Tuncel E, Zeid A, Kamarthi S. Solving large scale disassembly line balancing problem with uncertainty using reinforcement learning[J]. Journal of Intelligent Manufacturing, 2014, 25(4): 647–659. DOI:10.1007/s10845-012-0711-0
[27] Kalayci C B, Polat O, Gupta S M. A hybrid genetic algorithm for sequence-dependent disassembly line balancing problem[J]. Annals of Operations Research, 2016, 242(2): 321–354. DOI:10.1007/s10479-014-1641-3
[28] 汪开普, 张则强, 朱立夏, 等. 多目标拆卸线平衡问题的Pareto遗传模拟退火算法[J]. 计算机集成制造系统, 2017, 23(6): 1277–1285.
Wang K P, Zhang Z Q, Zhu L X, et al. Pareto genetic simulated annealing algorithm for multi-objective disassembly line balancing problem[J]. Computer Integrated Manufacturing Systems, 2017, 23(6): 1277–1285.
[29] 胡扬, 张则强, 汪开普, 等. 多目标拆卸线平衡问题的Pareto细菌觅食算法[J]. 计算机应用研究, 2016, 33(11): 3265–3269.
Hu Y, Zhang Z Q, Wang K P, et al. Pareto based bacteria foraging optimization algorithm for multi-objective disassembly line balancing[J]. Application Research of Computers, 2016, 33(11): 3265–3269.
http://dx.doi.org/10.13976/j.cnki.xk.2020.9480
中国科学院主管,中国科学院沈阳自动化研究所、中国自动化学会共同主办。
0

文章信息

张则强, 张颖, 蒋晋, 朱立夏
ZHANG Zeqiang, ZHANG Ying, JIANG Jin, ZHU Lixia
考虑零件分类的U型拆卸线平衡问题与改进烟花算法求解
An Improved Fireworks Algorithm for U-shaped Disassembly Line Balancing Problem Concerning Parts Classification
信息与控制, 2020, 49(4): 489-498.
Information and Control, 2020, 49(4): 489-498.
http://dx.doi.org/10.13976/j.cnki.xk.2020.9480

文章历史

收稿/录用/修回: 2019-08-30/2020-11-28/2020-03-05

工作空间