改进迭代局部搜索算法求解第Ⅰ类混流双边装配线平衡问题

唐秋华，饶 迪,李梓响,张利平

(武汉科技大学 机械自动化学院，湖北 武汉 430081)

0 引言

双边装配线是进行大批量生产或定制生产经常采用的一种重要生产方式。为了满足客户对产品个性化和多样化的需求，经常需要在双边装配线上同时对多种不同类型的产品进行生产，即混流双边装配。混流双边装配通过在同一条装配线上混合连续地生产不同的产品，不但能够提高装配线的生产效率[1]、减少在制品数量、均衡物料消耗速度，而且能够增强装配线的灵活性及适应性。

当前对双边装配线的研究主要集中于单模型双边装配线平衡问题[2-4]，对多模型的混流双边装配线平衡研究相对较少。2009年，Özcan等[5]首次建立了混流双边装配线平衡问题的混合整数规划模型，同时提出模拟退火算法对该问题的大规模案例进行求解;2012年，Chutima等[6]针对多目标混流双边装配线平衡问题，提出有负知识的粒子群算法进行求解。上述研究均采用联合优先关系图，将多类型产品的混流双边装配线转化为单模型双边装配线进行求解，该方法只能实现双边装配线上各工位的负载总量均衡，不能实现各工位间瞬时负载的平衡，因此会使双边混流装配线上出现等待和阻塞，大大降低装配线的效率。为保证各产品混流双边装配的平衡，Delice等[7]和Yuan等[8]通过限制每个产品类型在每个工位的总操作时间小于等于节拍，实现了各产品类型在各个工位的负载均衡。

针对多产品混流双边装配的平衡问题，目前的研究方向如下：

(1)关于解码方法。在进行双边装配线平衡时，由于某些任务的操作方向既可分配到左边又可分配到右边，导致了多种可行的解码方式。李梓响等[9]针对单模型双边装配线，设计并对比了多种解码，实验结果验证了不同解码对算法性能的影响很大，但是该研究并不能直接应用于求解混流双边装配线平衡问题。

(2)混流双边装配线的研究往往以最小化工位数量为目标，但在优化时常得到若干目标值相同而具体分配方案不同的解，需要对这些目标值相同的多个不同解进一步细分，找出综合属性更优的解，以引导算法进化的趋势。

(3)针对多产品混流双边装配平衡问题，目前的主要求解方法是群智能算法，如Delice等[7]提出的改进粒子群算法、Yuan等[8]提出的混合蜜蜂交配优化算法。与群智能算法相比，局部优化算法更关注问题特征、所用的参数更少、求解更快捷，但是目前还未见局部优化算法在该问题上的应用。

本文对第Ⅰ类混流双边装配线平衡问题的解码方式进行了深入研究，以期获得一种或多种有效的解码策略；研究迭代局部搜索算法，通过启发式初始化、多种邻域结构设计等手段，提高初始解质量、拓展邻域搜索空间。实验结果表明，所提算法与解码方法在求解第Ⅰ类混流双边装配线平衡问题上具有可行性和有效性。

1 第Ⅰ类混流双边装配线平衡问题

1.1 问题阐述

本文所研究的第Ⅰ类混流双边装配线平衡问题可描述为：在计划期内，多种不同产品在同一条双边装配线上进行装配，由于不同产品的工艺要求不同，每种产品所包含的任务都存在优先关系约束。根据任务的优先关系，将混合生产上多种产品的所有任务合理地分配到各个工位，且每种产品在各个工位上的操作时间满足节拍约束，以实现某些优化目标。

任务间的优先关系约束可用任务优先关系图进行描述，所有产品的优先关系图合并成一个联合优先关系图，如图1所示。图中的9个任务分别用圆圈里的数字表示，圆圈上方圆括号里的数字和字母分别表示任务的操作时间和任务的操作方向(L表示左边，R表示右边，E表示任意方向)，圆圈之间的箭头表示任务之间的优先顺序关系。不同产品同一任务的属性相同或者相似，例如图1中两种产品的任务2的操作时间不同，但操作方向肯定相同。需要说明的是，当一种产品不包含某个任务时，该任务的操作时间默认为零。基于上述属性，可得到图1c所示的产品A和产品B的联合优先关系图，该图包括2种产品的全部9个任务。

