资源约束下拆卸线平衡问题的建模与改进混合蛙跳算法

蔡 宁 张则强 张 颖 朱立夏

西南交通大学机械工程学院，成都，610031

0 引言

资源浪费与环境污染问题已成为制约人类发展和进步的重要因素之一。面对大量的废旧机电产品，通过拆卸可将有用零部件或可修复零部件再利用，而对危害零部件进行无害处理，进而实现循环利用和绿色制造，因此，拆卸是组成产品闭环生命周期的重要环节[1]。由于实际拆卸线中的复杂性、零件数量和质量的不确定性等，各工作站间普遍存在作业不均衡现象，这会影响生产效率，极大增加了拆卸线规划设计的难度，因此，合理规划拆卸方案是优化再制造拆卸线平衡及提高作业效率的关键。

针对拆卸线所面临的拆卸方案规划难点，国内外对拆卸线平衡问题(disassembly line balancing problem, DLBP)开展了大量的探索和研究。MCGOVERN等[2]通过理论推导证明了DLBP是复杂的非确定多项式(NP)问题，随着问题规模的增大，其求解难度会呈指数级增大。目前DLBP模型的建立主要基于两种不同的描述方式：零件优先关系图和任务优先关系图[3]。KOC等[4]在AND/OR关系图的基础上，提出了TAOG(transformed AND/OR graph)的描述方式，基于任务优先关系构建了以工作站数目最小为目标的DLBP模型，分别采用整数规划和动态规划进行求解；HEZER等[3]最先提出了平行拆卸线平衡问题，使用了两条平行直线布局拆卸线，基于TAOG描述方式，以最小工作站数为目标，采用最短路径模型方法求解并与传统直线型布局DLBP进行对比，研究发现：采用平行直线布局有利于减少工作站数目。

上述文献均是基于任务优先关系图，需要引入虚拟任务且优先关系矩阵难以确定，这将增加求解难度，然而零件优先关系图的结构简单且优先关系矩阵易确定。RIGGS等[5]基于零件优先关系图，对寿命周期末端(end of life，EOL)产品的不同状态分别赋予不同的概率，并利用联合优先关系图进行求解；ZHANG等[6]基于零件优先关系图，研究了多目标模糊DLBP；REN等[7]在零件优先关系图的基础上，构建了利润导向下的不完全拆卸线数学模型。

在DLBP的求解方法上，目前主要有数学规划方法、启发式方法、智能算法等[8]。AVIKAL等[9]将模糊层次分析法与PROMETHEE方法相结合来优化拆卸任务分配。虽然启发式方法原理简单、易操作，但求解精度不高，为提高精度可将数学规划方法用于求解DLBP。ALTEKIN等[10]建立了以利润为优化目标的混合整数规划模型，实现了整个拆卸周期的利润最大化；BENTAHA等[11]建立了机会约束二进制规划模型，考虑随机的作业时间，优化了工位开启成本和危害零件处理成本。但数学规划方法只能求解小规模问题，近年来，随着问题规模的增大，求解方法集中在智能优化算法上，如引力搜索算法[7]、免疫遗传算法[12]、蚁群算法[13]和人工蜂群算法[14]等。智能算法具有求解速度快，能够处理大规模问题的优点，被广泛应用于求解DLBP。针对多目标优化问题，丁力平等[13]在多目标DLBP优化中，引入Pareto解集的思想，能够得到多种较优的方案；汪开普等[15]采用拥挤距离筛选Pareto解集;李六柯等[16]通过Hyper-volume指标来评价Pareto解集的优劣，进一步改善了求解质量。但上述文献针对多个Pareto非劣解时，依然难以抉择。

现有文献在拆卸过程中考虑资源约束的情况较少，然而实际拆卸过程中，工具和机器等资源是有限的。METE等[17]基于TAOG描述，以资源总数最小化为目标，建立单目标资源约束的DLBP模型，利用GAMS-CPLEX软件进行精确求解，但忽略了多种资源共同完成一个任务的情况，且考虑目标单一，不能全面体现出资源约束DLBP问题的特性。目前尚未发现基于零件优先关系图定义拆卸过程的资源约束下多目标DLBP的研究报道。针对DLBP中考虑资源约束的不足，本文提出了资源约束拆卸线平衡问题(resource constrained disassembly line balancing problem, RCDLBP)，建立了多目标优化的RCDLBP模型，并设计了一种结合Pareto思想的改进混合蛙跳算法(shuffled frog leaping algorithm，SFLA)，通过与测试算例进行对比以验证有效性，并将所提算法运用到具体拆卸实例。

