考虑不确定拆卸时间的异步并行拆卸序列规划

　　摘要：因拆卸时间受操作者技能熟练程度、产品自身结构以及组成材料变化等多方面影响而存在不确定性的问题，基于灰数提出不确定拆卸时间的异步并行拆卸序列规划方法。在考虑拆卸最大规定时间约束、工作站先后顺序以及并行拆卸序列执行长度等约束条件的基础上建立最大拆卸收益与最小拆卸时间为目标的数学模型，提出一种改进人工蜂群算法。用矩阵编码构造可行解并使用锦标赛选择替代轮盘赌，在侦查蜂阶段设计一种基于潜能值的更新策略，提出一种新型的协同对比方法获得非劣解。通过算法对比验证改进算法的可行性，最后由笔记本电脑的拆卸实例来验证优化模型的有效性，实验结果表明：异步并行拆卸的经济效益提升了23.1%，拆卸时间缩短了12.7%。

　　关键词：异步并行拆卸序列规划;灰数;不确定性;改进人工蜂群算法

　　论文《考虑不确定拆卸时间的异步并行拆卸序列规划》发表在《福建理工大学学报》，版权归《福建理工大学学报》所有。本文来自网络平台，仅供参考。

　　拆卸是回收再制造的关键环节，拆卸序列规划(disassembly sequence planning, DSP)是指按照产品零部件的结构约束，探索可行的拆卸序列并找到最优拆卸顺序的过程，对拆卸效率和收益的提升具有重要意义。

　　自GUNGOR首次提出有关拆卸问题以来，国内外学者已对同步并行拆卸规划问题进行了研究。而目前拆卸研究的对象基本为大型复杂机电产品，对拆卸时间的要求逐渐提高，异步并行拆卸序列规划问题逐渐成为研究的热点。邢世雄等提出了一种改进蝙蝠算法的方法来研究拆卸序列规划问题。郭钧等提出了一种考虑不确定拆卸程度的选择性异步并行拆卸序列规划方法。孙娴静等在异步并行拆卸的基础上考虑了优先关系约束和机器工作区域冲突约束的异步并行拆卸序列规划问题。张雷等通过多个优化目标进行分析，提出一种基于环形拓扑结构的花授粉算法。贾宝惠等考虑协作度的双人异步并行拆卸序列规划模型，使操作者在优先约束下产生的闲置时间加入另一操作者进行协作。邓明星等提出了一种考虑多目标件的异步并行选择性拆卸序列规划方法，利用改进遗传算法获取最优拆卸序列规划方案。郭秀萍等考虑拆卸任务先后顺序约束并提出基于Pareto占优概念的多目标动态规划求解方法。尹凤福等建立手机拆卸混合图模型，同时考虑紧固件的连接关系，利用多种群遗传算法进行优化分析。

　　上述研究多数在确定的拆卸时间下进行序列规划的分析，现实中，拆卸时间会受到多种因素的影响，如产品的腐蚀与磨损、拆卸操作的难度、工厂设备的好坏等因素会导致拆卸作业产生诸多不确定性。为了方便处理不确定的数据，郑红斌等引入了三角模糊数的方法对不确定的目标进行求解，提出一种改进磷虾算法，验证了模型的实用性和算法的优越性。Peng Hu等研究一种新的集成RSC设计以处理相关DSP问题。在实际的拆卸作业过程中，不确定的拆卸时间往往是一个区间内的某个值，但不知其确切值，可以引入灰数来定性表示。灰数是一种能够处理不确定性的数学方法，将不确定的拆卸时间表示为灰数区间，提供更全面和准确的信息来进行后续的优化。

　　人工蜂群算法(artificial bee colony, ABC)是通过模拟蜜蜂觅食行为以及蜜蜂之间的信息共享和协作方式所提出的一种智能优化算法。因其简单性、鲁棒性和有效性，在组合优化问题中得到成功应用。

　　综上，本研究将灰数引入异步并行拆卸序列规划问题中，研究拆卸时间的不确定性，结合蜂群算法求解组合问题的优势，用改进的人工蜂群算法(improving artificial bee colony, IABC)对所提模型进行求解。