目前对混流双边装配线上任务的操作时间处理方式主要分为加权方式和非加权方式两类。时间加权是按照各种产品的投产比例，对操作时间进行加权，将多模型混流双边装配线平衡问题转化为单模型双边装配线平衡问题，实现了混流双边装配线上各工位的负载总量均衡;时间非加权的方式要求每种产品的每个任务满足节拍约束，更强调每种产品在各个工位的负载总量小于节拍，实现了混流双边装配线上每种产品在各工位的负载平衡。由于采用加权方式后所有求解单模型双边装配线的算法均可以直接求解混流双边装配线平衡问题，本文采用非加权方式。图2所示为非加权方式下图1中2种产品的平衡分配方案。

在图2中，工位1和工位2左右对称，因此称为成对工位，它们互称对方为自己的伴随工位。A和B为混流双边装配线上生产的两种产品，且其操作分别用斜线和网格线表示，除斜线和网格线外的阴影区域表示因任务优先关系引起的工位空闲时间，实际上，这类空闲时间是不可避免的。例如，产品B的任务7和任务9被分配到同一个成对工位的左边工位，由于任务5是任务7的直接前序，任务7必须在任务5完成后才能进行操作。

1.2 改进二级目标

第Ⅰ类混流双边装配线平衡问题就是给定生产节拍，在满足约束条件下最小化成对工位数量和总工位数量，即

minobj1=wnm×nm+wnm×ns。

(1)

式中：obj1表示一级目标;nm和ns表示成对工位数和总工位数;wnm和wns表示对应的加权系数,一般设wnm的值大于wns，参照文献[10]，将wnm和wns设置为2和1。

在实际算法优化过程中，往往存在多个具备相同工位的解，为方便筛选出较优的解，可使用如下二级目标进行区分：

minobj2=

(2)

2 双边混装平衡解码方法

第Ⅰ类混流双边装配平衡问题为在限定生产节拍的前提下，尽量减少总工位数量，因此常采用基于优先级的编码方式[5,8]。该方式首先随机生成一组包含所有操作的序列，如{1,4,2,3,5,7,8,6,9},该序列长度等于任务数，序列中各位置上的取值表示操作序号。序列中优先分配位置靠前的操作，如上例中操作1优先分配，依次是操作4、操作2、操作3等。

为获得一个可行解，还需在上述操作序列基础上采用特定解码方式进行解码。目前针对第Ⅰ类混流双边装配线平衡问题的解码方法有解码方式1[8]和解码方式2[5]，其主要思想是先选择一个操作，然后选择工位对操作进行分配，最后进行成对工位的调整。该解码方式会使成对工位的两边出现负载不均衡的情况。为更好地求解第Ⅰ类混流双边装配线平衡问题，在上述解码方法基础上提出两种解码方法，下文依次对基于操作的解码方法和基于工位的解码方法进行详细介绍。

2.1 基于操作的解码方法

基于操作的解码方法首先选择序列中位置靠前的操作进行分配，若该操作只能分配到左边或右边，则直接分配；若操作可分配到左右两边，则选择可最早开始加工的那一边作为分配任务的边；若操作可分配到左右两边且两边余量相同，则随机选择一边作为分配操作的边。最后进行成对工位调整。为方便后续实验，将该方法称作解码方式3，其流程如图3所示。

当所有操作分配完后，如果满足以下条件，则将最后成对工位上的所有操作调整到一个工位中：①最后成对工位两边均分配有操作；②最后成对工位上各个操作的操作方向非互斥，即其方向均为任意一边，或者任意一边和左边，或者任意一边和右边；③最后成对工位上所有操作的操作时间之和不大于节拍。进行上述最后成对工位调整的价值，是在不改变成对工位数量的前提下减少一个工位。

