麻 娟，刘俨后，楚满福，高 军

(山东理工大学 机械工程学院, 山东 淄博 255049)

装配线平衡(Assembly Line Balancing, ALB)是指在满足特定的约束条件下，将装配作业元素分配到不同的装配工位上，使工位数和生产节拍合理，同时各操作工人的生产负荷尽量均衡[1]。1954年Bryton在其学位论文中正式提出ALB问题，并列举了一些解决方法[2]；Salveson首次用数学解析的方法对ALB进行了研究，提出一个求解ALB问题的线性规划模型[3]；Jachson在给定生产节拍条件下，采用枚举法解决了最小化工位数量的ALB问题[4]。但是，ALB问题是一个NP-hard问题，在作业数量增加时，容易产生组合爆炸，数学解析法和一般的启发式算法求解效果不理想。

近年来，遗传算法(Genetic Algorithm, GA)在基础理论和实际应用上均取得了长足的发展，在车间调度、制造元设计、车辆路径、设备布局、网络设计等许多组合优化问题中得到了成功应用。Noorul等将关键阶位权重法引入GA的初始化过程，提出一种混合GA对ALB问题进行求解[5]；Kim等针对一个具体的问题设计特定的启发策略与GA结合，加快算法收敛速度[6]；Mutlu等和Zaman等将工人操作技能作为约束条件建立了ALB问题模型，并设计了一种改进GA进行求解[7-8]；皮兴忠等依据作业优先关系生成初始群体以及构造交叉算子和变异算子，保证搜索空间中个体的可行性，以提高算法的效率[9]；吴尔飞等针对双边装配线的特点，提出一种基于序列组合编码的GA，对ALB问题进行求解[10]；刘金山等设计了企业链和任务链的双链GA，以解决制造资源优化配置问题[11]。

上述研究中，GA通过保留精英个体实现解空间信息的染色体遗传共享，种群比较快速地向最优区域移动，收敛性较好。但同时也容易造成进化过程早熟，难以获得最优解，而早熟收敛也是GA的一大缺陷[12]。为此本文提出一种混合遗传算法(Hybrid Genetic Algorithm, HGA)，将烟花算法(Fireworks Algorithm, FWA)中基于免疫浓度思想的分布式信息共享机制引入GA，以保持进化过程中种群多样性；将邻域搜索引入变异操作，以改进算法的局部搜索性能。针对第Ⅱ类ALB问题的求解，将本文的HGA与其它典型算法进行对比分析。

1 平衡问题描述

为方便描述，文中涉及变量见表1。

表1 变量符号定义

Tab.1 Variable symbol

符号定义C生产节拍m工位数量n作业数量S工位集合,S={s1, s2, …, sm}sti工位si的作业时间A作业元素集合,A={a1, a2, …, an}ti作业元素ai的作业时间Bn×n作业优先约束0-1矩阵,bij=1表示作业aj必须在作业ai后面进行

一般可将ALB问题分为三类[13]：ALB-Ⅰ，固定生产节拍C，最小化工位数量m；ALB-Ⅱ，给出工位数量m，最小化C；ALB-Ⅲ，已知C和m，最小化均衡指数SI

(1)

在实际装配生产中，设备和人员基本固定，随着市场需求波动或工人操作经验改变而导致作业时间发生变化时，企业更需要ALB-Ⅱ优化，以保证生产节奏适应市场变化，提高生产柔性。因此本文以ALB-Ⅱ为研究对象，在给定工位数量m下寻求最小节拍C，同时将均衡指数SI作为评价指标。基于表1所述相关变量，建立本文ALB-Ⅱ数学模型如下：

min(C，SI)

(2)

s. t.

(3)

(5)

(6)

函数表达式min(x.y)表示优先最小化变量x，x值相等时最小化变量y，即若x1

决策变量xij=1表示作业ti分配到工位sj，xij=0表示作业ti未分配到工位sj。约束条件式(3)表示每个作业只能分配到一个工位，且每个作业必须被分配；式(4)表示约束优先关系被满足；式(5)表示每个工位必须被使用；式(6)表示每个工位作业时间满足节拍约束。