　　1 不确定拆卸时间的异步并行DSP

　　1.1 问题描述

　　图1为异步并行拆卸示意图，展示了两条拆卸线和若干操作员的工作情况，灰色的长条表示两条拆卸线，黑色圆点表示不同的拆卸任务，黑色方块表示不同的工人，虚线表示工人和任务之间的关系。

　　1.2 模型建立

　　最小拆卸时间(F_{1})表示为：

　　[

　　otimes Min F_{1}=sum_{j=1}^{J} max left(t_{11} x_{11}, t_{12} x_{12}, cdots, t_{j m} x_{j m} ight)

　　]

　　式中，(j)表示任务编号，(J)表示拆卸任务总数，(m)表示算子指数，(t_{j m})为第(m)个操作者执行拆卸操作(j)时所需时间，(x_{j m})表示决策变量，若操作(j)由第(m)个操作员执行，则(x_{j m}=1)，否则(x_{j m}=0)。

　　最大拆卸收益(F_{2})表示为：

　　[

　　Max F_{2}=sum_{j=1}^{J} sum_{i=1}^{N} C_{i j} f_{j} x_{j}-left[sum_{j=1}^{J} z_{j} x_{j}+otimes F_{1} q ight]

　　]

　　式中，(sum_{j=1}^{J} sum_{i=1}^{N} C_{i j} f_{j} x_{j})代表拆卸产品的总收入;(sum_{j=1}^{J} z_{j} x_{j}+otimes F_{1} q)为拆卸能耗，(C_{i j})表示关联矩阵，(i)为零件编号，(f)是零件的回收利润，(x_{j})表示第(j)个机械手;(z_{j})表示第(j)个任务的基本成本，(q)表示单位时间的研究成本。

　　除上述约束，所构建模型还需满足6个条件：

　　1. 一条可行拆卸路径最大操作时间不能超过规定时间约束，即：

　　[

　　sum_{l=1}^{L} max left(t_{11} x_{11}, t_{12} x_{12}, cdots, t_{j m} x_{j m} ight) leq T_{B}

　　]

　　式中，(T_{B})表示并行拆卸中规定的最大拆卸时间。

　　2. 确保整个拆卸过程中每个零件最多拆卸一次，即：

　　[

　　0 leq sum_{j=1}^{J} C_{i j} x_{j} leq 1, i=1,2, cdots, N

　　]

　　式中，(N)为零件总数。

　　3. 每次操作只能是优先互斥、协同以及关联的其中一种，即：

　　[

　　C_{i j}+P_{j k}+E_{j k} leq 1

　　]

　　式中，(P_{j k})为优先互斥矩阵，(E_{j k})为协同矩阵。

　　4. 工作站顺序约束，确保工作站按照顺序开启，即：

　　[

　　x_{w-1} geq x_{w}, forall w=1, cdots, W

　　]

　　式中，(x_{w})表示第(w)个工作站，(x_{w-1})为前一个工作站。

　　5. 一个机械手在任意一次的并行拆卸中最多执行长度为(L)的操作，即：

　　[

　　sum_{j=1}^{j}left(x_{j 1}+x_{j 2} ight) leq L

　　]

　　式中，(x_{j1})、(x_{j2})分别表示两个机械手，(L)为一个异步并行拆卸序列的长度。

　　6. 决策变量为0~1变量，即：

　　[

　　x_{j}, y_{j m} in{0,1}(j, m=1,2, cdots, J)

　　]

　　式中，如果执行拆卸任务(j)，则为(x_{j}=1);否则为0;如果操作(j)是由第(m)个操作员执行的则(y_{j m}=1)，否则为0。

　　1.3 灰数白化

　　目标函数中含有灰色不确定参数(otimes F_{1})，无法直接求解，需要进行白化处理：

　　1. 设置白化权函数：

　　[

　　varphi(x)=frac{1}{a_{1}left(x-a_{0} ight)^{2}+1}

　　]

