第II类双边拆卸线平衡问题建模与优化

王书伟, 徐国勋, 刘 佳

(1.山东科技大学 经济管理学院,山东 青岛 266590; 2.海南大学 旅游学院,海南 海口 570228; 3.青岛理工大学 商学院,山东 青岛 266520)

0 引言

截至2019年底我国汽车保有量达2.6亿辆，同比增长8.83%，产销量已连续11年蝉联全球第一。我国汽车保有量持续增长的同时，报废量也在大幅增加，对其进行再利用，不仅能实现资源的循环，还能降低对环境危害。拆卸是回收再利用的重要环节，拆卸线平衡问题DLBP在国内外重要期刊均有报道，这些工作大部分是基于精确方法和智能算法，研究拆卸线上作业的均衡分配。

Bentaha等[1]针对拆卸过程作业时间的不确定，以最大化拆卸利润为目标，采用随机动态规划求解部分拆卸DLBP；Altekin[2]针对随机DLBP，提出分段线性规划法。Ilgin等[3]通过线性物理规划解决多产品混流DLBP。DLBP已被证明为NP-complete[4]，其解空间随着问题规模增加呈爆炸式增长，精确方法对大规模问题无力适从，因此更多学者采用智能算法求解DLBP，以在合理时间内得到问题的满意解。Pistolesi等[5]从工作站开启数量、拆卸利润和拆卸危害角度出发，构建DLBP多目标优化模型，提出一种极值多目标遗传算法，以实现对Pareto前沿解的搜索；Zhu等[6]考虑到实际拆卸过程中的潜在安全隐患，评估危害，并设计一种萤火虫算法进行求解；此外，变邻域搜索算法[7]、人工蜂群算法[8]等智能算法也被应用于DLBP的优化。

上述研究均是关于单边DLBP，针对的是小型废旧产品拆卸作业。然而，对于报废汽车等大型产品，单边拆卸会造成工人作业时走动频繁，而采用双边拆卸将工作站分布于传送装置的两侧，两侧工人并行作业，可有效减少移动距离提升拆卸效率。为此，邹宾森等[9]建立以最小化工作站数量、最小化空闲时间和尽早拆除高价值零部件为目标的双边拆卸线平衡问题模型(two-sided DLBP, TDLBP)，并提出一种Pareto蝙蝠算法求解；王书伟等[10]则进一步考虑最小化工位启动数量，以减少工人、设备等作业成本投入；考虑拆卸时作业数量和作业时间的不确定性，Wang等[11]构建了随机TDLBP模型，并设计了离散花朵授粉算法，以优化作业负荷、能耗及利润指标。

以上DLBP的研究都是在给定节拍时间前提下，最小化工作站开启数量以降低固定成本投入，该类问题可定义为第I类问题，而第II类问题则是在工作站数量固定的情况下，最小化节拍时间以最大化拆卸线产能。目前，仅有Bentaha等[12]、王书伟等[13]和Kalaycllar等[14]以工作站作业负荷、利润为目标对第II类单边DLBP(DLBP-II)展开研究。然而，对于报废汽车拆解企业已规划成型的拆卸线，两侧工位数量已确定，为了提高拆卸效率，需最小化节拍时间以在最短周期内完成产品拆卸，因此对第II类TDLBP(TDLBP-II)进行研究符合实际拆卸情况。鉴于此，本文以最短节拍时间、负荷均衡和优先拆除有危害零部件为目标建立TDLBP-II优化模型，并设计了一种变邻域蛙跳算法(shuffled frog leaping algorithm with variable neighborhood search, VNS-SFLA)进行求解。蛙跳算法概念简单、参数少且计算速度快、寻优能力强，在选址问题[16]、车间调度[15]等组合优化问题得到广泛应用。TDLBP-II也属于组合优化问题，因此本文将蛙跳算法应用于该问题求解，并与变邻域算法进行融合，针对问题特点，对算法进行改进，以提升寻优能力。

