第Ⅱ类拆卸线平衡问题建模及优化

王书伟，郭秀萍，刘佳

(1.西南交通大学经济管理学院，四川 成都 610031；2.青岛理工大学商学院，山东 青岛 266520)

1 引言

科技进步以及人们消费水平的提高加快了产品更新换代的速度，大量废弃产品导致了严重的资源浪费，以及巨大的环境污染。拆卸是将废旧产品分解成若干零部件的发散过程，其一方面是将有价值的零部件或原材料从废旧产品中分离出来用于再制造，以提高废旧产品的再利用价值；另一方面是将有危害的零部件有效拆除，以减少废旧产品对人体和生态环境的危害。面对大规模产品拆卸，采用流水线的方式可实现零部件的精细化拆卸。然而拆卸过程复杂，需对作业任务合理排序并均衡分配，以最大化拆卸线效益。

自Gungor和Gupta[1]于2001年提出拆卸线平衡问题DLBP，研究者便采用启发式算法[2-3]和传统数学方法[4-5]等对其进行求解。启发式方法简单易实现，但解精度不高，而传统数学方法虽求解精度高，但耗时较长。DLBP已被证明是NP-complete[6]，解空间随问题规模增大呈爆炸式增长，因此，求解精度较高、速度更快的智能算法更适用于DLBP的优化。考虑不完全拆卸，Ren Yaping等[7]以最大化利润为目标，构建了部分拆卸DLBP优化模型，并提出一种重力搜索算法。针对拆卸过程中任务间的相互干扰，Kalayci等[8-10]分别采用遗传算法、粒子群搜索算法和变邻域搜索算法优化顺序相依DLBP。考虑不同类型产品混流拆卸，Agrawal和Tiwari[11]提出了随机混流U型DLBP模型，并设计了协作蚁群算法。基于Pareto理论，胡杨等[12]通过细菌觅食算法求解多目标DLBP。考虑拆卸时间不确定，Kalayci和Hancilar[13]采用人工蜂群算法求解模糊DLBP。

以上对DLBP的研究均是在给定拆卸线节拍时间(Cycle time, CT)的前提下，最小化工作站开启数量。参照装配线平衡问题划分方式[14]，该类问题可定义为第I类DLBP(DLBP-I)，而第II类DLBP(DLBP-II)则是在工作站开启数量一定的情况下最小化节拍时间，以最大化拆卸效率。目前对DLBP-II的研究较少，仅有Bentaha等[15]和Kalayclar等[16]分别以工作站作业负荷均衡和利润最大化为目标对其展开研究。然而，当企业拆卸线构建完毕，工作站的数量则已确定，为了提高拆卸效率，需最小化节拍时间以便在最短周期内完成产品拆卸，因此，对DLBP-II的研究符合企业实际拆卸情形。鉴于此，本文针对拆卸线工作站开启数量固定，以最短节拍时间和均衡工作站上的作业负荷为目标构建第Ⅱ类拆卸线平衡问题优化模型，并提出一种并行动态邻域深度搜索(Parallel Dynamic Neighborhood Depth Search,PDNDS)算法进行求解。

2 问题描述与建模

2.1 问题描述

图1 任务关系图

2.2 符号说明

相关符号如下：

i，j：零部件(任务)编号，i,j=1, 2, …,N；

k：工作站编号，k=1, 2, …,M；

ti：任务i的拆卸作业时间；

Pij：零部件i、j的拆卸先后关系，若零部件i是j的前驱零部件则Pij=1，否则Pij=0；

xik：0-1变量，若任务i分配到工作站k则xik=1，否则xik=0。

CT：整数变量，表示节拍时间。

2.3 数学模型

考虑最短节拍时间和均衡任务在工作站上的分配，构建第II类DLBP数学模型如下：

目标函数：

minf1=CT=max{STk|1≤k≤M}

(1)

(2)

约束条件：

(3)

(4)

(5)

(6)

目标函数：式(1)表示最小化节拍时间，即在最短周期内完成产品拆卸，以提高拆卸效率；式(2)为平滑指数，用于平衡各工作站上的任务量。约束条件：式(3)保证每个任务都被分配；式(4)为拆卸优先关系约束，即前驱任务要先于后继任务拆卸；式(5)为节拍时间约束，以限定分配到工作站上的任务数量，使其总作业时间不超过节拍时间；式(6)表示每个工作站至少有1个任务分配，即无工作站闲置。

3 PDNDS算法设计与实现

变邻域搜索算法是由K个邻域结构构成邻域结构集，并通过不断变化邻域结构来扩大搜索空间，以寻得问题(近似)最优解[17]，已在订单接受[18]、车辆路径[19]等诸多组合优化中得到应用，且取得良好的效果。鉴于此，本文提出一种平行动态邻域深度搜索算法，所提算法构建了两种邻域结构集，从而实现对两个初始解在不同邻域结构集内的并行深度搜索；在邻域结构变换过程中设计了动态选择策略，以提高对解改进效果好的邻域结构被选中的概率；在一定迭代周期后，将两个邻域集内的解互换，以实现在不同邻域集内的搜索；若解在多次迭代后仍未改进则对其实施干扰，流程如图2所示。