2 混合遗传算法

在GA的进化进程中，适应度越高的父代个体参与繁衍后代的机会越多，而适应度低的父代个体逐渐被淘汰，这种精英保留策略使得种群较快收敛，但容易造成进化过程早熟，最终导致算法陷入局部次优，难以获得最优解。FWA是一种新颖的群体智能算法，它通过爆炸、变异、选择等进行爆炸式搜索，与GA具有相似的进化过程，但却有本质上的不同。FWA采取免疫浓度思想(Immune Concentration, IC)的分布式信息共享机制，有利于保持种群多样性，避免陷入局部最优解，但进化过程缺乏精英解的指导，容易陷入随机搜索，造成计算资源耗费、难以收敛。为解决此问题，本文结合二者优势，基于GA框架提出一种混合遗传算法(HGA)：在选择算子中引入IC思想，以保持种群多样性；在变异算子中借鉴邻域搜索(Neighborhood Search, NS)策略，以改进算法的局部搜索性能。

2.1 问题编码

采用作业序列编码方式，按作业分配至工位的顺序进行编码，每个作业元素对应于染色体上的一个基因位。如图1所示，第一次分配a1，第二次分配作业a2，……，第九次分配作业a4，最后一次分配作业a3。

图1 10个作业的染色体编码Fig.1 Chromosome encoding of 10 tasks

ALB-Ⅱ问题的生产节拍C是未知的，在解码的时候不能按照C去分配作业，对于这个问题的解决思路是预估一个C*，以C*为约束按照一定的增量进行探索求解计算。由于ti的离散性，C*的增量是不连续的，而是以ti作为增量。解码过程如下：

(1)计算理论最小节拍Ct=(Σtk)/m，其中Σtk表示所有作业元素作业时间之和，m为给定的工位数量，令C*=Ct。

(2)以C*为节拍，按照染色体编码作业序列把n个作业分配到m个工位中，如果每个工位作业时间均满足sti≤C*，则C*就是在这种排序下的最小节拍，搜索停止；否则转(3)。

(3)计算工位sti的潜在增量d1，d2，…，dm，其中di(i=1, 2, …，m-1)表示工位si+1的第一个作业元素作业时间，dm=0。

(4)令C=max{sti}，C*=min{sti+di}，若C≤C*，则C就是此染色体编码排序下的最小节拍，搜索停止；否则转(2)。

HGA的初始化是随机生成N个个体编码的过程，种群Q={q1,q2, …,qN}，然后通过交叉算子、变异算子和选择算子，基于初始种群完成进化搜索。

2.2 基本操作算子

2.2.1 交叉算子

交叉算子采用两点交叉法，如图2所示，随机产生两个交叉点，在父代2中搜索父代1基因段的排列方式，进行交叉替换获得子代1，同样的交叉过程获得子代2，如图3所示。这种交叉操作能够保证子代个体为可行解，减少计算量，提高算法效率。

图2 两点交叉算子Fig.2 Two-point cross operator

图3 子代的编码Fig.3 Encoding of offspring

2.2.2 变异算子

个体的染色体进行独立的变异，采用单点变异，随机产生一个变异点，对变异点后面的基因段进行重新排列。重新排列的过程，即根据优先关系矩阵重新分配作业的过程，获得新的子代，如图4所示。

图4 染色体变异操作Fig.4 Mutation operator of chromosome

2.2.3 选择算子

适应度评价函数是区分种群个体优劣的标准，是进化中优胜劣汰的唯一依据。ALB-Ⅱ的优化目标是生产节拍C最小化，本文将SI作为第二评价指标，如式(2)所示。

f1=min(C);C=max(sti)

(7)

(8)

(9)

函数len(x)表示获取数值x的整数位数，即式(9)表示将f1作为整数部分，f2作为小数部分，组合得到数值f，f越小则适应度越优，符合式(2)要求。