1 问题描述与数学模型

1.1 问题描述

双边拆卸线如图1所示，左右两侧相对应的两个工位称为一个工作站或成对工位，彼此称对方为伴随工位。在拆卸过程中，由于零部件所处位置不同，作业任务仅能分配到左侧(L)工位、右侧(R)工位或两侧(E)工位均可，这种分配限制称为任务的操作方位约束。

图2为任务优先关系图，用于表示拆卸先后关系，其中圆表示拆卸任务，箭头表示拆卸先后，圆外字母和数字表示任务分配方位和拆卸时间。以图中任务7为例，其与任务6和8存在直接关联，在任务6拆卸完后，任务7才能被分配到右侧工位进行拆卸，作业时间为10秒，而后任务8才能被分配。

1.2 符号设置

问题模型涉及的符号设置如下：

I：为任务集合，一个零件对应一项拆卸任务。

W：为工作站集合。

L：为工位边{0，1}集合，0代表右侧，1代表左侧。

Lt：为分配到左侧工位的任务集合。

Rt：为分配到右侧工位的任务集合。

Et：为分配到左侧或右侧工位均可的任务集合。

ti：为任务i作业时间。

tid：为任务i的等待时间。

STwl:为分配到w工作站中l侧工位的任务拆卸结束时间。

Pi：为任务i直接前驱任务集。

hi：表示零部i的危害性。

PSlk：表示在拆卸线的l侧工位，任务k所分配的拆卸位置；如左侧工位的任务分配序列为{1,3,2,5,9,11}，那么任务5的分配位置PS15为4。

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

swl：为0-1变量，1表示开启，0则表示为开启。

xiwl：为0-1变量，1表示分配，0则表示未分配。

1.3 数学模型

企业在对报废汽车实施拆卸时，需在满足环保要求下最大化拆解线效益，因此所构建问题优化模型如下：

minf1=CT=max{STwl|w∈W,l∈L}

(1)

(2)

(10)

目标函数：式(1)为最小化节拍时间式(2)最小化平衡指数，以将任务在各工位上均衡分配；式(3)为优先拆卸有危害零部件。约束条件：式(4)表示一个任务仅能分配一次；式(5)为拆卸先后关系约束限制；式(6)满足每个工位的任务作业结束时间不能超过节拍时间；式(7)表示每一个工作站至少有一侧工位启动，即没有工作站闲置；式(8)、(9)、(10)表示零部件分配满足操作方位约束。

2 算法设计与实现

蛙跳算法是受青蛙觅食过程启发而演变的一种群智能算法[17]，其结合了文化基因算法和粒子群算法的优点，具备较强的全局搜索能力，已应用于多种组合优化问题，然而也存在过早收敛等不足。本文针对所解决问题特点对算法进行改进，以进一步提高搜索效率，具体描述如下。

2.1 编码与解码

TDLBP-II中存在先后关系和操作方位约束，构建基于一维正负整数排列的编码，排列的顺序表示任务拆卸顺序，排列中各位置上带符号整数表示所分配的任务编号与操作方位(“+”代表右侧工位，“-”代表左侧工位)。例如整数排列S1{-1，+4，-3，-2，+6，-5，-9，+7，+8，-11，+10}表示先将任务1分配至左侧工位，再将任务4分配至右侧，按照排列依次分配，最后将任务10分配至右侧工位拆卸结束，该排列为图2所示产品的一个明确拆卸过程，可表示一个可行解。

由于TDLBP-II的节拍时间未知，且受拆卸优先关系的影响，待分配任务若未分配至其前驱任务所在同侧，则需“等待”其前驱拆卸完毕后分配。因此，在解码时，需首先确定理论节拍时间(最长任务作业时间)，然后对任务进行依次分配，工位最长结束时间为实际节拍时间。以整数排列S1在工作站数量m=3(6个工位)的双边拆卸线上进行解码为例，解码结果如图3所示，右侧第三个工位作业结束时间最长，因此实际节拍时间为25。