1 资源约束DLBP数学模型

1.1 问题描述

参数定义见表1。RCDLBP是指在满足资源约束、优先关系约束等条件下，一方面，合理分配各作业任务到对应工作站，另一方面，确定拆卸任务顺序，将每个拆卸任务合理排序，使得工作站数、资源种类数最少及拆卸效率尽可能高。可以用四参数集合(T,S,Z,P)表示RCDLBP。

图1为8个零件的拆卸优先关系图，假设完成一项拆卸任务得到一个零件，实线箭头为AND优先关系，如任务2、5、6与任务8满足AND关系，当任务2、5、6全部完成拆卸后才可以执行任务8；虚线箭头为OR优先关系，如任务2、3和任务6，任务2和任务3至少有一项任务已完成，任务6即可执行。

在文献[10, 14]的基础上，采用一种新的优先关系矩阵P=(ali)n×n，其中ali为0、1、-1三个变量值，若任务l∈PAND(i)，则ali=1，若l∈POR(i)，则ali=-1，若两者均不满足，则ali=0。资源相关矩阵Q=(bir)n×R，若任务i需要资源Zr，则bir=b(i,Zr)=1，否则bir=b(i,Zr)=0。假设有Z1、Z2、Z3、Z4四种资源，则图1的优先关系矩阵P、资源相关矩阵Q可分别表示为

表1 参数说明表Tab.1 Parameter description table

图1 拆卸实例零件优先关系图Fig.1 Parts priority relationship diagram of disassembly example

Z1Z2Z3Z4

1.2 RCDLBP数学模型的建立

为方便数学模型的建立，对RCDLBP进行如下假设[15]：①废旧拆卸产品属于完全拆卸，零件不存在缺损等情况；②忽略零件或组件在工作站之间的移动时间；③拆卸线为直线型布局且为单品种拆卸；④拆卸产品的供给量是无限的；⑤拆卸线处于正常不中断状态。基于上述模型假设和参数定义来建立多目标RCDLBP模型。

各决策变量的表达式如下：

目标函数：

minGF=(f1，f2，f3)

(1)

(2)

(3)

(4)

约束条件：

(5)

(6)

(7)

‖Nkr‖≠0 ∀r,k

(8)

(9)

(10)

Sk+1≤Skk=1，2，…，M-1

(11)

(12)

式(1)为优化的三个目标；式(2)为最小化工作站数；式(3)为最小化危害指数；式(4) 为最小化资源总数，尽可能将需要相同资源的任务分配在同一个工作站中。约束条件中，式(5)和式(6)为优先关系约束，其中式(5)为AND优先关系约束，式(6)为OR优先关系约束；式(7)表示若存在一个需要资源Zr的任务在工作站k中完成，则Mkr=1；式(8)为工作站数约束，以确定其上下限；式(9)为任务分配约束；式(10)为拆卸节拍约束；式(11)确保工作站分配的编号连续；式(12)用来确定开启的工作站有任务分配。

2 求解RCDLBP的蛙跳算法

混合蛙跳算法(SFLA)具有概念简单、计算速度快、全局寻优能力强等特点[18]，且搜索框架灵活，已受到国内外学者的广泛关注，在求解车辆路径问题、柔性车间调度问题和装配线序列规划问题[18-19]等组合优化问题上均表现出一定的优越性，而多目标RCDLBP也属于组合优化问题，为此，本文设计了一种结合Pareto解集和最大满意度思想的改进SFLA，其主要流程包括种群初始化、种群分组、局部搜索和全局搜索。

2.1 产生初始可行解

本文采用文献[10]的编码方式，基于改进的优先关系矩阵P，提出了一种新的初始解产生方式，在满足优先关系条件下可保证解的随机性，其步骤如下：

(1)从优先关系矩阵P中选择每列元素为-1的位置，行编号对应的所有任务则构成满足OR关系任务集合V1的一个元素子集，例如由图1得到的优先关系矩阵P可知，第6列对应任务为任务2、3，其他列没有满足OR关系的任务，则V1={(2, 3, 6)}。