根据适应度评价，从子代种群中选取下一代种群，除最优个体外，其余个体采用轮盘赌规则选出，选择概率为

(10)

2.3 基于NS的交叉操作

在基本变异算子中引入邻域结构，提高HGA的局部搜索能力。在变异操作中获得子代以后，随机产生两个变异点，在两点范围内生成邻域结构(在矩阵B约束下重排序)，如图5所示。

图5 变异中的邻域结构Fig.5 Neighborhood structure in mutation

对邻域空间进行局部搜索会占用大量的计算资源，进而影响算法效率，HGA会根据算法迭代次数控制邻域规模进行变邻域搜索，变邻域规则如下：

(11)

式(11)表示变异操作时需进行邻域搜索的概率，其中t为迭代次数，T为最大迭代次数。通过变邻域可以实现种群在进化初期进行较大范围的邻域搜索，而到了进化后期，只需要进行小范围邻域搜索来达到寻优的目的，既提高了算法局部搜索性能，也能保证搜索效率。

2.4 基于IC的选择操作

基本选择算子通过精英策略选择子代，算法收敛性较好，但容易早熟收敛。将FWA爆炸算子中的IC策略引入选择算子，以提高种群多样性。定义选择概率pI为

(12)

(13)

式中，‖qi-qk‖表示个体之间的欧式距离，即个体与其它个体偏离越大，其被选中的概率越大，从而避免了多样性损失，但也容易使算法陷入随机搜索过程。结合GA的精英保留策略和FWA的IC选择策略，定义HGA的选择算子概率为

p(qi)=λ1pE(qi)+λ2pI(qi)

(14)

式中0≤ λ1≤ 1，0≤ λ2≤ 1，λ1+λ2= 1，通过系数可调整精英保留策略和IC选择策略的权重。HGA综合了GA收敛性好和FWA种群多样性优的特点，提高了算法全局搜索性能。

2.5 HGA基本流程

HGA的基本流程如图6所示，其中算法终止条件为最大迭代次数。

图6 HGA的基本流程Fig.6 Flow chart of HGA

3 算例求解

Kilbridge问题是一个10工位ALB测试问题[14]，工位数m=10，作业数量n=45。Kilbridge问题作业优先约束关系如图7所示，作业时间见表2。

图7 Kilbridge问题作业优先关系Fig.7 Precedence relation of Kilbridge-problem

将HGA、GA以及文献[15]基于成组工序遗传算法(Group Technology Genetic Algorithm, GGA)进行求解结果对比，种群规模N=300，交叉概率取0.6，变异概率取0.4，迭代终止条件为最大迭代次数200；进行100次重复试验，算法各自寻到的最佳解作为算法的最优解，求解结果见表3。

表2 Kilbridge问题作业时间

Tab.2 Task’s time of Kilbridge-problem min

No.tiNo.tiNo.tiNo.tiNo.ti19102019728243742911102042943873101211215530539541013622143174045171422232732441216171511242933154212713161925263434368131712266357445920183275369455

表3 Kilbridge问题求解结果

Tab.3 Solution of Kilbridge-problem

求解算法最优解CSI最优解次数平均运行时间/sGA588.7233/10036.5HGA564.0078/10027.1GGA564.1272/10039.0

从表3可以看出，在最优解求解能力方面，HGA和GGA相当，且均优于GA；在算法求解效率方面，HGA优于GGA和GA。

4 结束语

装配线平衡是典型的组合优化问题，作业优先约束增加了问题复杂性，针对第Ⅱ类装配线平衡问题，提出一种混合遗传算法进行求解。HGA将FWA爆炸算子中基于免疫浓度思想及GA中精英保留策略进行结合，设计了选择算子，以保持进化过程中种群多样性；同时将邻域搜索策略引入变异操作，以改进算法的局部搜索性能。通过第Ⅱ类装配线平衡问题实例，将本文的HGA与典型GA进行对比分析，验证了HGA的有效性，为装配线平衡问题的解决提供了一种新的方法。