2.2 种群初始化阶段

在觅食过程中，若种群中的个体能较广分散在解空间，将大幅提升搜索效率。为了保证初始种群个体的多样性，分别采用优先分配作业时间最长/最短任务的方法生成差异显著的两个个体，剩余个体基于这两个个体随机构造，以扩大个体差异。

2.3 族群划分

种群初始化完毕后，需将个体划分到m个族群中，然后再以族群为单位进行觅食。TDLBP-II中最小节拍时间与平衡指数两个目标之前存在相关性，与危害指数存在冲突，在此将种群中的个体按照字典排序进行评价，并选择一个较好个体依次放入每个族群中，余下个体随机分配。

2.4 局部搜索

蛙跳算法以族群为单位进行觅食，最差个体通过最优个体的引导得以改进。然而，在实际搜索过程中较差个体所代表解也较差，往往不具备搜索潜力。为了提高族群进化速度，采用变邻域搜索(variable neighborhood search, VNS)对族群个体进行局部搜索。VNS是将不同的邻域结构组建成一个邻域结构集，与单一邻域搜索相比，VNS搜索范围更广、能更好地跳出局部最优，搜索过程如图4所示。邻域结构是VNS的核心，在此针对TDLBP-II特点，设计了如图5所示的三种邻域结构。

2.5 个体学习

自然界中的各类种群都会通过对自身的不断调整来提升适应周边环境的能力，以向有利于种群发展的方向进化。蛙跳算法强调族群内部个体间的学习，忽视了个体自主调整的能动性，和族群精英个体间的交流。为此，在族群内部进化完后，组织各族群最优个体进行自学习和相互学习：基于0-1整数的互学习操作和基于优先顺序的0-1整数自学习操作(图6)，从而加强精英个体的相互学习及自我学习，进一步提升精英个体进化速度，与此同时还可有效避免陷入局部最优。

2.6 族群混合与再分

经过一定周期进化后，所有族群将重新混合，然后按照2.3节中所采用方法对个体进行再划分，以实现种群间信息的传递与交流。经过如此往复，保证后代个体有更好的适应度，进而寻得问题最优解。

2.7 节拍时间调整

节拍时间CT是从理论最小节拍时间(最大任务作业时间与平均任务作业时间的大者)开始搜索。在此基于二分法的定界策略，通过不断调整CT的上下界实现快速对最优CT的搜索[12]。若搜索得到的CT大于当前设置的CT，则将CT下界变更为当前设置的CT，并重置CT为搜索得到CT和所设置CT的平均值；反之则下界不变，CT重置为下界CT与搜索得到CT的平均值。该策略可更快实现节拍时间向最优节拍时间的快速靠拢。

3 算法有效性分析

3.1 算例验证

目前尚无TDLBP-II研究算例，但已有单边直线DLBP可以看成是双边拆卸线一侧工位未开启的特殊形式。本节采用P10算例[7](含10个零件)、P25算例[7]和P47算例[8]三个单边拆卸算例对所提算法的有效性进行验证，将三个算例中任务操作方位均设置为右侧工位，任务优先关系、作业时间(取整)和危害性等具体数据请参见对应文献。为了保证测试的有效性，在CPU i3-7100 3.9GHz，4G电脑上，采用C++编码，将P10、P25、P47分别在0.5s、2.5s、5s内求解，每个运行25次，计算平均值(D)和均方差(V)，并与变邻域搜索算法[7]、离散人工蜂群算法[8](DABC)求解进行对比，结果请见表1。