(2)从优先关系矩阵P中找出所有列之和为0对应的任务，来构成当前可分配任务集合V2，若V2≠∅，则在V2中随机选择一个任务j作为当前的拆卸任务，否则转至步骤(5)。

(3)判断该任务是否属于集合V1中的某个元素子集的元素，若不属于则转至步骤(4)，否则找出V1中包含任务j的元素子集C，其中任务i为C中的一个特殊元素，它与其他各元素满足OR关系约束。若步骤(2)中选择的任务j满足j∈POR(i)，则令C中排除i的任意元素为l，其对应优先关系矩阵中的元素均满足ali=0，并转至步骤(4)，否则，直接转至步骤(4)。如针对图1对应的优先关系矩阵P,若j=2，则令a26=0、a36=0。

(4)通过修改优先关系矩阵P释放已分配任务的优先顺序约束，令P中的第j行和第j列全部置为0，然后转至步骤(2)。

(5)结束任务分配，得到初始可行解。

2.2 种群分组方式

由于本文涉及多个目标协同优化，无法简单地对所求解进行排序，但在寻优过程中需要保存种群中每次全局搜索得到的最优解Gbest及每次局部搜索得到的各个族群中的最优解Pbest和最差解Pworst，因此采用一种基于最大满意度的方法进行排序，具体步骤如下：

(1)求出每个青蛙个体对应于不同目标的满意度μ(fi(X))，其计算表达式如下：

μ(fi(X))=

(13)

式中，ci为第i个目标通过单目标优化得到的较优值；X为拆卸序列向量；fi(X)为多目标优化时第i个目标值；δi为第i个目标的伸缩值。

(2)计算出每个青蛙个体的最大满意度λ，并按照从大到小的顺序排列，其表达式如下：

λ=min(μ(f1(X))，μ(f2(X))，…，μ(fH(X)))

(14)

式中，H为目标的个数。

(3)基于满意度的排序选择分组，分组方式如下：

(15)

u=1,2，…,mj=1,2，…,F/m

2.3 局部搜索策略

为了优化搜索方向使其最终趋向于全局最优个体，对蛙群个体执行局部搜索，即对每个族群最差的个体进行更新操作，更新策略满足式：

S=rand(Pbest-Pworst)

(16)

S=rand(Gbest-Pworst)

(17)

Pnew=Pworst+SS≤Smax

(18)

式中，Gbest为蛙群中具有最大满意度的解；Pbest、Pworst分别为每一个子族群中具有最大满意度的解和最差满意度的解；rand(·)为分布在[0,1]内的随机数；S为青蛙的跳动步长；Smax为最大步长；Pnew为更新后的Pworst。

首先依据式(16)和式(18)更新最差解，若无改进，则依据式(17)和式(18)更新最差解，若依然无改进，则利用初始解产生方式随机产生一个解。针对离散优化问题，为了让每个子族群具有一定的更新能力，通常采用调整序的思想进行局部离散搜索，本文在基本SFLA的基础上，采用文献[19]中调整序的思想进行局部搜索。

由于DLBP属于较强约束关系的组合优化问题，需要判断每个个体局部搜索后的可行性，这会增加额外的运行时间，因此本文在局部搜索中引入一种可满足优先约束关系的交叉和变异操作。随机产生一个数，若rand(·)>0.5，则采用交叉操作，若rand(·)≤0.5，则采用变异操作。为了增加解的多样性，采用一种四点交叉方式，产生4个随机点将每个父代分为5段，分别为0-1、1-2、2-3、3-4、4-5片段，将父代P1的0-1、2-3、4-5片段全部复制给子代O1，父代P1剩下1-2、3-4片段的所有元素按照父代P2中相同元素出现的顺序排列，并填充到O1的空余位置，按照同样的原则产生子代O2，具体四点交叉过程如图2所示。

图2 交叉操作示意图Fig.2 Cross operation schematic diagram

具体变异方式见图3，产生2个随机点，将一个子代个体O1分为3个片段，分别为0-1、1-2、2-3片段，复制子代O1的0-1、2-3片段给O1new，将中间1-2片段的顺序重新排列，其步骤如下：①删除优先关系矩阵P中关于0-1、2-3片段所有元素的优先关系约束，然后得到新的优先关系矩阵P*;②在新的优先关系矩阵P*条件下，依据产生初始解的过程，对1-2片段的所有元素进行随机重新排列，将排列好的元素插入到O1new的1-2片段对应的位置，则构成新的子代O1new。