　　式中，(varphi(x))表示白化权函数，(a_{1})表示系数，(x)表示随机变量，(a_{0})为白化权函数值最高时的白化值。

　　2. 生成白化值，将式(9)的白化权函数变换为式(10)，得到灰数(otimes)的白化值(overline{otimes})：

　　[

　　left{egin{array}{l}

　　f(x)=varphi(x) / int_{a}^{b} varphi(z) d z \

　　F(x)=int_{a}^{x} varphi(z) d z / int_{a}^{b} varphi(z) d z \

　　overline{otimes}=F^{-1}(u)

　　end{array} ight.

　　]

　　式中，(x)满足概率密度函数(f(x))以及相应的分布函数(F(x))。根据概率密度的定义，(x)的概率分布函数为(F(cdot))。若随机变量(u)服从区间([0,1])上的均匀分布，通过(F^{-1}(u))可获得符合分布(F(cdot))特征的随机数，根据式得到灰数对应 的白化值(overline{otimes}=F^{-1}(u))。

　　2 改进的人工蜂群算法

　　2.1 任务关系优先表示方法

　　在操作层次拆卸树(operation-dependent hierarchical disassembly tree, OHDT)图中，通过树状图结构呈现拆卸路径，其中每个节点代表一个组件或一个拆卸操作，如图2即展示了一台笔记本电脑的OHDT图。

　　根据图2可以得到拆卸过程中存在3种类型的关系。本研究采用矩阵(P_{j k})以表示操作(j)和(k)之间的优先互斥关系：

　　[

　　P_{j k}=left{egin{array}{l}

　　1, 若 j 在操作 k 之前且 k 无法完成 \

　　-1, 若 k 与 j 不可以一起进行 \

　　0, 其他

　　end{array} ight.

　　]

　　采用协同矩阵(E_{j k})记录任务(j)和(k)之间是否存在协同关系：

　　[

　　E_{j k}=left{egin{array}{l}

　　1, 若 j 可与 k 一起进行 \

　　0 , 其他

　　end{array} ight.

　　]

　　引入了关联矩阵(C_{i j})强调操作与拆卸零件之间的关联性：

　　[

　　C_{i j}=left{egin{array}{l}

　　1, 若 i 零件通过操作 j 得到 \

　　0, 其他

　　end{array} ight.

　　]

　　2.2 编码阶段

　　本研究提出“多解协同对比”的优化方法。用序列(S=[S_{1}, S_{2}, cdots, S_{l}])来表示操作序列，其中(l)表示总操作数，操作按1到(l)的顺序编号。随后将两个执行向量部分进行交叉以完成编码工作。编码过程如下：

　　1. 随机生成的每个可行解的元素值被标记并涂上阴影，代表了每次实际的拆卸序列，例如，(S=[5,3,8,9,14,17,15,20])被提取作为下一步的起始序列。

　　2. 执行拆卸操作，若操作(a)在操作(b)之前则操作(a)在(S)序列中位于操作(b)右侧，交换操作(a)和(b)后再次从左循环操作序列，(S_{1})至(S_{l})均重复该步骤。

　　3. 序列向量需满足协同关系;将经过上述两个步骤所得到的两个可行序列向量，一个向量首端与另一个向量末端依次进行上下的协同比对以满足矩阵(E)的协同要求。如果符合要求将保留操作;反之，标记为非阴影状态。最后可以得到两个机械手协同拆卸的序列向量。

　　2.3 解码阶段

　　可行的拆卸序列采用了矩阵解码(Z={Z_{1}, Z_{2}})来表示，图中(t_{15,1})表示机械手(Z_{1})执行操作所需的大致拆卸时间区间，(t_{16,2})表示(Z_{2})执行操作时所需的大致时间区间，(Z_{2})在(L=5)时并没有出现矩阵，表示此时为空闲状态。

　　2.4 雇佣蜂阶段

　　传统蜂群算法在该阶段通过轮盘赌来筛选蜜源从而进行下一步的操作，每次迭代都需要重新计算个体的适应度值。相比之下，锦标赛选择更为简便，且能有效地保护最优解。因此，本研究选择使用锦标赛选择来替代轮盘赌方法。

　　2.5 守望蜂阶段

　　本研究引入了遗传算法的变异操作，该策略有助于探索更广泛的解空间，提高算法的全局搜索能力。变异操作采用自适应变异概率，如式(14)所示：

　　[

　　A_{g}=A_{g}^{max }-frac{A_{g}^{max }-A_{g}^{min }}{max \_D} cdot D

　　]

　　式中，(A_{g})为变异概率;(A_{g}^{max })为最大变异概率，取(0.65);(A_{g}^{min })为最小变异概率，取(0.35);(max\_D)为最大迭代次数;(D)为当前迭代次数。

　　为了选择适应度更高的食物来源，本研究采用了贪婪的选择程序。经过变异的食物来源与原始食物来源进行比较，通过贪婪选择，将优秀的食物来源保留。

　　2.6 侦察蜂阶段

　　当雇佣蜂未能及时更新新的蜜源时，侦察蜂会在整个解集内进行搜索，在一定程度内避免了早熟机制，但也降低了寻优效率;针对该问题，本研究在IABC内提出“潜能值”定义：若新迭代的蜜源无法取代旧蜜源，则潜能值减少，反之增加;个体的潜能值将设置为一个区间内的预设值。潜能值更新公式如(15)所示：

　　[

　　Q_{i}=Q_{i}-frac{m_{i}}{S}

　　]

　　式中，(Q_{i})表示第(i)个蜜源的潜能值，(m_{i})表示第(i)个蜜源的目标函数值，(S)表示当前的最佳目标函数值。

　　2.7 IABC算法步骤

　　IABC算法具体步骤如图6所示。

　　3 算法验证

　　3.1 算法对比

　　为检验IABC的优越性，选取切诺贝利灾难算法(CDO)、机器学习算法(ILA)以及人工蜂群算法(ABC)进行比较，使用MATLAB进行1000次的迭代，收敛曲线图如图7所示。由图7可知，IABC算法在接近120次迭代时到达最优值，收敛速度要优于其他算法。

　　3.2 实例基本信息

　　现实中，相比其他的家用电器，笔记本电脑的零件成本较高且回收简单，故采用Fujitsu AH556型号笔记本作为拆卸对象，拆卸信息包括显示屏、系统板、固态驱动器、散热器等22个零件，每个零件拆卸收益从0.5元到72.3元不等。

　　3.3 算例对比

　　在改进算法下进行同步并行拆卸与异步并行拆卸的测试，取部分结果如表3和表4所示。操作过程中出现0表示此时机械手为空闲状态。

　　表3 同步并行拆卸算例帕累托解(部分)

　　|序号|机械手|过程|F1/s|F2/元|

　　|1|M1|3￫17￫6￫9￫11￫14￫13￫16|291.97|270.88|

　　||M2|4￫15￫18￫20￫0￫0￫13￫3| | |

　　|2|M1|13￫7￫9￫11￫17￫16￫0|260.47|263.91|

　　||M2|6￫4￫7￫10￫12| | |

　　|3|M1|14￫3￫6￫11￫16￫7|100.6|154.95|

　　||M2|13￫4￫8￫12￫13￫0| | |

　　表4 异步并行拆卸算例帕累托解(部分)

　　|序号|机械手|过程|F1/s|F2/元|

　　|1|M1|1￫3￫8￫10￫11￫14￫17￫18|113.3|240.4|

　　||M2|2￫4￫5￫9￫12￫13￫19| | |

　　|2|M1|2￫4￫9￫5￫12|100.4|230.9|

　　||M2|1￫8￫3￫9￫12| | |

　　|3|M1|1￫3￫8￫9￫11￫15￫7￫0|178.5|304.4|

　　||M2|2￫4￫6￫10￫14￫12￫18￫13￫0| | |

　　比较可得：异步并行拆卸平均拆卸收益为256.4元，相比同步并行拆卸的208.3元，经济效益提高了23.1%;而异步并行拆卸所用的平均拆卸时间为142.6s，相比同步并行拆卸的163.3s，时间缩短了12.7%。

　　4 结束语

　　本研究考虑实际拆卸作业中拆卸时间的不确定性，引入灰数将确定的拆卸时间拓展至不确定拆卸时间，构建了两个目标函数的异步并行拆卸数学模型。引入了优先互斥、协同和关联3个约束来描述各组件之间的操作关系，并通过OHDT来描述拆卸信息模型。结合本研究特征，设计了IABC，用锦标赛代替原本的轮盘赌策略，提出一种新型的多解协同对比的方法;在侦查蜂阶段为避免陷入局部最优，设计了潜能值的更新策略。将所提算法与现有算法进行对比，验证其优越性。最后将本研究所改进算法与所提模型应用于笔记本电脑拆卸实例，结果表明异步并行拆卸在拆卸收益与拆卸时间上均优于同步并行拆卸。本研究仅考虑了拆卸时间的不确定性，实际拆卸过程中还存在许多不确定因素，如工人的体能消耗、疲劳程度等情况，未来将深入研究。

　　参考文献

　　[1]吴秀丽,张兴宇.工位数固定的U型拆卸线部分拆卸平衡问题[J].控制理论与应用,2024,41(6):1079-1088.

　　[2]GUNGOR A,GUPTA S M.An evaluation methodology for disassembly processes[J].Computers&Industrial Engineering,1997,33(1/2):329-332.

　　[3]徐鹏程.机电产品异步并行拆卸序列规划与评价技术研究[D].杭州:浙江大学,2020.

　　[4]邢世雄,陈国华,孙川,等.基于改进蝙蝠算法的再制造装配体拆卸序列规划研究[J/OL].机械设计与制造,1-6[2024-11-08].https:∥doi.org/10.19356/j.cnki.1001-3997.20240516.008.

　　[5]郭钧,王振东,杜百岗,等.考虑不定拆卸程度的选择性异步并行拆卸序列规划[J].中国机械工程,2021,32(9):1080-1090,1101.

　　[6]孙娴静,唐秋华,邓明星.基于改进遗传算法的异步并行拆卸序列规划[J].工业工程,2022,25(4):151-157.

　　[7]张雷,耿笑荣,陶凯博.考虑碳排放与收益的随机并行拆卸线平衡优化[J].机械工程学报,2023,59(7):330-338.

　　[8]贾宝惠,任帅,卢翔.考虑协作度的双人异步并行拆卸序列规划[J].机械设计与制造,2024(1):359-363,369.

　　[9]邓明星,陈方颖,唐秋华,等.考虑多目标件的异步并行选择性拆卸序列[J].计算机集成制造系统,2020,26(7):1749-1755.

　　[10]郭秀萍,周玉莎.用多目标动态规划求解拆卸序列的Pareto最优前沿[J].系统管理学报,2023,32(6):1205-1212.

　　[11]尹凤福,刘广阔,王晓东,等.基于多种群遗传算法的废旧手机拆卸序列规划[J].合肥工业大学学报(自然科学版),2023,46(4):438-446.

　　[12]ZHANG X S,FU A P,ZHANG S,etal.Selective disassembly sequence planning under uncertainty using trapezoidal fuzzy numbers:a novel hybrid metaheuristic algorithm[J].Engineering Applications of Artificial Intelligence,2024,128:107459.

　　[13]郑红斌,张则强,曾艳清.不确定工人体能消耗的多目标U型拆卸线平衡问题[J].计算机集成制造系统,2023,29(2):392-403.

　　[14]HU P,CHU F,DOLGUI A,etal.Integrated multi-product reverse supply chain design and disassembly line balancing under uncertainty[J].Omega,2024,126:103062.

　　[15]REN Y X,GAO K Z,FU Y P,etal.Ensemble artificial bee colony algorithm with Q-learning for scheduling bi-objective disassembly line[J].Applied Soft Computing,2024,155:111415.