2.2 基于工位的解码方法

基于工位的解码方法首先判断左右两边能否分配任务，即左右两边的候选操作集是否非空，若只有一边能够分配操作，则选择该边作为分配操作的工位;若两边都能分配，则选择余量较多的边作为分配操作的边,或者在余量相同时随机选择一边。当工位选定以后，采用不同的策略对操作进行分配，首先判断候选操作集中是否存在不产生序列相关空闲时间的操作，如果存在，则从不产生序列相关空闲时间的候选操作集中选取操作序列中位置靠前的操作进行分配；如果不存在，则选择操作序列中位置靠前的操作进行分配，然后进行成对工位调整。为后续实验方便，将该方法称为解码方式4，其具体流程如图4所示。

与目前用于求解第Ⅰ类双边装配线平衡问题的两种解码方法相比，所提出的基于操作或工位的解码方法更加关注同一成对工位内左右两边工位的负载均衡，也更大程度地避免了空闲时间的产生。所提两种解码方法的差异在于：改进的基于工位的解码首先利用工位选择策略选择余量较多的边作为分配操作的边，使左右两边工位负载均衡；然后采用操作选择策略优先分配不产生序列相关空闲时间的操作，减少工位上由序列相关导致的空闲时间。

3 改进迭代局部搜索算法

迭代局部搜索(Iterated Local Search, ILS)算法被广泛应用于各个优化领域[11-13]，并获得了不错的效果。ILS算法是一种元启发式算法，该算法通过局部搜索和扰动两种机制使算法具有较好的全局搜索能力，能够有效提高算法的求解效率。改进ILS算法由解的初始化、局部搜索、扰动3部分组成。解的初始化给算法的执行一个起点S0；局部搜索是从初始解S0或某个中间解S′出发，快速搜索其邻域中的局部最优解；扰动通过不断变换局部搜索在解空间的领域达到跳出局部最优的目的。ILS算法的全局搜索能力依赖于扰动，因此在算法设计时应避免扰动抵消局部搜索的作用。

3.1 启发式初始化

为了提高初始解的质量和加快搜索效率，提出改进NEH(Nawaz-Enscore-Ham)[14]启发式初始化，其主要思想是：首先根据分级位置权(Ranked Positional Weight, RPW)[15]对各个操作赋予对应的初始优先权值，然后按照优先权值的大小对操作进行排序，最后对排序的操作进行一定调整得到可行的操作序列。启发式初始化的流程如图5所示。

3.2 改进局部搜索

局部搜索在ILS性能实现过程中扮演了重要的角色，本文通过设计插入算子来改进局部搜索。改进局部搜索将1个操作从当前满足优先关系约束的操作序列中移出，插入到该操作序列中其他b个不同的位置，构成关于该操作的插入变换领域。若b次插入获得的新解优于当前解，则用新解替代当前解，反之保留当前解。该方法能有效减少重复插入导致的算法求解时间的浪费，加快搜索速度。改进局部搜索的复杂度为O(a×b×n)，搜索流程如图6所示。

3.3 扰动

为了避免陷入局部最优，实现全局搜索的目的，扰动用来不断改变当前局部最优解。将扰动对当前解局部最优解随机重复插入Parameterd次，选择其中最优的一个邻域解作为新解。由于得到的新解不一定比当前解局部最优解好，为了保证新解的质量，产生了Parametermu个新解，选择最优新解代替当前局部最优解。

3.4 算法流程

在改进ILS算法中，启发式初始化能够提高初始解的质量，加快搜索速度；改进的局部搜索能够快速求得当前解邻域中的局部最优解；扰动通过在解空间不断变换解的位置来改变局部搜索求得最优解，避免陷入局部最优，使算法具有较好的全局搜索能力。改进ILS算法的流程如图7所示。

4 实验结果与分析