图2 PDNDS算法流程

3.1 编码与解码

DLBP-II是寻求废旧产品的一个可行拆卸序列，该序列在满足拆卸先后关系约束前提下，实现产品零部件的有序拆卸，以达到最大化拆卸效率等相关目标，属于离散的组合优化问题。在第2.2节符号说明中，每个零件及其对应的拆卸任务被赋予了相应的整数编号，因此，在可行解的编码过程中采用整数排列的编码方式，排列的顺序代表任务的分配顺序。例如整数排列{1, 3, 2, 5, 4, 6,7}表示在产品拆卸过程中首先拆卸任务1，再拆卸任务3，接着按照排列顺序依次对任务进行作业，其满足图1所示任务拆卸优先关系，能将产品所有零件分离下来。

以整数排列{1,3,2,5,4,6,7}为例进行解码，已知工作站数量M=4，假设节拍时间CT=11s，首先将任务1分配至WS1(工作站1)，此时WS1作业时间ST1=10s，空闲时间IT1=11-10=1s；随后分配任务3，由于t3=6s>IT1则需将任务3分配至WS2，此时IT2=5s；继续分配任务2，t2为5s等于IT2，因此可将任务2分配至WS2；然后将任务5分配至WS3；最后将剩余任务4、6、7分配到WS4，解码结束，如图3所示。可求得各工作站总作业时间分别为：10s、11s、9s和14s，实际节拍时间取最长工作站作业时间，即f1=CT=14s，同时可得f2=(14-10)2+(14-11)2+(14-9)2+(14-14)2=50。

图3 解码结果

3.2 初始解生成

分别采用最大直接后继数(GNIS)和最大任务处理时间(LPT)两种启发式方法[21]各生成一个初始解，具体过程如下：

第1步：确定理论节拍时间CT，并从第一个工作站k=1开始分配任务。

第2步：由无前驱及前驱任务已分配的任务构成可选任务集C*。

第3步：若k=M则转至第5步，否则从C*中选则不超过当前工作站空闲时间的任务构成可分配任务集A*。若无可选任务，则启动下一工作站，并重复第3步。

第4步：从A*中根据LPT/GNIS启发式方法，选取作业时间最长的任务/后继任务数最多的任务分配至当前工作站k，然后转至第2步。

第5步：若C*不为空，则从C*中选取一个任务分配至最后一个工作站M，然后转至第2步，否则初始解生成结束。

3.3 局部搜索

PDNDS算法构建两种邻域结构集，实现对两个初始解的并行深度搜索。考虑邻域结构的规模，为每个邻域结构集设计了3种邻域结构，第一个邻域结构集Nk(k=1,2,3)由交换(图4a)、插入(图4b)和交叉(图4c)组成，邻域结构规模相对较小，侧重对解的局部搜索，第二个邻域结构集Nl(l=1,2,3)由逆序(图4d)、多次插入(图4e)和多次交换(图4f)组成，邻域结构规模相对较大，侧重对解的广度搜索。在邻域结构变换过程中采用动态选择策略，即在搜索过程中记录邻域结构Nk对解改进次数INTk，以轮盘赌方法选择邻域结构。当邻域结构被选择后，从该邻域中选择含有n个元素的子集进行局部搜索，步骤如下：

步骤1：确定参数，构造邻域结构集Nk(k=1,2,3)，并设INTk=1(k=1, 2, 3)，初始解为x。

步骤2：扰动，随机选一邻域结构并在该邻域内任意选一解x'。

步骤3：选择邻域结构，根据改进次数以轮盘赌的方法动态选择邻域结构Nk。

步骤4：局部搜索，在解x'邻域Nk(x')中选择n个元素进行局部搜索获得解x"。

步骤5：更新解，若解x"优于x，则x=x"，INTk=INTk+1，然后转至步骤2。

步骤6：重复步骤2-5，直至停止。

图4 邻域结构

3.4 局部干扰

为加快个体跳出局部最优，本文设置扰动阈值。在寻优过程中，若解x经过ut次搜索后仍未改进，则视其已陷入局部最优，将采用变异操作方法进行干扰，如图5所示，新生成的解既包含了当前解的部分优秀序列片段，又有新构建序列片段的注入，以引导个体x快速跳出局部最优。

图5 变异操作

3.5 节拍时间变化策略

