基于蜂群算法的双边装配线平衡问题研究

熊 晶 段晓坤

(常州信息职业技术学院 智能装备学院，江苏 常州213164）

0 引言

在汽车、装载机等产品的装配过程中，由于装配区域较大，能够在双侧同时进行装配工作，因此双边装配线在大型产品的装配过程中得到了广泛的应用。相比于单边装配线，双边装配线能够缩短装配线长度、减少物料搬运、工人移动和减少工具成本等优点[1]。

双边装配线操作任务的分配不仅要满足单边装配线的基本分配约束要求，如任务时间约束、优先顺序约束、时间结束约束和节拍时间约束等；同时，要满足特有的操作方位约束和不同操作方位对先序任务的装配约束等要求[2]，因此，双边装配线平衡问题更复杂，更难得到精确的最优分配方案。鉴于双边装配线平衡问题的实际应用价值，越来越多的研究人员对该问题进行了深入研究。

文献[3-5]针对双边装配线平衡问题的不同优化目标，如最大化任务相关性和最小化工作载荷、最小化工位数量和多目标优化等，提供和改进了启发式方法、遗传算法、粒子群算法和蚁群算法等多种群体智能算法。但对于双边装配线在应用中存在的位置约束、区域约束和同步约束等实际分配约束问题研究较少。

本文为解决以上实际约束问题，针对双边装配线任务分配的特点，设计了一种解码方法解决多重约束的赋值问题，并结合延迟爬山算法对蜂群算法进行改进，加快了求解过程的收敛速度和求解精度。

1 双边装配线平衡问题

1.1 双边装配线

双边装配线在产品装配过程中，由于左右两侧同时进行装配工作，装配线划分为左右两个装配区域。左右两个并行的工位称为伴随工位，如工位1和工位2，工位2n-1和工位2n，如图1所示。考虑到产品的功能要求，存在只能在产品左侧或者右侧进行装配的零部件，此类操作任务具有操作方位约束，称为左侧任务（L型）和右侧任务（R型）。在装配线左右两侧均可进行操作的任务称为双侧任务（E型）。

双边装配线的所有操作任务分配时，须遵循以下基本原则：每个任务必须分配到唯一的工位上；同一工位上所有任务的结束时间不能超过装配节拍时间；所有任务的分配须遵循优先顺序约束，即该任务的所有先序任务完成后才能进行该任务的操作。由于优先顺序约束的原因，每个工位上都可能产生空闲时间，如图1的阴影部分。

图1 双边装配线

双边装配线平衡问题可以通过先序关系图表示，如图2所示。图中圆圈内的数字表示任务号，圆圈上方括号内的数字表示该任务的操作时长，字母表示该任务的操作方位约束（该任务需要在伴随工位的哪一侧进行）。圆圈之间的箭头表示任务的相互顺序约束。例如，任务7需要在任务4和5完成后才能，（3，E）表示任务7其操作时长为3，可以分配到左侧或右侧工位进行操作。同理L表示任务需要分配到左侧工位，R表示任务需要分配到右侧工位。

图2 双边装配线先序关系图

1.2 第一类双边装配线平衡问题的数学模型

本文研究第Ⅰ类装配装配线平衡问题：已知装配线的生产节拍，在满足任务分配约束的前提下，将所有任务分配到装配线的各个工位中，并最小化装配线长度。其数学模型如下：

设I为任务集，I={1，2，…，I，…，n}；J为伴随工位集，J={1，2，…，j，…，m}；k为伴随工位方位，k=1表示左侧工位，k=2表示右侧工位；SL、SR、SE分别为左侧、右侧和双侧任务；P0表示无先序任务的任务集合；P（i）为任务i的紧邻先序任务集合；Pa（i）为任务i的所有先序任务集合；S（i）为任务i的紧邻后序任务集合；Sa（i）为任务i的所有后序任务集合；ti为任务i的操作时长；fti为任务i的结束时间；Nm为开启的伴随工位总数；Ns为开启的工位总数。

约束条件为：

（5）位置约束（任务i必须分配到指定工位）：

（6）区域约束：

积极区域约束（任务i，h必须分配到同一工位）：

消极区域约束（任务i，h不能分配到同一工位）：

（7）同步约束：（任务i，h必须分配到同一伴随工位且操作开始时间必须相同）：

2 针对双边装配线平衡的混合蜂群算法

蜂群算法中，每一个蜜源代表问题的每一个可行解。雇佣蜂搜索蜜源并将信息分享给跟随蜂；跟随蜂根据适应度在所有的蜜源中选择一个并进行深度挖掘，以寻找更优的可行解；侦察蜂利用随机策略寻找新的蜜源，增加可行解的多样性。通过有限次的搜索迭代，收敛得到最优解，即最佳分配方案。

2.1 编码

在混合蜂群算法中，将双边装配线满足所有分配约束的任务排序编码为一个字符串的排列序列。根据随机原则产生一个1~n（整数）的权重字符串，n为任务个数，数字k在该序列中的位置顺序i表示任务i按顺序第k次分配该任务。例如包含12个任务的双边装配线，随机产生的字符串为{2，5，3，7，6，1，12，9，8，11，4，10}，任务6的权重值为1，表示该任务是左右任务中最优先分配的。所有任务的分配顺序依次为6—1—3—11—2—5—4—9—8—12—10—7。

2.2 解码

显而易见，上述编码序列无法表示任务与分配工位间的关系，而且这种分配序列可能不遵循优先顺序约束。因此，需要一种解码方案将该序列编译为符合分配约束的可行解。

解码时，采用任务侯选集的方法，将满足节拍约束和优先顺序约束的所有任务放到侯选集中。在任务集中，选择一个任务，如果满足节拍约束、区域约束和同步约束，则该任务根据位置约束分配到相应的工位；否则删除该候选任务及其候选任务，再候选集中选择其他候选任务，并检查是否满足分配约束。当任务集中的所有任务分配均已分配完毕，则开启新的伴随工位并更新候选任务集。

解码过程中，E型任务优先分配到最早开始操作的一侧工位。如果开始时间相同，则将E型任务分配到伴随工位的左侧工位。

所有任务分配完毕后，检查最后一个伴随工位的任务是否均为L型和E型任务或者R型和E型任务。如果符合该条件，在满足其他分配约束的基础上，将该伴随工位的所有任务分配到同一侧工位中，减少工位的开启数量。

2.3 雇佣蜂策略

延迟爬山算法是一种具有迭代过程和后期接受策略的高效局部搜索算法。该算法在初始解的基础上，通过邻域结构对其进行迭代改进，从而加快收敛速度。

在搜索可行解阶段，每个雇佣蜂随机选择一个现存的可行解。为了寻找更好可行解或者潜在的更好的可行解并保持种群的多样性，雇佣蜂采用四种邻域结构（交换算子、插入算子、多交换算子和多插入算子）进行迭代更新。雇佣蜂在四个邻近结构中随机选择一个产生新的可行解。如果新的可行解优于现行解，则更新为现行解，否则仍保持原来的可行解。

2.4 跟随蜂策略

当雇佣蜂得到新的可行解并更新种群后，跟随蜂在此基础上使用二进制锦标赛选择策略在新种群中选择现行解。为了挖掘更好的可行解，跟随蜂采用多交换操作和多插入操作的变邻域结构的延迟爬山算法进行迭代更新现行解。变邻域结构是指当多插入操作邻域结构对最佳可行解没有改进时，使用多交换操作邻域结构。

如果采用贪婪策略决定跟随蜂得到的新可行解是否更新为现行解，可能会错过新解继续迭代而产生的更优解。因此，将新可行解与现种群中的最差解进行对比，如果新可行解优于最差解，则将最差解进行替换，否则舍弃新可行解。通过这种方式，跟随蜂可以将种群导向搜索空间中最有得到最优解的区域。

2.5 侦查蜂策略

如果一个可行解经过多次迭代后，仍没有得到更新改进，则相应的雇佣蜂转变为侦查蜂并放弃该现行解。如果侦查蜂利用随机原则产生一个新的可行解，那么随机解很可能是一个较差的解，它无法为种群迭代更新提供更好的信息，这种策略可能会降低搜索效率。因此，为了找到新的更好的解，避免陷入局部最优，侦察蜂对现种群中的一个随机解进行多次邻域搜索，产生的解作为新的可行解。

3 工程实例应用

3.1 工程实例

随着精益生产的推入，某公司对双边装配线进行重新规划设计，以期达到改善生产现状，提高产能的目的。经实际调研，该公司的双边装配线包括65项操作任务，各任务的先序关系图，如图3所示。由于产品的工艺复杂性，65项任务之间存在位置约束、区域约束和同步约束等分配约束条件。具体为：位置约束{任务，（伴随工位，工位）}：{8，12，（3，2）}{9，10，（3，1）}、{16，17，（4，1）}{55，56，（4，2）}，积极区域约束{任务…任务}：{3，23，24}{31，32}{36，37}；消极区域约束：{10，30}{46，56}；同步约束{任务，任务}：{9，12}{51，52}。

图3 65项任务先序关系图

3.2 算法参数设计

为更好地优化双边装配线，得到更好的分配方案，本文的混合蜂群算法参数设置为：

蜂群数量Np=100，其中雇佣蜂、跟随蜂和侦查蜂的数量分别为50、50和1；可行解最大更新迭代次数为limit=20；延迟爬山算法中可行解最多为20个；算法的终止条件为CPU计算时间Ts=n×n×15 ms，其中n=65。

3.3 计算结果

考虑新装配线规划设计过程中的工艺问题、生产实际条件，以及产品装配过程中的位置约束、区域约束和同步约束等分配约束条件，该双边装配线可以有5种设计方案。在装配节拍CT=325时，能够求解得到的最优解为9[17]，即开启9个伴随工位，17个工位。当生产节拍CT=380、435、490、545时，能够求解得到的最优解分别为8[15]、7[13]、6[11]、6[11]。

结合生产区域面积、工人数量、生产效率以及订单量的实际需求，最终的双边装配线设计选用CT=490，开启6个伴随工位，11个工位的分配方案。此方案的具体任务分配甘特图，如图4所示。

图4 65项任务分配方案甘特图

图中，X轴表示操作时间，Y轴表示伴随工位和工位，“1L”表示伴随工位1的左侧工位。矩形框中的数字表示任务序号，矩形框的顺序表示该工位中各任务的优先顺序。例如“6R”工位中的任务分配顺序为：35—54—50—61—65。深色的矩形框表示具有位置约束、区域约束或同步约束的任务，如同步约束任务{51，52}。

矩形框右上侧的数字表示该任务的操作结束时间，最后一个任务的结束时间为该工位的操作时间。例如任务65的结束时间为471，表示“6R”工位的操作时间为471。所有工位的最大操作时间为装配节拍时间，例如该方案的最大节拍为CT=489。

4 结语

本文针对双边装配线平衡问题中存在的实际应用约束，如位置约束、区域约束和同步约束等，提出了一种结合延迟爬山局部搜索策略的混合蜂群算法。该算法中针对双边装配线任务分配的特点，设计了一种解码方法解决多重约束的赋值问题。搜索求解过程，雇佣蜂使用四种邻域结构探索新的可行解，跟随蜂使用变邻域结构的延迟爬山算法挖掘更优的可行解。应用混合蜂群算法求解双边装配线工程实例，得到了装配线平衡的最优解，验证了该模型与算法对求解装配线平衡问题有实际意义。