基于双种群遗传算法的T 公司生产线平衡改善

赵龙基，刘 洋，郑 璇，吴鸿宇

（中国矿业大学（北京） 能源与矿业工程学院，北京 100083）

0 引言

随着第四次工业革命的到来，全球的制造业正在遭受着前所未有的冲击和变革。各个工业发达国家相继制定了国家战略规划，以求在这次变革中抓住新的发展机遇。近年来，中国发展进入新常态，发展速度逐渐放缓，企业出现了产能过剩、制造成本升高、客户流失的现象，竞争程度日益激烈。因此，企业在面对激烈的竞争环境下，不仅要重视技术研发，更要注重生产管理，改变原有的生产方式，合理分配生产资源，优化生产线，提高生产效率。

对生产线进行平衡性改善是工业工程专业领域最初始也是最基本的问题，能够合理调配企业内部生产，消除生产过剩、作业间不平衡所导致的效率损失[1]。传统制造业对生产线的研究是将生产工艺进行细分，并根据细分后的工作内容，将生产线作业过程划分为不同的作业单元的阶段[2]。此类研究方式优点在于易于提高工人作业熟练度，单元生产效率快。但此类划分方式容易导致划分后工作任务分配不平衡，不同的工序作业时间相差较大，生产线整体节拍高、部分工位生产力浪费严重，需要进行后续改进。国外关于生产线优化方面的研究始很长的时间，但直到21 世纪，国内的专家和学者才开始对生产线优化进行深入研究，目前在研究过程中主要用到工业工程技术、数学模型、仿真建模等优化工具等。 VanchaiLaem 运用工作研究相关方法，以冷冻食品加工生产线为研究对象，通过优生产工艺流程，对工序进行重排优化和合理布局，生产线平衡率提升了12.48%，单个产品生产成本降低了16.65%。Pornthipa 通过调研分析生产流程，找出了生产中的瓶颈工序。然后应用生产线平衡相关理论和ECRS 四大改善原则对生产流程进行优化，并用小车运输代替人工搬运，达到了节省生产人员14 位，生产效率提升至94.2%的效果。Kitaw 通过对服装生产过程进行仿真模拟，识别出瓶颈工序，并应用工业工程方法为解决瓶颈工序、生产效率低及服装产品周期短、生产周期长等问题提供了优化方案。国内外学者对装配生产线优化的问题研究主要是基于改进算法和建立仿真模型，主要包括粒子群算法、遗传算法、蜂群算法等。因此，本研究采用双种群遗传算法以及Flexsim 软件对T 公司生产线平衡问题进行优化求解最终达到提升生产线平衡率以及降低生产节拍的目的。

1 T 公司生产线平衡问题的数学描述

1.1 T 公司生产线数据及生产线流程图

T 公司作为一家传统的制造企业，其生产线作业方案制定主要是按照工艺方式与作业顺序，工位安排与产线布局粗糙，不同工作站之间作业时间相差较大，不同作业单元的工人劳动强度悬殊，由此带来工人工作人员情绪低落，工人安全与产品质量难以保障，生产效率低下、生产成本增加。基于以上原因，对T 公司目前生产线进行平衡性改善研究，提高生产线平衡率、重新规划工作站是提高产量，降低成本的有效方式。目前T 公司生产线平衡率现阶段为85.85%，生产线平滑指数为3.85。生产节拍为49.11 s。整条生产线利用率最低的流程的加工率只有17.2%，利用率排名前十的工序加工率平均值为84.63%。

T 公司的65F6 机型生产线的主要工时统计表见表1。

表1 65F6 机型作业工序节拍

T 公司初始生产线流程图如图1 所示。

图1 初始生产线流程图

1.2 生产线评价指标及目标函数

目前主流的生产线平衡评价指标为生产线平衡率与生产线平滑系数，其定义以及计算公式如下[3]：

生产线平衡率：生产线平衡率通常用来形容整条生产线作业时间的平衡程度，同时也可定量展示生产线的连贯性，其计算式为：

式中：P为生产线平衡率；T（Si）为编号为i的作业单元的作业时间；maxT（Si）为作业时间最长的作业单元；m为工作站数量。

平滑指数：平滑指数通常被用来衡量某一单个工作站与整条生产线的平均生产时间之间的偏离程度，其计算式为：

式中：SI为生产线平滑指数；CT为生产线生产节拍；T（Si）为编号为i的作业单元的作业时间；m为工作站数量。

主要改善目标是根据上述两个评价指标，通过工作站的划分，提高生产线的整体平衡率，降低生产线平滑指数。据此，设立目标函数为：

式中：n为工作站序号；α=β= 0.5。P越接近1，生产线平衡效果越好；生产线的平滑指数SI与工作站负荷的均衡程度成反比。α与β为分别赋予生产线平衡率以及生产线平滑指数的权重，为两者赋予相等的重要程度，在分母中的SI之后加0.01 是为了避免SI为0 时产生无穷大干扰求解。目标函数就是综合生产平衡率和生产平衡指数，对生产线进行评价的一个值，并通过采用双种群遗传算法来防止平衡指数收敛过快，从而避免至得出局部最优解。

基于上述数学模型与生产线的实际情况，拟定如下约束条件：

（1）作业单元最小：一个作业单元在一次分配中只能存在于同一个工作站。

（2）作业单元必须全部分配完成。

∪ni=1Si = E（5）

（3）所有工作站的加工时间均低于生产线节拍。

（4）作业单元的分配需要服从作业单元之间的优先关系，即作业单元的分配需要满足0-1 矩阵：

若作业单元i为单元j的紧前工序，那么aij= 1，否则aij= 0。

2 T 公司生产线的双种群遗传算法设计

