基于改进遗传算法的多目标装配线平衡优化研究

李 明，包建军，袁逸萍

（新疆大学机械工程学院，新疆 乌鲁木齐 830047）

1 引言

随着智能制造以及智慧装配车间的不断发展，离散制造企业生产模式由单品种大批量向小批量多品种转变。

如今，生产装配成本、产品质量、成品交货期决定了装配企业生死存亡，而这些取决于作业车间工人是否配置合理、作业装配生产线是否平衡、物流运输是否高效，即能否做到生产资源的合理配置和及时优化。

对企业来说更须熟知装配线平衡方法，装配线平衡是指在满足工序间优先关系约束的前提下，将产品切割后的每个工序平均地分配到各个工位上[1]，通过装配线平衡，有效的利用和分配工人和机械设备，使装配生产线在加工时间上不产生闲置同时达到生产平衡。

当前，国内外许多学者对装配线平衡优化也进行了大量研究。

文献[2]基于改进多目标灰狼算法的装配线平衡与预防维护集成优化，综合考虑了装配线平衡和设备预防维护；文献[3]针对装配关系复杂性影响工人工作效率，进而产生瓶颈工位的问题，提出一种考虑装配关系复杂性的改进型多目标装配线平衡优化方法；文献[4]为了更有效地减少工作站数目、提高装配线效率，提出了一种基于多目标混流装配线平衡问题的方法；文献[5]提出了多目标模拟退火算法，以解决混流装配线平衡排序优化问题，并采用了一种新的接受策略，提高了算法寻优能力。

综上所述，装配线再平衡问题是典型的多目标优化问题[6]，现有的处理方法大多采用单目标优化，此外在求解算法方面，传统遗传算法[7]的全局搜索能力不佳。

基于以上分析，为了帮助离散制造企业管理人员对装配线进行更加高效的平衡规划，文章以最小化生产节拍、最大化产线平衡率和最小化平滑指数为优化目标建立装配线再平衡优化模型，采用改进的遗传算法对平衡模型进行求解，并引入启发式任务分配规则，提高了算法寻优能力。最后以青贮机装配线实际案例验证算法的可行性和有效性。

2 多目标装配线平衡优化数学模型

这里研究的问题可简化为：根据生产需求确定装配线生产节拍的情况下，对于其最优工位数进行求解，从各种工序a,b生产组合中判断的Op(k)总加工时间，进行各工位的分配，确定工位k，分配完成时，达到CT，K和B的最优。文章以满足生产需求的最小节拍条件下最小化工位数K、最大平衡率B和最小平滑性指数为优化目标对装配线平衡进行优化。

（1）优化目标1：Hmin。

在求解过程中，添加一个目标，记为H：

式中：Bmax—平衡率的最大值。

（2）优化目标2：节拍时间小于等于生产所需求的节拍。

（3）优化目标3：平衡率B最大化。

在装配过程中，工序数以及工位都不确定，当工序变化时，工位数也随之变化，总工位数也因此变化。目标值可由工位数量K在不同的工序组合下寻找一组最优的组装组合，使工位数尽可能少，进而得到最小的目标值，这里生产线平衡率B的计算方式为：

式中：Ik相当于k工位的空闲率；

各个工位Ik的平均值。

（4）优化目标4：平滑性指数最小化。

在优化过程中，平滑性指数越小，表示装配线总体状态越优。

式中：K—工位数；

k—工位索引，k=1,2,……，n；

a,b—工序索引，a,b=1,2,……，m；

Xak—第a个工序分配到工位k时为1，否则为0；

Yk—第k个工位在利用时为1，否则为0；

Ta—第a个作业的作业时间；

Op(k)—k工位可分配的操作集合；

CT—生产线节拍；

B—生产线平衡率；

Pred—作业在完成顺序上的先后约束关系的集合。

3 改进遗传算法设计

3.1 编码方法

基因串的编码采用自然数编码，编码是长度为N的数据串。每一个基因的序号对应作业工序的编号，基因座上的基因值标识的是分配到的各个工位的工序编号，如图1所示。

图1 编码方法示意图Fig.1 Schematic Diagram of Coding Method

3.2 获得初始种群的方法

将N个作业工序分配到K个工位上，需要考虑每个作业的约束工序和工序组合下的每个工位时间等于或小于生产节拍。这里使用了基于任务排序的种群初始化方法。