为了验证基于工位的解码方法和改进ILS算法在求解第Ⅰ类混流双边装配线平衡问题上的有效性，本文分别设计了2组对比实验,即解码性能对比、改进ILS算法与7种常见智能算法对比。运用Microsoft Visual C++语言进行编程，在2.50 GHz Intel(R)Core(TM)、4 GB内存个人计算机上运行，对第Ⅰ类混流双边装配平衡问题的所有案例进行求解，其中小规模案例为P9,P12,P16,P24四组，大规模问题为P65,P148,P205三组。

4.1 解码对比

为了验证本文所提出的基于工位的解码方法的优越性，对上述4种解码方法进行了对比。为保证解码方法对比结果的公平性和普适性，所有的解码方法都使用改进ILS算法进行对比，并对大规模问题P65,P148,P205的所有案例进行求解。采用相对百分率偏差RPD比较不同解码方法获得解的质量，具体计算为

RelativePercentageDeviation(RPD)=

(3)

式中：Somesol表示任意一种解码方法获得的工位数，Best表示所有解码方法中的最优工位数。同时，为了对比不同解码方法的优越性，使用方差分析(ANalysis of VAriance，ANOVA)统计分析不同解码方法的质量。在95%最小显著差数间隔的置信水平下，4种解码方式的平均值如图8所示，其中:decoding1为解码方式1[8]、decoding2为解码方式2[5]、decoding3为解码方式3(即基于操作的解码方式)、decoding4为解码方式4(即基于工位的解码方式)。由图8可见，decoding4的性能最优，decoding1的性能次之，decoding2的性能最差，从而证明了所提出的基于工位的解码方法优于所有对比的解码方法。

4.2 参数校验

本文通过多因素ANOVA选择改进迭代局部算法的最优参数组合。该算法有4个参数需要确定，即局部搜索的a和b以及扰动的Parameterd和Parametermu。全因素设计如下：①a设置3个水平，即10，20，40；②b设置4个水平，即1，2，3，4；③Parameterd设置4个水平，即4，8，12，16；④Parametermu设置4个水平，即100，150，200，300。

为保证参数选择的合理性，对大规模问题P205的所有案例进行求解，每个案例求解5次，然后取平均值。由于问题规模不同，将算法的终止条件设置为运行时间t=n×n×ρms，其中n为任务数量，ρ取值10。实验结果中，b和Parameterd的P值均小于5%，即均存在显著差异；a和Parametermu的P值均大于5%，即均不存在显著差异。各参数的校验结果如图9所示。

图9为参数b和Parameterd在95%最小显著差数间隔的置信水平下的平均值。从图中可以看出，b=2时的平均值明显优于b=1,3,4时的平均值，因此参数b取2；Parameterd=8时的平均值明显优于Parameterd=4,12,18时的平均值，因此参数Parameterd取8。按照P值递增的顺序，依次得到各因素的最优水平,算法的校验结果为a=40,b=2,Parameterd=8,Parametermu=50。

4.3 算法性能对比

为了验证改进ILS算法在求解第Ι类混流双边装配线平衡问题上的有效性和优越性，将其与如下常用的7种智能算法进行对比：遗传算法(Genetic Algorithm, GA)、离散人工蜂群(Discrete Artificial Bee Colony, DABC)算法、蜂群算法(Bee colony Algorithm, BA)、粒子群优化(Particle Swarm Optimization, PSO)算法、延迟接受爬山(Late Acceptance Hill-Climbing, LAHC)、模拟退火(Simulated Annealing, SA)算法、禁忌搜索(Tabu Search, TS)算法。其中PSO算法设置参照文献[16]，LAHC参照文献[17]，SA参照文献[18]，DABC参照文献[9,19],其余的说明和出处参考文献[9,19]。为了保证算法结果对比的公平性，对所有算法进行重新编码，都使用基于工位的解码方法代替原来的解码方法，并在相同配置的电脑上运行，所有算法的终止条件为运行时间达到n×n×10 ms。

