求解双边装配线第I类平衡问题的改进离散蝙蝠算法*

詹慧文，罗亚波

(武汉理工大学 机电工程学院，武汉 430070)

0 引言

双边装配线常用于汽车、装载机等大型产品的装配，与单边装配线相比，具有缩短装配线长度，提高工装、夹具的利用率，降低物流成本等优点。装配线平衡问题按照研究目的可分为两类：①最小化工位数[1]；②最小化生产节拍[2]。1993年，Bartholdi[3]首次提出双边装配线平衡问题，并提出一种基于先分配原则的启发式平衡算法。由于TALBP-I复杂的NP属性，启发式方法可以快速找到问题的近似解，然而任何一种启发式规则都有一定的偏好，可能对某类问题求解效果比较好[4]，具有一定的适用性。2000年，Kim等[5]提出一种基于工位编码的遗传算法，但提出的关键位阶权重启发式解码方法使算法无法搜索到部分可行解空间。2007年，针对Kim提出的遗传算法的缺陷，吴尔飞[6]提出基于序列组合的编码方法，设计了相应的交叉与变异算子，使搜索过程仅在可行解空间内进行，提高了搜索效率。2008年，Baykasoglu等[7]首次应用蚁群算法求解TALBP-I，并首次引入区域约束，使研究更贴近生产实践情况。2014年李大双等[8]研究了基于Pareto机制的多目标随机型TALBP-I，为TALBP-I的研究提供了新思路。2016年，李梓响等[9]研究了TALBP-I的解码策略，提出了工位-操作融合的解码策略，改进了以往的操作-工位解码策略。

目前遗传算法、蚁群算法、模拟退火算法等被广泛用于双边装配线平衡问题中，但是Yang[10]于2010年提出的蝙蝠算法，相比遗传算法等具有易实现、寻优精度高、鲁棒性好等优点，但目前还未见其在双边装配线平衡问题方面应用的报道。基本蝙蝠算法求解离散问题具有局限性[11]，需要对其改进，才能够应用于TALBP-I。针对TALBP-I，本文设计了一种改进离散蝙蝠算法，并与其它文献结果对比，验证算法的有效性。

1 双边装配线平衡问题

1.1 问题描述

双边装配线将生产线分为左右两边，两边都可以作业，一对左右对称分布的工位被称为成对工位，成对工位中的任一工位被称为另一工位的伴随工位。双边装配线工位布置如图1所示。

由于双边装配线的布局特点，有些任务适合左边(L)操作，有些任务适合右边(R)操作，有些可以在任意一边(E)操作，此为操作方位约束。任务彼此间存在优先关系，此为优先约束。图2是算例P9[5]的任务优先关系图，圆圈内数字表示任务编号，(*，*)分别表示任务的加工时间和方位。

单边装配线上各工位工人之间作业相互独立，工位负载等于所有分配在该工位上的任务操作时间总和。但是，双边装配线由于存在成对工位，左右工位任务之间存在优先关系，可能会产生因序列相关而造成的等待时间，具体情况以图3为例说明。图3是P9问题第一个成对工位的一个可能布置方案。

图2 P9任务优先关系图

图3 P9问题第一个成对工位任务分配图

右边工位的任务6因左边工位内的任务3和它存在优先关系，所以任务6必须等待任务3完成才可以开始装配，图3中的剖面线部分就是因序列相关而产生的1个单位的等待时间。工位节拍为5，左边工位已分配不下任何其它任务，所以末端产生了1个单位的空闲时间，如图中网格线部分所示。

1.2 启发式目标函数

TALBP-I常见的优化目标为同时最小化成对工位数和最小化总工位数[6-7]，即：

minf1=wnm·nm+wns·ns

(1)

式中，nm和ns分别为装配线使用的成对工位数和启用的总工位数，wnm和wns为相应的权值，一般根据成对工位数和总工位数的比值，设为2和1。为了在工位相同时筛选出较优解，提出如下启发式二级目标：

(2)

式中，j、J分别为成对工位编号和成对工位集，k为操作方位，CT为节拍，STjk为分配到工位(j,k)上的操作时间，(CT-STjk)为该工位的空闲时间。该目标倾向于保留前面工位空闲时间更少的方案。如果前面工位的空闲时间少，留下的操作会随之减少，需要的工位数量也可能会更少。TALBP-I的其他基本约束的数学模型描述可参考文献[3]。

2 改进蝙蝠算法

2.1 基本蝙蝠算法

fi=fmin+(fmax-fmin)·β

(3)

(4)

(5)

