基于成组技术的遗传算法求解第Ⅱ类装配线平衡问题

摘 要：个性化需求的出F，致企业多品种、小批量的装配线平衡出现失调问题。针对第Ⅱ装配线平衡问题，分析成组技术与最小节拍的对应关系，结合成组技术、遗传算法建立数学模型，按照遗传算法进行编码、译码、构造适应函数。成组技术问题是组合优化问题，而遗传算法正是目前求解组合最优化的有效方法之一。因此，文章将成组技术与遗传算法相融合，提出了一种基于遗传算法的工序成组方法。

关键词：第Ⅱ类装配线；遗传算法；负荷平衡；成组技术

中图分类号：F253.9 文献标识码：A

Abstract： The emergence of personalized demand， resulting in multi-species， small batch of assembly line balance imbalance problem. Aiming at the balance problem of the second assembly line， the correspondence between the group technology and the minimum beat is analyzed. Combining the grouping technique and the genetic algorithm to establish the mathematical model， the genetic algorithm is used to encode， decode and construct the adaptive function. Group technology is a combinatorial optimization problem， and genetic algorithm is one of the effective methods to solve the combinatorial optimization. Therefore， this paper combines group technology with genetic algorithm， and proposes a process grouping method based on genetic algorithm.

Key words： class Ⅱ assembly line； load balancing； genetic algorithm； group technology

0 引 言

对于日新月异的社会发展，随之企业的装配线负荷平衡就成为瓶颈问题。装配线的失衡会严重造成企业生产效率大大降低，装配线负荷平衡可以有效解决工人、机器等待问题，并使工作站之间负荷均衡，以保证生产效率的提高。从根本上讲，装配线平衡就是组合优化问题，但是该问题涉及到产品设计研发和制造过程，这也就决定工作站先后顺序以及作业元素逻辑关联。市场需求多样性的变化对装配线的柔性要求增强，但在实际生产过程中由于工序的排列不合理、工作站负荷不均衡等一些因素导致装配线不能顺畅进行。针对装配线平衡目标的不同，单一型装配线平衡分四种：第Ⅰ类：已知装配线节拍C，优化工作站数N；第Ⅱ类：已知装配线工作站数N，优化节拍T；第Ⅲ类：已知装配线工作站数N，优化均衡指数SI；第Ⅳ类：已知装配线工作站数N，优化相关指数SN。

装配线平衡（Assembly Line Balance，ALB）是个组合优化问题，属于典型的NP-hard问题，到目前为止没有公认的最优算法。Salveson[1]首次提出ALB的线性规划模型；Dooyoung[2]采用0-1整数规划同时优化装配线工作站节拍问题；Tonge[3]提出了一种启发式算法优化装配线；Rubinovitz[4]等人研究了结合启发式算法的装配线平衡的遗传算法。不过上述算法多为理论值，没有完全结合实际状况，导致可信度差；采用单纯的遗传算法（Genetic Algorithm，GA）优化装配线平衡问题，因不满足实际约束的可行解使最优解不可行。

本文提出了一种结合成组技术的遗传算法来优化第Ⅱ类装配线的数学模型，运用工序成组结合传统的遗传算法，既保留了原始遗传算法的空间搜索能力又仅在可行解空间搜索。本文针对第Ⅱ类装配线采用该方法进行优化。

1 遗传算法

遗传算法（GA）是Holland受自然界生物进化论启发而提出来的，它是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局化概率搜索算法。随着GA的开启可以克服启发式方法的规则困难，同时提出了一种新的有效决策支持工具，而之前启发式方法的产生主要是因为现实建模的需求但没有万能的启发式规则。GA依一定的概率进行全局搜索，并且可以较大概率求得最优解，GA过程中的适应度函数的选择，编码和译码规则对装配线平衡都有影响，鉴于此本文采用工序成组的非标准遗传算子，保证解的可行性，同时采取最优策略避免最优解的丢失，其可定义为8元组[5]：

GA=（C，E，P ，M，Φ，Γ，ψ，T），T） （1）

上述式中8元组依次表示个体编码方法、适应度函数、群体范围、选择算子、交叉算子、变异算子、终止条件，本文处理每个单元的规则将结合装配线实际情况具体操作。

2 设计装配线遗传算法模型

装配线平衡（ALB）问题的研究就是产品装配过程中每个工作站工序的分配，使其作业元素按照一定的装配操作顺序进行装配，运用遗传算法（GA）就是每个工作站的工时接近节拍T或者差距最小。因此分配工序任务时需要降低工作站之间的空闲时间，平衡其作业时间。在运用GA时需要结合实际约束，这些约束用数学表达如下：

（1）S ∪S ∪…S =D k=1，2，…，m；――工作站中工序的约束。

（2）S ∩S =φ i≠j；i，j=1，2，…，m；――工作站之g工序的约束。