DLBP-II的理论最小节拍时间CTlow为工作站平均拆卸时间与任务最长拆卸时间中的大者，CTlow=max{∑ti/M, max{ti|1≤i≤N}}。最优节拍时间的搜索通常是从理论最小节拍时间CTlow开始，令CT=CTlow，如果搜索到的可行解节拍时间CTnow大于当前设置的节拍时间CT，那么在下一次迭代时增加节拍时间CT=CT+1；反之则缩小节拍时间CT=CT-1，这种增加缩小方式节拍时间变化幅度为1，搜索时间复杂度为O(N)，效率较低。鉴于此，所提算法在节拍时间变化过程中采用基于二分法的定界策略，如图6所示，若寻得可行解节拍时间CTnow>CT，则在下一次搜索时令CTlow=CT，CT=(CTnow+CT)/2；若CTnow≤CT，则CTlow不变，CT=(CTlow+CTnow)/2。二分法搜索的时间复杂度为O(logN)，搜索效率较高，能够实现节拍时间向最优节拍时间的快速靠拢。

4 实验结果与分析

为了验证所提PDNDS算法的有效性，采用10个零件的产品拆卸算例(P10)、25个零件的手机拆卸算例(P25)[11]和47个零件的笔记本拆卸算例(P47)进行测试[13]，并与DABC[21]、PSO[9]算法求解以上三个算例的结果进行比较。所有算法均用C++编码，在Corei3-7100 3.9GHz，4G内存电脑上运行，为保证结果的可靠性，P10、P25、P47分别在0.01s、0.5s、2.5s内求解，每个运行30次，求得结果如表1所示。

图6 二分法定界策略

对于小规模算例P10，在不同工作站数量情况下，PDNDS、DABC和PSO三种算法均能搜索到问题的最优解且随着工作站数量的增多，节拍时间呈缩短趋势。当节拍时间一定，工作站数量越多平滑指数越大(如图7所示)，说明工作站的空闲时间增加，拆卸线的平衡效果变差。表2为5个工作站情况下，所得最优拆卸序列任务在拆卸线上的分配。此时，实际节拍时间等于理论最小节拍时间，即最长任务拆卸时间36，且在节拍时间内实现了任务在各工作站上的均衡分配。

图7 P10算例节拍时间和平滑指数随工作站数量变化趋势

对于中规模算例P25，PDNDS求得平均值和标准差均不比DABC和PSO算法差，尤其是当工作站数量为8和9时，PDNDS能够获得更好的求解效果且算法稳定性更好，PDNDS良好的寻优性能在P25算例上开始显现。

对于大规模算例P47，除了工作站数量为9时，PDNDS获得的节拍时间平均值与其他两种算法相等之外，在节拍时间和平滑指数方面，PDNDS所求得的平均值和标准差均好于DABC和PSO，且优势显著。图8为三种算法在不同工作站数量情况下求得节拍时间的对比，可以看出，除了P47(6)、P47(9)，PDNDS搜索到CT的上界与DABC一致外，在其他情况下，PDNDS搜索到CT的上界均小于DABC和PSO，且在算例P47(7)和P47(8)中，PDNDS求得CT的下界也小于DABC和PSO，体现出更强的寻优性能。

图8 三种算法求解P47算例的节拍时间对比

表1 PDNDS、DABC和PSO求解结果对比(AVG为平均值，SD为标准差)

算例工作站数PDNDSDABCPSOf1f2f1f2f1f2AVGSDAVGSDAVGSDAVGSDAVGSDAVGSDP1028101081010810103580130580130580130446011704601170460117053604303604303604306360503036050303605030

续表1 PDNDS、DABC和PSO求解结果对比(AVG为平均值，SD为标准差)

此外，通过表1可以看出，在不同情况下，拆卸线所能达到的平衡效果也不相同，其中P47(4)情况下，PDNDS所得到的最优拆卸序列平滑指数为0，说明在拆卸过程中，每个工作站所分配的任务总作业时间恰好等于节拍时间，各工作站均满负荷运转，此时拆卸线运行效率最高、平衡效果最好。因此，产

表2 P10算例5个工作站数量下的任务分配

品拆卸过程中考虑平滑指数，可实现拆卸任务在工作站上的均衡分配，保证拆卸线高效运行。通过以上对比表明PDNDS算法能够寻找到问题更优解，求解稳定性更高，寻优能力更强，特别是对于中大规模算例，PDNDS算法在求解质量、求解稳定性方面的优越性体现的更加充分。

5 结语

本文针对工作站数量确定情况下的拆卸线平衡问题进行研究，建立以最短节拍时间和均衡工作站空闲时间为目标的第II类拆卸线平衡问题数学模型，并提出一种并行动态邻域深度搜索算法进行求解。所提算法通过构建两种邻域结构集，实现对两个初始解在不同邻域结构集内的并行深度搜索。在节拍时间调整过程中，采用基于二分法的定界策略，实现节拍时间向最优节拍时间的快速靠拢。

对P10、P25、P47三个算例进行求解，验证了本文所提PDNDS算法寻优效果更好。通过优化拆卸方案发现，合理对作业任务进行排序，并平衡任务在各个工作站的分配，能够实现拆卸线节拍时间更短，单位时间内拆卸的废旧产品数量更多，可以充分发挥拆卸线的产能，节约资源。此外，在拆卸过程中，考虑任务的平衡分配可以实现工作站上作业负荷大致相同，从而保证工人作业效率，维持整个拆卸线的稳定运行。