通过表1可以看出，P10算例工作站为2的情况下，三种算法在节拍时间与平衡指数两个目标上的求解结果相同，但所提VNS-SLFA在危害指数方面要好于VNS和DABC两种算法。而在其他不同工作站数量下，三种算法在指定时间内每次均能搜索到问题的最优解。图7为拆卸方案{5,10,6,7,9,4,8,1,2,3}在设有5个工作站(10个工位)的双边拆卸线上的分配情形，该方案节拍时间为36s，拆卸过程所产生的空闲时间最少，任务分配也最均衡。

表1 VNS-SLFA、VNS和DABC求解结果对比

在P25算例工作站设置为6和8的两种情况下，三种算法在各个目标上的结果一致。在剩余三种情形中，三种算法在节拍时间方面求解结果相同，但在工作站为7时，所提算法在平衡指数方面要优于VNS和DABC两种算法，在工作站数量为9、10时，虽三种算法的平衡指数也一致，但在危害指数方面，所提算法要优于其他两种算法。通过对比发现，所提算法在P25算例中整体搜索质量要好于VNS和DABC。另外需要注意的是，在工作站数量为9和10的两种情况下，拆卸线的节拍时间均为18，但在平衡指数方面，工作站为9的情况要明显小于工作站为10的情况，说明当节拍时间一定后，工作站数量越多平衡指数会越大，此时工作站的空闲时间也会增多，拆卸线平衡性变差。

随着问题规模的继续增大，在P47算例中，除了工作站数量为4的情况下，所提算法在危害指数上比VNS算法求解效果要差外，在其余情况所提算法求解结果都要好于其他两种算法，且优势较为明显，体现更好的寻优效果。

3.2 实例分析

本节以大型打印机(含55个零件)为例，进一步验证算法的有效性及说明优化任务在工作站上的分配在企业生产时的重要性。拆卸线设有4个工作站，其中任务6/9/11-15/17/25/31/33-35/37-38/43/45-46/51/53-54操作方位为右侧工位，任务3/19/28/49为左右两侧工位均可，剩余任务为左侧工位，任务拆卸优先关系请参见文献[18]。将算法迭代时间设为200s，所得最好拆卸方案如图8所示。

通过图8可以看出，零部件在双边拆卸线上进行作业时，第一个工作站的左侧工位作业结束时间91s为所有工位中最长作业结束时间，则设为拆卸线节拍时间。总空闲时间为每个工位上的空闲时间和：0+2+0+13+1+13+0+13=42s。在整个作业过程中仅在拆卸零件9时产生了1次等待，时间为9s。通过该方案实施产品拆卸，拆卸线空闲时间与等待时间较少，任务分配相对平衡，在很大程度上避免了工人和机器，在拆卸过程中处于“无事可做”的状态，保证了拆卸效率，提高了拆卸线产能。

4 结论

本文对工作站数量固定的双边拆卸线平衡问题展开研究，建立问题数学模型，然后采用变邻域蛙跳算法求解。通过对不同算例测试表明，相较于VNS和DABC两种算法，所提VNS-SFLA具有更好的寻优效果。对实例产品拆卸过程进行分析表明优化任务在拆卸线上的分配，使任务尽可能均衡在各工位上分配，能够减少拆卸等待时间和闲置时间，缩短节拍时间，最大化拆卸线产能。

此外，需特别指出的是当双边拆卸线只开启一侧工位时，可看成是单边拆卸，因此单边拆卸可以看成是双边拆卸的特殊形式，所以本文所构建的第II类双边DLBP优化模型也可适用于第II类单边DLBP。也正因为此，本文所设计的变邻域蛙跳算法不仅能用于TDLBP-II的寻优，也可应用于DLBP-II的求解，在对算法进行适当的调整还可用于其他类型DLBP的优化。另外，本文所提出编码方式、种群初始化策略、邻域结构可为其他启发式算法求解提供借鉴。但本文研究的TDLBP-II是对废旧产品完全拆卸，未考虑因零部件损坏导致拆卸中断现象的发生以及拆卸线的再平衡，因此，针对产品不完全拆卸与拆卸线再平衡的研究是后续工作的方向。