上述公式是针对全局搜索方式的，为提高算法性能，蝙蝠算法设计了如下局部搜索方式：

(6)

随着迭代过程的进行，响度会逐渐降低，脉冲频度会提高，迭代过程可用公式(7)、式(8)模拟。

(7)

(8)

2.2 编码策略：双重编码

TALBP-I的优先关系图是一个有向无环图，任务分配活动可以用AOV网[12](Activity On Vertex)描述，求TALBP-I最优解就是求AOV网的最优拓扑排序。蝙蝠算法中蝙蝠位置对应问题的解，对于TALBP-I，将蝙蝠位置对应的解定义成一个n×n的拓扑排序矩阵[13]：

(9)

(10)

式(10)是P9问题的一种可能拓扑排序矩阵，式(10)可以推出它的拓扑排序为3 2 1 6 4 5 9 8 7。

(11)

(12)

(13)

第1列开始，依次重新构造拓扑排序矩阵，任务j被分配到c列的概率为：

(14)

2.3 工位-操作解码方法

TALBP-I目前广泛应用的解码方法是“操作-工位”，即首先选择一个操作，然后选择工位分配操作[7]。但是这种解码容易导致成对工位的两边负载不均衡，李梓响[9]于2016年提出一种基于“工位-操作”的新解码方法。其主要思想就是首先选择余量更大的边作为当前工位，然后优先选择不产生等待时间的操作进行分配。实验表明该种策略能提高解码效果，较为显著地降低工位数。

2.4 改进的局部搜索机制：变邻域搜索

基本蝙蝠算法和其他智能算法一样，同样存在后期搜索速度慢，易陷入局部最优等问题[11]，主要原因还是邻域结构太过单一，对于TALBP-I这样的组合优化问题，搜索易陷入停滞。为了扩大BA的邻域搜索空间，本文设计了4种插入算子，产生邻域解集，4种插入算子如图4所示。4种算子按照变邻域方式搜索，即先用单次插入算子对最优任务序列做轻微扰动，当单次插入算子不能获得更好解时采用多次插入算子，再对任务序列做较大范围扰动。

图4 4种插入算子

2.5 算法步骤

所提IDBA算法采用随机初始化方法产生初始种群，利用双重编码映射机制实现蝙蝠实际位置到拓扑序列映射，采用“工位-操作”方法生产解码方案，局部搜索采用变邻域搜索方式，算法基本流程如图5所示。

3 基于标杆算例的比对实验

图5 DBA算法流程图

表1 算法完整名称及简写

从表2可以看出，对于标杆算例，只有IDBA和DABC能找到所有问题的最优解。各算法求解结果显示，GA、ACO求解性能较差，SA较好些，DABC、IDBA均比GA多找到4个更优解，比ACO多找到3个更优解，比SA多找到一个更优解。DABC是对比算法中求解TALBP-I性能最好的算法，但是DABC算法过程过于复杂。算法首先要利用分级位置权的启发式方法生成初始种群，算法对初始解的质量有较强依赖。算法寻优过程包含雇佣蜂阶段，观察蜂阶段，探测蜂阶段，每一个阶段都要设计相应的算子。IDBA算法虽然和DABC算法获得的最优解相同，但IDBA算法寻优过程简单，整个过程不产生非法解，不需要二叉树调整算法[8]重新调整任务序列。与未采用变邻域搜索方式的DBA相比，改进后IDBA算法性能更好。如对于P205(CT=1133)这种装配线平衡问题中的“难解”问题[6]，采用变邻域搜索的IDBA找到了21个工位数的最优解，比DBA少了一个工位数，事实上对于P205(CT=1133)问题，所有算法中只有IDBA和DABC算法能找到该问题的最优解。另外从DBA、IDBA的10次运行结果可以看出，IDBA比DBA运行结果更稳定，证明IDBA搜索域更广，在搜索过程中可以很好的保持种群的多样性。

表2 算法对比结果

4 结论

本文针对TALBP-I所具有的离散性、序列相关性等特征，采用双重编码机制，使基本蝙蝠算法可以解决离散问题，扩展了蝙蝠算法的应用范围。所提改进蝙蝠算法为了避免搜索过程陷入局部最优，设计了四种插入算子，进行变邻域搜索，改进了蝙蝠算法单一的局部搜索方式。基于标杆问题的对比实验验证了所提算法求解TALBP-I的有效性和优越性，为解决TALBP-I提供了新方法。然而本文只研究了基础的TALBP-I，未来复杂约束耦合的TALBP-I和第II类平衡问题将是下一步的研究内容。