2.1 作业单元编码

使用遗传算法解决生产线平衡问题的首要步骤是采用一个能够针对具体问题特征的编码方式对作业单元进行编码。采用实体编码的方式进行编码，把每一个单独的作业单元作为一个单独的基因，选择作业单元序号所有排布情况中能够满足作业优先顺序的排列方式作为染色体数据串，将其作为初始种群的染色体，这种编码方式能够比较完好地适应目标函数以及操作算子从而使得算法结果具有准确性[4]。

本文结合实际生产过程中工艺流程获得优先关系矩阵，进而对作业单元进行编码，得到双种群遗传算法中的初始染色体。

2.2 译码

译码就是在满足约束条件的情况下，将染色体所包含的信息转换为实际表现。根据生产线平衡问题类别的不同，译码的方式也会随之发生改变[5]。

本文对CT 值的探索方式进行改进，基于生产线节拍自身所存在的变化规律进行译码，其主要步骤如下：

（1）以理论最优解作为初始值，初始化生产线节拍，计算公式见6。

式中：T为生产线上所有单元加工完成的时间之和；M为预设的生产线初始工作站数量。

（2）基于CT(初始)按照作业单元之间的优先顺序将n个作业单元分配到m个工作站，设第个工作站的作业时间为T（si）。将工作站作业时间T（si）与初始作业节拍CT(初始)进行比较。当所有工作站的作业时间均小于作业节拍，则认为此种情况下的作业排布满足最优解，停止搜索并输出最优解。如果不满足，则进行下一步操作。

（3）对设计生产节拍的增量，根据生产线的性质以及生产节拍的定义，我们取可能增量为Δi= 第i+1个工作站的首个作业单元作业时间（i= 1，2，3，…，m- 1）。

（4）确定节拍增量后将节拍增量与初始节拍相加得到增量后的生产线节拍。

（5）令CT= max{T（si）}如果CT(修正)> = min{T（si）+Δi}则重新返回第二步，继续对CT进行修正，否则取得最小节拍，停止迭代。

2.3 适度评估

本研究的问题归属于第二类生产线平衡问题，预期目标为生产线平衡率尽可能大的同时，生产线平滑指数尽可能小，因此本文预设适度函数为：

式中：

2.4 选择

用轮盘赌的方式进行父代选择。轮盘赌方式的实际含义为：将所有父代被选择的概率进行归一化处理，并按照适应度分配每个个体被选择为父代的概率。

2.5 交叉

传统的遗传算法因为引入适度函数，会导致局部最优解的出现概率较大，为了防止此类情况，引入第二种群，第一个种群进行全局搜索，提供最优超平面，第二种群进行局部子搜索，保证算法的收敛速度。

本文在具体运行算法的过程中，采用了两点交叉的方式进行来获得新的个体。

2.6 变异

为了保证能够探寻全局，采用的双种群遗传算法对子种群1 设置大变异算子，子种群2 设置小变异算子。操作如下：

定义大变异算子：

式中：P1m为第一个子种群出现交叉的概率；P2m为第二个子种群出现交叉的概率；f1max为第一个子种群中适应度最大的个体适应度；f2max为第二个子种群中适应度最大的个体适应度；f1avg为第一个子种群所有个体的适应度；f2avg为第二个子种群所有个体的适应度。

2.7 种群基因交换

为了充分发挥双种群遗传算法全局搜索的优势，算法每一次迭代均进行如下的基因交换：

（1）交换两个种群中适应度最高的个体。

（2）在父代挑选结束后，随机交换若干个个体。

3 实际案例

选择较为经典的生产线模型——Jackson 模型进行试求解。令初始种群1 和2 中的个体数均为100；种群1 和2 的交叉概率分别为0.8 与0.2；种群2 的变异率为0.05；迭代300 次。

在上述条件下，求不同工站数目之下函数的最优解，从而确定能够使得生产线平衡性最优的工位布置方式。

通过对不同数量的工作站情况下取得最优工序排布情况进行统计，结果见表2。

表2 不同工作站数量下的最优工序排布

从表2 可以看出，当工作站数量取5 的时候，目标函数取得最大值0.5542 生产线平衡率最高为97.79%，生产平滑指数为3.85。随后无论工作站取4或者6、7、8，目标函数均无法取得超过0.5542 的最大值，且生产线平衡率与生产平滑指数也都无法超过5个工作站时的情况。

因此，最优工作站数量为5。同时，根据现场实际情况对最优解进行调整，最终结果见表3。

表3 最优工作站数量下的生产线数据

4 基于Flexsim 改进效果仿真验证

为了更好地验证工作站划分带来的效果，根据改进之后的工作站排布方式建立仿真模型，如图2 所示。

图2 划分工作站后的生产线线仿真模型

由表3 可知，划分工作站之后，工作站数量为5的工作耗时最少。在划分工作站的过程中对作业单元进行了删减，因此需要对产量进行在此仿真评估，搭建改进后的仿真模型如图3 所示。

图3 改善后的生产线流程图

改善后运行模型，经过一个月后，得到生产线月产量为82453 台，较未改善的月产量54543 台提高了51.17%。生产节拍由最初的49.11 s 提升至32.48 s。

5 结束语

本研究通过采用双种群遗传算法对生产线数学模型进行求解，并统计百次运行下的最优目标函数分布情况。研究结果表明，生产线最终平衡率由公司现阶段实施方案的85.85%提升至97.79%，生产线平滑指数为3.85。生产节拍由最初的49.11 s 降低至32.48 s。整条生产线中，利用率最低的流程的加工率从17.2%提升至52.13%，利用率排名前十的工序加工率平均值从84.63%降低至80.02%。整条生产线的平衡率得到有效提升。