首先，任取出一个任务节点，放入空队列，然后接下来在剩余节点中的任一节点上，按作业优先顺序将其他节点放入（只能放在左边就放在左边，只能放在右边就放在右边，两边都能放，就任选一个位置放入），重复以上操作过程，直到队列放满位置。

3.3 交叉和变异

针对问题的特性和编码方式，这里采用两点交叉方法，如图2所示。从原始种群中任意选两个染色体为父代1和父代2，然后可生成两个交叉点n1、n（21

图2 交叉操作示意图Fig.2 Cross Operation Schematic Diagram

任意产生一个染色体，将其作为变异的父代，然后随机找个变异点1 ≤n1≤n。接下来首先根据作业优先顺序找到变异点的前约束工序，保持前约束工序和其前面工序基因排列顺序不产生变化，然后找到变异点的后约束工序，保持后约束工序和其后面的工序基因排列顺序不产生变化，将变异点放入染色体前约束工序和后约束工序间的任何基因点，最后组合以上三部分基因生成子代染色体排列顺序，如图3所示。

图3 变异操作示意图Fig.3 Sketch of Mutation Operation

3.4 适应度

这里建立的优化模型的目标值为越小越好，个体的适应度值与种群中个体的目标值相悖，即目标值越小，其对应的适应度值越大[8]。

因此，文章提出了如下的适应度函数：

式中：K—个体对应的目标函数；u—不小于maxK的常数。

4 实例分析

以农机典型产品青贮机装配线为研究对象验证算法的可靠性和有效性，首先需要对装配线参数进行收集，绘制产品的作业优先顺序图并计算理论生产节拍。

4.1 作业优先顺序图

绘制青贮机装配线的作业优先图需要两个不可缺的因素，第一需要对工位进行编号，并将工位切割为多个工序；第二需要收集各工序的实际作业时间[9]。

运用工业工程中的秒表法测量青贮机装配线各工序工时，进行装配线平衡分析，结果，如表1所示。

表1 青贮机装配线时间分析Tab.1 Time Analysis of Y1 Production Line

由此绘制青贮机装配的作业优先顺序图，如图4 所示。其中，圆圈代表每个工序，圆圈上的数字表示各工序的标准作业时间，箭头则表示作业的先后约束关系。

图4 青贮机作业优先顺序图Fig.4 Priority Chart of Silage Harvester Operation

由表1计算出当前装配线平衡率B：

根据过去历史销售数据和销售预测，目前实际每天需要生产数量为10件/shift，由此计算出理论生产节拍：

4.2 平衡方案求解

基于上述算法思路和流程，首先采用通用仿真工具MAT‐LAB 进行了算法实现，在程序中取生产节拍TT=54min，样本数（种群大小）s=100，进化代数G=300，选择的最优个体数目K=15，交叉的概率Pc=0.8，变异的概率Pm=0.06。迭代结果和工位甘特图，如图5~图6所示。

图5 迭代次数Fig.5 Number of Iterations

图6 青贮机装配工位Gantt图Fig.6 Gantt Diagram of Silage Harvester Assembly Station

4.3 仿真结果分析

根据上述优化结果，工位数为15时的青贮机装配线平衡方案，如表2所示。

表2 工位数为15的装配线平衡方案（节拍时间=52min）Tab.2 Balancing Scheme with Working Number 15 of Assembly Line（TT = 52 min）

从计算结果可以得出：优化后青贮机装配线工位数为15时的生产节拍CT、装配线平衡率B、Hmin、最小平滑性指数分别为：

优化后实际节拍小于理论生产节拍，可以满足生产的需求。通过优化，青贮机装配线总平衡率为由64.4%提高到90.6%，提高了26.2%，同时优化目标Hmin和平滑指数均为最小，装配线平衡优化的同时提高了整体的生产效率。

5 结束语

对于离散装配企业，装配线平衡的优化可以有效提高生产效率以及产品质量。文章以最小化生产节拍、最大化产线平衡率和最小化平滑指数为优化目标建立装配线再平衡优化模型，并采用改进的遗传算法对平衡模型进行求解，并引入启发式任务分配规则，提高了算法寻优能力。最后以青贮机装配线为实例验证算法的可行性和有效性。

通过优化，青贮机装配线平衡率由64.4%提高到90.6%，提高了26.2%，同时各装配工位负荷更加均衡，提升了作业人员积极性，也极大减少了在制品堆积。结果表明，运用改进遗传算法可有效解决农机企业装配线平衡问题。