同时，为消除随机因素的影响，将所有算法的每个案例都运行10次，取10次运行结果的平均值、最小值和方差进行对比。表1和表2所示分别为小规模案例和大规模案例的对比结果。表1中：第1列为案例；第2列节拍；第3列为工位数量下限；第4～10列为不同算法的结果；最后3列对应所提改进ILS算法获得的最小值、平均值和方差;ns表示总工位数;nm表示成对工位的数量。

表1 小规模案例结果对比

对于小规模问题P9,P12,P16,P24，实验数据来源于文献[5]。由表1可知，对于小规模问题，所有算法均能找到大部分案例的最优解。其中改进ILS算法10次运行结果的均方差为0，证明了所改进的ILS算法求解小规模问题的稳定性。

表2所示为当前最好解的对比，表中的其他设置与表1相同。大规模问题P65，P148的实验数据来源于文献[5]，对于大规模问题P205，本文做了2组对比实验，第一组实验的数据来源于文献[6]，第二组实验的数据来源于文献[8]。表2中，DABC算法、BA算法、SA算法、改进ILS算法均获得了当前最好解，其中DABC算法获得18个更好解，BA算法获得19个更好解，SA算法获得20个更好解，改进ILS算法获得20个更好解。表2关于平均值的对比中，改进ILS算法有14个优于GA算法，12个优于DABC算法，10个优于BA算法，12个优于PSO算法，19个优于LAHC算法，11个优于SA算法，19个优于TS算法。对于大多数案例，改进ILS算法在10次运行中均能获得当前最好解且均方差为0，证明了改进ILS算法的性能具有优越性且稳定可靠。

表2 大规模案例结果对比

为进一步比较以上算法的综合性能，本文采用统计分析工具ANOVA进行分析。对8种算法求解的均值进行了对比，图10所示为95%最小显著差数间隔的置信水平下的均值。在图10中，改进ILS算法的性能最优，其次是TS算法和BA算法，性能较差的是TS算法和LAHC算法。以上统计分析进一步证明了改进ILS算法的优越性，因此改进ILS算法能高效求解第Ⅰ类混流双边装配线平衡问题。

5 结束语

本文研究了第Ⅰ类混流双边装配线平衡问题，针对该NP难题提出一种改进ILS算法。算法利用改进NEH启发式得到初始解，通过变邻域搜索来加强算法的局部搜索能力，利用扰动的插入操作转移局部寻优在搜索空间中的作用域，达到跳出局部最优的目的，实现算法全局搜索和局部搜索的均衡。同时，通过方差分析选择ILS算法参数的最优组合，证明了算法改进的合理性。

为了提高算法性能，采用新的目标函数和基于工位的解码。新的目标函数，既考虑了最常用的最小化节拍，又考虑了最小化序列相关空闲时间和负载均衡，使算法能在多个解中筛选较优的解，以保留解的细微改进。提出基于工位的解码，该解码方式通过工位选择选取余量较多的边来实现负载均衡，而当余量相同时随机选择，扩大了解的搜索空间；通过操作分配策略尽可能消除序列相关空闲时间，通过优先选择操作完成时间大于下限的操作，进一步保证负载均衡。

为验证所采用的解码方式和改进ILS算法的优越性，将基于工位的解码方式与3种不同解码方式进行对比，将改进ILS算法与7种不同的算法进行对比。实验结果表明,该解码方式能有效减少序列相关空闲时间，保证负载平衡，进一步提高算法性能；本文所采用的改进ILS算法能获得所有当前最好解，优于其他对比算法。后续研究将考虑求解混流双边装配线平衡问题中存在的多约束或不确定因素。

[1] TANG Qiuhua, LIANG Yanli, ZHANG Liping, et al. Balancing mixed-model assembly lines with sequence-dependent tasks via hybrid genetic algorithm[J].Journal of Global Optimization,2016,65(1):83-107.

[2] BARTHOLDI J J. Balancing two-sided assembly lines:a case study[J].International Journal of Production Research,993,31(10):2447-2461.

