基于双种群遗传算法的L公司生产线平衡问题研究

李杨帆

摘要：本文通过对L公司连接器线圈生产线平衡问题的研究，根据客户需求及生产情况，建立生产平衡率最优及均衡指数最低的多目标优化数学模型，在Matlab环境下进行双种群遗传算法设计，实现工作站负荷均衡，节省生产成本，消除作业间生产过剩。

Abstract： This paper studies the balance problem of connector coil production line of L company， establishes the multi-objective optimization mathematical model with the best production balance ratio and the lowest equilibrium index according to customer demand and production situation， and designs the double population genetic algorithm in Matlab environment， to achieve workstation load balancing， save production costs， and eliminate overproduction between operations.

关键词：生产线平衡；双种群遗传算法；多目标优化数学模型

Key words： production line balance；double population genetic algorithm；multi-objective optimization mathematical model

中图分类号：TG95 文献标识码：A 文章编号：1006-4311（2018）33-0272-02

0 引言

随着智能移动端产业迅猛发展并趋于成熟，移动端配件的市场需求日益增长。连接器线圈等配件生产方式基本采用流水线型，其生产线均衡情况直接影响产能和效率，所以生产线平衡是电子产品制造重组优化的重要方法之一。

国内外学者对生产线平衡进行了大量研究。文献[1]利用领域搜索算法解决混合品种汽车装配生产线的平衡问题；文献[2]采用遍历搜索和遗传算法对生产线进行平衡处理；文献[3]运用遗传算法对汽车底盘装配生产线平衡进行了分析改善。

1 生产线现状

L公司为移动端品牌商制造配件产品，根据客户需求，建立一条连接器线圈生产线，初步优化后对该生产线调研，运用IE方法测定各工序的标准时间，并根据工序优先关系绘制优先关系图（图1），结果如下：

生产线的主要问题有：

①客户要求日产量为2000件，日工作时间为10h，即生产节拍最大为18s，目前节拍12.9s，导致工作站位过多与生产过剩；

②生产线平衡率较低，出现半成品堆积。

2 生产线平衡模型建立

2.1 目标函数

式中，生产平衡率越接近1，生产状态越好，工作站越少；均衡指数越小，工作站负荷越均衡；α和β为赋予目标函数的权重，α+β=1，若α<0.5，则均衡指数比生产平衡率重要。文中取α=β=0.5；为使目标值计算方向一致，将生产平衡率做取负值处理。

2.2 约束条件

3 双种群遗传算法设计

生产线平衡优化采用的方法中，数学模型方法如整数规划[4]等，更适用于解决小规模问题；仿真方法如Arena[5]等，在解决模型构造复杂的问题时运算量过大，不易寻优求解；智能算法如遗传算法[6]等，对求解模型复杂的多目标问题有一定优势，可得全局最优解。单种群遗传算法收敛速度过快，导致过早结束收敛，陷入局部最优。而基于双种群的改进遗传算法扩大了搜索范围，对解决陷入局部最优问题是一良好方案。故此，本文采用双种群遗传算法求解生产线平衡优化问题。

3.1 染色体编码和解码

染色体编码即工序编码，采用整数排序，每个工序编号代表一个基因位，将工序按图1优先关系随机抽取并整数排列，多次操作获得初始种群。

染色体解码根据染色体基因型进行紧前约束转换，将工序依次填入工作站且不超过节拍时间，否则工序将填入下一工作站，最终检查是否所有工序均已分配。

3.2 适应度函数以及选择算子

3.3 变异算子和交叉算子

变异算子有利于维持种群多样性，本文采用两点互易法，步骤为：①产生随机自然数c1和c2；②交换第c1和c2位基因。

交叉算子推动整个种群进化，本文采用两点交叉法，步骤为：①随机选择两个染色体作为父本；②产生随机自然数c1和c2；③将两个父本染色体c1至c2之间的基因片段交换， 得到两个子代染色体，并对其修订，使得染色体无冲突。

4 求解

本文基于双种群遗传算法对L公司生产线平衡问题建模，运用Matlab软件实现算法设计，设置6组最大生产节拍的实验数据，分别进行算法求解，对比得到最优结果。具体参数设置为：工位数最大值N=20；最大生产节拍为CT=13，14，15，16，17，18；初始种群数pop_1= pop_2=10；遗传算法迭代次数ga_1=ga_2=100；变异概率PM_1=PM_2=0.5；交叉概率PC_1=PC_2=0.7。6组实验数据运行结果如表1。

对比结果可知，CT=17时适应度值最优，优化后生产平衡率由78.2%升至92.14%，均衡指数由3.36降至1.87，工作站数由20降至13。遗传算法计算求解的工序分布结果如图2。

5 结论

①本文在L公司生产线平衡问题中运用双种群遗传算法，并结合Matlab进行求解，优化后生产线平衡率提升13.94%，均衡指数降低44%，工作站减少7个，使生产线负荷更加均衡并减少了人工成本。②双种群遗传算法求解生产线平衡问题更易得全局优化结果，使L公司生产线得到改善，并验证了双种群遗传算法在该领域的可行性。③本文根据生产线平衡问题进行的双种群遗传算法设计对其他企业开展类似研究有参考价值。

参考文献：

[1]刘文平.混合品种汽车装配线平衡与排序问题研究[D].山东大学，2009.

[2]方景芳，徐艳凯.基于遍历搜索与遗传算法的生产线平衡优化[J].计算机应用与软件，2017，34（08）：276-280，300.

[3]刘环宇，夏吉庆，施灿璨，文士发，王吉权.基于遗传算法对A公司生产线平衡的分析[J].物流技术，2014，33（17）：367-370.

[4]熊建星.基于Arena仿真的生產线改善研究[D].成都理工大学，2014.

[5]田凌峰.基于FLEXSIM的A公司生产线平衡问题优化研究[D].成都理工大学，2017.

[6]赵云飞.基于遗传算法的生产线平衡改善研究[D].南昌大学，2014.