（3）TS ≤T k=1，2，…，m；――工作站时间与节拍的约束。

（4）若M =1， i∈S ， j∈S ， 则x≤y， M=M 为优先矩阵；――工序顺序约束。

D表示工序集合，M表示工作站数k=1，2，…，m，S 表示第i个工作站工序集合。上述为装配线基本约束，目标一般就是衡量装配线的指标，尽量减少工作站之间的空闲时间，最终达到每个工作站总工时均衡，提升生产效率。

2.1 成组工序的装配线遗传算法模型

本文主要针对成组工序的第Ⅱ类装配线平衡问题进行研究[6]，运用成组技术将工序集中分类安排，使节拍T最小化，工序相似度最大，提高装配线效率。用数学模型描述该装配线问题如下：

w 为某一个工序的某一特征的权重系数；x为工序代号；k为零件的特征要素数，k=1，2，…，s；i，j为待分类的工序数，i，j

=1，2，…，m；针对工序成组特征本文选取5M1E（人，机，料，法，测，环）六个方面，每个特征方面依据工艺及工作站要求赋予权重。权重系数反应每个工序之间的相似度，需要满足归一条件，即∑wx =1k=1，2，…，6。余弦值越接近1，就表明夹角越接近0度，也就是两个工序越相似，夹角等于0，即两个工序相等。

2.2 编 码

遗传算法的优化结果受编码规则的影响，在实际装配线生产过程中约束较多，一般的二进制编码会影响整个算法的每一步，因此在这里并不适用，所以需要选择特殊的编码方式。针对装配线平衡问题，由于受装配线工序先后顺序以及工艺设计的约束，所以可用装配工序图表示现有的流程制造。图1是某装配线的工序流程约束图，连接点的弧表示工序顺序，节点上方数字表示工序时间，装配线的排列顺序也就是成为一种优化组合问题，使工序先后逻辑顺序编码符合实际约束更为简单[7]。在排列工序时应结合成组技术，按照工序的相似度进行配列，最大可能分配同一个工作站，提高装配线作业效率，降低工序之间的空闲时间。因此，本文采用工序成组的方法对染色体进行编码，每个工序对应一个基因，每个工作站对应一段基因位，按顺序排好。图2为图1工序约束图下的一个染色体。每个工作站的总工时不能超过节拍T。

2.3 译 码

编码后的染色体要按照一定的规则进行译码，该过程是将工序编码表示的染色体（成组工序）中的每个基因（工序）顺序分配各个工作站。在工作站给定的情况下，依据染色体中工序号顺序最小化节拍T（最大化生产效率P）和工序的相似度最大[8]。首先在给定满足工作站数的条件下，依照染色体的工序号，运用模糊聚类分析法――夹角余弦法对每个工序进行分类，再依据给定的工作站数以及工艺要求进行分配，然后依据工作站上所分配工序求其时间。在此过程需要满足以下条件：

（1）每个工作站的工时不能超过节拍时间，即TS ≤T；

（2）一个工序只能分配一个工作站；

（3）考虑到节拍的约束，若一个工序不能被分配到工作站，但该工序的紧后工序可以分配，则该工序优先分配到工作站。

在译码过程需要借助平衡指数SI= 来衡量成组工序分配情况，即∑s 值的合理性。

2.4 适应函数的构造

由于该适应函数是求极大值的过程，但是平衡指数是极小值问题，因此需要进一步转化SI也为极大值。本文借助指数函数构造适应函数如下：

fi= +e

其中：SI= ，因此就有指数函数越小，相似度越大，节拍越小的染色体使适应函数越大。

2.5 初始群体的选取

为保持最优解的可行性和计算结果的精确性，本文采取的可行解都是在装配线可操作的工序条件下进行筛选。因此依据工序流程图采用图论中随机拓扑排序方法生成初始群体，具体步骤如下：

（1）使当前初始化染色体序列为空；

（2）随机从工序流程图中选择一个无紧前工序安插在当前序列尾部；

（3）在图中删除该节点以及所连接的边，若已无节点则输出当前作业序列，否则转（2）。

成组工序顺序的输出是建立在装配线实际情况之上，可排列组合出新的成组工序，并生成初始群体。

2.6 选择策略的确定

因需要适应值较大的个体保留在群体中，本文采用确定式采样选择方法（Deterministic Simpling）。其具体操作过程如下：

（1）群体中每个个体在下一代中期望生存数目N ： N =M i=1，2，…，M。

（2）用N 的整数部分 N 确定每个对应个体在下一代群体中生存数目，其中 N 表示取不大于x的最大整数。由该步可确定下一代群体中的∑ N 个个体。

（3）按照N 的小数部分对个体进行降序排列，顺序取前M-∑ N 个个体加入到下一代群体中，至此完全确定出下一代群体中的M个个体，保持总的群体数量不变。