[3] KIM Y K, SONG W S, KIM J H. A mathematical model and a genetic algorithm for two-sided assembly line balancing[J].Computers & Operations Research,2009,36(3):853-865.

[4] ÖZCAN U. Balancing stochastic two-sided assembly lines:a chance-constrained, piecewise-linear, mixed integer program and a simulated annealing algorithm[J].European Journal of Operational Research,2010,205(1)：81-97.

[5] ÖZCAN U, TOKLU B. Balancing of mixed-model two-sided assembly lines[J].Computers & Industrial Engineering,2009,57(1)：217-227.

[6] CHUTIMA P, CHIMKLAI P. Multi-objective two-sided mix-ed-model assembly line balancing using particle swarm optimization with negative knowledge[J].Computers & Industrial Engineering,2012,62(1):39-55.

[8] YUAN Biao, ZHANG Chaoyong, SHAO Xinyu, et al. An effective hybrid honey bee mating optimization algorithm for balancing mixed-model two-sided assembly lines[J].Computers & Operations Research,2015,53(C):32-41.

[9] LI Zixiang, TANG Qiuhua, ZHANG Liping, et al. Improved discrete artificial bee colony algorithm for type I two-sided assembly line balancing problem[J].Computer Integrated Manufacturing Systems,2016,22(4):974-982(in Chinese).[李梓响,唐秋华,张利平,等.求解第Ⅰ类双边装配线平衡问题的改进离散人工蜂群算法[J].计算机集成制造系统,2016,22(4):974-982.]

[10] LI Zixiang, TANG Qiuhua, MAO Yongnian, et al. An iterated local search algorithm for mixed-model two-sided assembly line balancing problem[J].Mechanical design & Manufacturing,2016(3):54-57(in Chinese).[李梓响,唐秋华,毛永年，等.迭代局部搜索求解双边混流装配线平衡问题[J].机械设计与制造,2016(3):54-57.]

[11] PAN Quanke, RUIZ R. Local search methods for the flowshop scheduling problem with flowtime minimization[J]. European Journal of Operational Research,2012,222(1):31-43.

[12] LI Zixiang, TANG Qiuhua, ZHANG Liping, et al. Balancing two-sided assembly line with a simple and effective iterated local search algorithm[J].ICIC Express Letters,2015,9(10):2695-2701.

[13] LU Rui, WANG Cheng’en. Heuristic approach for resource-constrained project scheduling problems[J]. Computer Integrated Manufacturing Systems,2009,15(12):2439-2444(in Chinese).[卢 睿,王成恩.求解资源受限项目调度问题的启发式方法[J].计算机集成制造系统,2009,15(12):2439-2444.]

[14] NAWAZ M, ENSCORE E E, HAM I.A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem[J]. Omega,1983,11(1):91-95.

[15] HELGESON W B,BIRNIE D P.Assembly line balancing using the ranked positional weight technique[J].Journal of Industrial Engineering,1961,12(6):394-398.

[16] TANG Qiuhua, LI Zixiang, ZHANG Liping, et al. A hybrid particle swarm optimization algorithm for large-sized two-sided assembly line balancing problem[J].ICIC Express Letters,2014,8(7):1981-1986.

[17] YUAN Biao, ZHANG Chaoyong, SHAO Xinyu. A late acceptance hill-climbing algorithm for balancing two-sided assembly lines with multiple constraints[J].Journal of Intelligent Manufacturing,2015,26(1):159-168.

[18] KHORASANIAN D, HEJAZI S R, MOSLEHI G.Two-sided assembly line balancing considering the relationships between tasks[J].Computers & Industrial Engineering,2013,66(4):1096-1105.

[19] TANG Qiuhua, LI Zixiang, ZHANG Liping. An effective discrete artificial bee colony algorithm with idle time reduction techniques for two-sided assembly line balancing problem of type-Ⅱ[J].Computers & Industrial Engineering,2016，97:146-156.