图3 变异操作示意图Fig.3 Mutation operation schematic diagram

2.4 全局信息交换

为了收集各族群搜索的局部信息，获得全局最优解新的搜索方向，需进行全局信息交换。各个族群经过L次局部进化搜索后，先将各族群中青蛙个体混合在一起，不断更新种群，然后将青蛙个体按满意度降序排序并重新划分族群，保存当代全局最优解Gbest，以确保青蛙个体间的元信息得到充分的传递，再重复进行局部搜索和进化，直到达到最大迭代次数G，最后算法停止运行。

2.5 多目标处理方法

为协同优化多个目标，本文采用Pareto支配的思想，对于H个目标最小化问题的任意两个解Xp和Xq，若解Xq的每个子目标函数值均不小于解Xp的每个子目标函数值，即满足

(19)

则称为XpPareto支配Xq。所有Pareto最优解对应的目标值构成Pareto前沿，由于DLBP的复杂性，真实的Pareto前沿是未知的，因此本文将当前文献中所求的最好结果和改进蛙跳算法所求结果汇总，并将Pareto筛选后的结果作为近似的Pareto前沿。

(20)

包含H个目标的非劣解X的拥挤距离可表示为

(21)

2.6 改进蛙跳算法的求解步骤

在求解RCDLBP问题中，改进SFLA的流程图见图4，具体步骤如下：

(1)设置改进SFLA算法参数，包括确定种群规模F、最大迭代次数G、子族群数m、局部进化次数L、外部档案容量Nq。

(2)依据2.2节规则产生规模为F的初始种群，设置外部档案Q=∅。

(3)依据2.3节规则将个体排序并分组，记录全局最优解Gbest和各族群局部最优解Pbest、最差解Pworst。

(4)局部进化迭代循环，对各个子族群执行2.4节中改进的局部搜索，IP为局部迭代计数参数，直到局部进化次数达到L。

(5)将每个族群混合，进行全局搜索并更新种群，然后进行Pareto解集筛选，并更新外部档案Q, 其中N1为更新种群后计算得到的非劣解个数。

(6)全局循环至最大迭代次数G时算法停止运行，其中IG为全局迭代计数参数。

3 算例验证与实例应用

基于Win10系统的MATLAB R2010b平台开发蛙跳算法程序，运行环境为Intel Corel i7-6700(3.40GHz)CPU，8.00G内存。对具有25个任务的DLBP算例(以下简称“P25”)进行参数筛选和算法性能验证，并采用改进SFLA求解电冰箱拆卸实例的RCDLBP模型，每个算例运行10次，保存每次运行结果和平均运行时间。

图4 改进混合蛙跳算法流程图Fig.4 Flow chart of improved shuffled frog-leaping algorithm

3.1 算例验证分析

为便于算法的参数筛选，同时为得到近似Pareto前沿以便于对比验证，将文献[21]中的P25拆卸实例作为测试算例，引入文献[21]中最小化均衡指标F3、最小化需求指数F4，P25考虑的其他2个目标和本文f1、f2一样，分别用F1、F2表示，则P25的优化目标为minGF=(F1,F2,F3,F4)。

多目标改进SFLA算法的主要参数为：种群规模F、最大迭代次数G、子族群数m、局部进化次数L和外部档案容量Nq，为了得到较好的求解效果，从参数常用的选择范围中筛选最佳参数组合：种群规模F为{100,150,200,250}，最大迭代次数G为{80,90,100,110}，子族群数m为{5,10,25,50}，局部进化次数L为{10,15,20,25}，外部档案容量Nq为{8,10,12,14}。利用Minitab软件进行田口实验和统计分析，将五因子四水平的参数组合成16组实验，采用改进SFLA求解P25的多目标数学模型，每组参数运行10次，计算出所求非劣解的最大满意度的平均值，其结果见表2。

表2 最佳参数组合实验Tab.2 Optimal parameter combination experiment