上述的选择方法保证了较大的适应群体被保留，避免最优解流失，也就是最优的可行性解的保留。

2.7 交叉和变异准则

单点交叉算子（One-point Crossver）：它是指个体编码随机选取某个交叉点，然后互换该点后的部分染色体，是一种最常用和最基本的一个交叉方式。由于初始群体是可行解，经过单点交叉后产生的新一代个体也是可行解。初始群体具体操作方式如下：

（1）初始群体中随机选取两个进行配对。若该群体数量为M，则有 M/2 对进行配对；

（2）对于每个相互配对的个体，随机设置某基因后的位置为交叉点。若染色体长度为n，则共有n-1个交叉点数[9]；

（3）依据设定的交叉率（一般0.4～0.99）进行交叉互换部分基因，从而产生两个新的个体。

用上面两个染色体说明单点交叉操作，随机选取交叉点：position 1=5，产生的新个体见图3。

基本位变异算子（Simple Mutation）：依据变异率p 对当前染色体上基因位进行变异操作，本文为保证可行解的持续，采用位移变异方式。随机选择一个关系进行变异操作，将其插入约束条件下的任意位置，而它的紧随工序按照原来的顺序排列，这也就保证了变异后的可行解持续性[10]。取工序6进行变异，将其插入第十个位置，则8，10，7，9工序向前平移一个位置，工序11位置保持不变。具体操作过程如图4：

2.8 终止代数

鉴于本文工序数目较少，终止代数取100，即进化100代后结束运算。

3 实例分析

基于第Ⅱ类装配线结合遗传算法的叙述，本文采用仿真软件Matlab2016a基于处理器为Intel（R）Core（TM）i5-4256U/2.4GHz，操作系统为64位四核window10平台进行模拟，交叉概率0.8，变异概率0.2。选取一条十一个工序四个工作站的装配线为例，其总工时为46s，优化结果如表1至表3：

目前装配线平衡率P =P =P = =95.83%；minT为11S；均衡指数SI = =1.4；SI =SI

= =2即SI

4 结束语

针对第Ⅱ类装配线工序相关因素（5M1E）分析，提出了成组工序的作业序列，在此基础运用遗传算法。该方法既保留了原有的GA遗传算法搜索能力，又依据实际情况选择初始群体和构造交叉算子、变异算子，重要的是只在可行解范围内进行搜索最优可行解。交叉算子一般取0.4～0.99，变异过程中算子的随机选取范围0.3～0.5。在适应度函数方面考虑了各个工序之间的相似度和装配线的平衡率以及平衡指数，可以用来比较不同工作站内工序相似度，增加工序的聚集度，提高工作效率。由于本算法中的相似度根据5M1E需要赋予相应的权重，该过程会涉及到主管因素，所以在结果上会产生差异性，结合实例可见该算法以及相关指数还是取得相对满意的结果。本文的成组工序遗传算法的提出，为提高装配线效率和改进装配线技术提出了参考依据。

参考文献：

[1] Salveson M E. The assembly line balancing problem[J]. Journal of industrial Engineering， 1955，6（3）：18-25.

[2] Dooyoung Shim， Hobey Min. Flexible Line balancing practices in a just-in-timeenvionment[J]. Production and inventory management Journa1， 1991（4）：38-41.

[3] Tonge F M. Summary of a Heuristic line balancing Procedure[J]. Management Science， 1960，7（11）：21-42.

[4] Levitin， Rubinovitz， Jacob， et al. A genetic algorithm for robotic assemblyline balancing[J]. European Journal of Operational Research， 2006，168（3）：811-825.

[5] 周明，O树栋. 遗传算法原理及应用[M]. 北京：国防工业出版社，1999：19-20.

[6] 皮兴忠，范秀敏，严隽琪. 用基于可行作业序列的遗传算法求解第二类装配线平衡问题[J]. 上海交通大学学报，2005，39（7）：1123-1127.

[7] 朱会霞，王福林，张勇，等. 改进遗传算法优化非线性规划问题[J]. 数学的实践与认识，2013（7）：117-125.

[8] 梁燕，金烨. 基于工位约束快速启发式算法的混合装配线分段优化[J]. 上海交通大学学报，2007，41（9）：1501-1505.

[9] 鞠彦兵，李桂芬，王爱华. 基于遗传算法的车间作业计划仿真研究[J]. 数学的实践与认识，2006（10）：79-85.

[10] 吴君华，夏巨谌，曹山河. ALB问题的数学模型及其优化算法的研究[J]. 系统学报，1999，11（5）：358-361.

[11] 王丽颖，孙丽，王秀伦. 基于虚拟工序的小批量工序质量控制方法研究[J]. 计算机集成制造系统，2006，12（8）：1263-1266.

[12] 郭胜会，杨育，邢青松，等. 基于联合作业序列的遗传算法求解第二类装配线平衡问题[J]. 机械，2011，11（38）：42-47.