由表2可知，满意度均值越大，所求解的质量越好。采用田口实验中的望大特性函数对表2中的结果进行分析，见图5。依据信噪比的均值越大对应的参数越优的准则，可得到图5最佳参数组合为：F=200，G=100，m=50，L=10，Nq=12。

图5 效果图Fig.5 Effect diagram

采用最佳参数组合求解P25，可得12组Pareto非劣解，其结果见表3。为综合评价改进SFLA算法多目标优化的性能，并与基本SFLA和经典的多目标优化算法NSGA-Ⅱ[20]进行对比，基本SFLA的参数设置为：Smax=5，其他参数则依据最佳参数设置。采用程序运行时间td、非支配解比率(RP)、趋近度(CM)、空间评价指标(SP)4个指标对比分析基本SFLA、改进SFLA、NSGA-Ⅱ，性能对比结果见表4，其中，td用于评价程序的运行速度，该值越小越好；RP用于评价所求非劣解集不被其他非劣解集支配的非劣解个数所占比重，非支配解比率的值越大表示解的质量越好；趋近度是收敛性指标，用于反映非劣解与真实Pareto前沿的的逼近程度，趋近度指标的值越小越好；空间评价指标是分布性指标，用于反映方法的分布性能，空间评价指标的值越大越好，说明分布越均匀。

表3 改进FSLA求解P25的结果Tab.3 The result of P25 solved by improved FSLA

通过分析表4可知，NSGA-Ⅱ分布性较好，运行时间适中，但收敛性很差；基本SFLA分布性较好，收敛性较好，但运行时间最长；改进SFLA虽然分布性稍差一些，但收敛性、求解质量和运行时间均优于其他二种算法，因此，改进SFLA求解多目标DLBP的综合性能优于其他两种算法，具有良好的求解优势。

表4 多目标优化的性能对比Tab.4 Performance comparison of multi-objective optimization

注：加粗的数据为最优结果。

3.2 实际案例分析

现以某企业废旧电冰箱拆卸为实例，表5所示为电冰箱的相关拆卸信息(如拆卸时间t、零件危害指数h、需求资源Z等),其中拆卸主要用到4种资源Z1～Z4，分别代表扳手、专用夹具、配送框、机器。图6为电冰箱的拆卸任务优先关系图，结合企业实际生产计划，设定节拍Tc=130 s。

表5 冰箱拆卸信息表Tab.5 Refrigerator disassembly information form

运用改进SFLA对具有25个任务的电冰箱拆卸实例进行优化，按照最佳参数组合设置改进SFLA的参数，求解电冰箱的RCDLBP模型，并得到4组Pareto非劣解，其结果见表6。

为了便于决策，采用种群分组中涉及的最大满意度方法，依据式(13)、式(14) 确定最大满意度值。由表6可知，最大满意度值为0.667，方案3为最佳拆卸方案，其具体任务分配情况见图7。

图6 电冰箱优先关系图Fig.6 Priority relation diagram of refrigerator

表6 电冰箱的拆卸方案Tab.6 Refrigerator disassembly program

图7 最满意的电冰箱拆卸任务分配Fig.7 The most satisfactory refrigerators dismantling assignment

4 结论

(1)考虑实际拆卸过程中的AND/OR关系，对优先关系矩阵进行修改，加入了OR关系的描述，同时增加了资源约束相关的约束条件和目标，构建以工作站数目、危害指数、资源总数均最小的多目标资源约束拆卸线平衡问题(RCDLBP)模型。

(2)将Pareto的思想融入混合蛙跳算法(SFLA)中，针对多目标优化问题，依据最大满意度进行排序使种群快速分组，为改进局部搜索策略和提高收敛速度，提出了一种新的交叉、变异操作，为维护外部档案容量且保持解的均匀分布，采用了拥挤距离机制。

(3)在算例验证过程中，依据田口实验筛选出改进SFLA的最佳参数组合，将具有25个任务的拆卸线平衡问题算例作为测试算例并与基本SFLA和NSGA-Ⅱ所求结果进行对比，通过非支配解率、运行时间、趋近度和空间评价指标对比分析所求Pareto解集，并验证了改进SFLA的优越性。将所提出的改进SFLA用于求解电冰箱的RCDLBP模型，得到了4组Pareto非劣解，为便于决策，采用最大满意度法筛选出了一个最满意的拆卸方案。