基于双种群遗传算法对A公司生产线改造以及平衡问题研究*

杨 磊，徐晓鸣※，张海洋，曾伟镇

（1.广东海洋大学机械与动力工程学院，广东湛江 524088；2.小天才科技有限公司，广东东莞 523846）

0 引言

在需求多样化市场下，客户对产品的交付质量和交付周期要求越来越高，如何将客户需求与批量生产相结合来组织生产，是企业面临的一个难题。国内外企业纷纷引进精益生产方式，采取混流生产线，以期提高生产效率和降低节拍，提高企业自身的竞争力[1-3]。然而，进行混流生产线改造首先要解决其平衡问题。

针对混流生产平衡研究中，根据研究内容不同，第一类是给定节拍时间，求最小工位数；第二类是给定生产线长度，求最小化节拍时间；第三类是优化生产线工位负荷均衡。以往的研究大致有以下几种研究方法：工业工程改善方法、启发式算法、仿真方法和智能算法。吴智勇等[2]通过建立补充生产机制、模式排产、作业改善等精益改善方案，提升了混流生产的问题；许向川等[3]利用Flexsim 仿真的方法，建立仿真模型，通过精益改善，提升了生产线平衡率；周金平[4]利用Plant Simulation 仿真软件研究混流生产的物料配送问题，优化最大完工时间。包建军等[5]运用启发式算法对混流装配线的平衡问题进行分析与优化，并采用Flexsim 仿真验证优化方案的有效性。邱伊健等[6]利用Flexsim 对混流生产线的瓶颈问题，生产线平衡问题进行优化，并进一步利用遗传算法优化投产序列；李伟等[7]针对混流装配线第二类平衡问题，建立了基于作业空间和装配工具约束等条件下的优化模型，并利用遗传算法进行求解；郑晨鸣等[8]考虑了作业时间随机情形下，最小工作站数和各产品负荷均匀为目标，设计改进的遗传算法并验证其有效性。

本文结合A 企业实际生产场景，通过合并工艺相似的产品生产线，在考虑工序之间优先顺序、产品需求信息和作业时间约束下，以生产节拍和负荷均衡为目标，建立混流生产线第二类平衡问题的多目标混合整数规划模型，设计求解模型的有效算法，有效提高混流生产线平衡率和降低生产线均衡指数，从而提高企业的生产效率。研究内容为企业改造混流生产线提供理论依据和技术支持，可以推广到其他类型的混流生产线设计与改造上。

1 混流生产线平衡模型建立

在一个计划期T内，已知某混流生产线上有N个工作站完成M种产品的装配作业，这些产品的工艺相近、结构相似，属于企业内同一产品族的[9-10]。该混流生产线上所有类型产品所包含的工序数为S，每种产品需求为Dm，M种产品的总需求量为表示第m种产品在第i道工序上加工的时间，由于不同类型的产品工序上有所不同，所以如果第m种产品不含有第i道工序，那么tim= 0，qm为第m种产品占总需求的比例，其中qm=Dq∕D；Tmk为第m种产品在第k个工作站单件装配的时间。

模型假设条件：（1）各个作业元素的操作时间不变；（2）混流生产线的工作站可以进行一种或者多种作业元素的操作，员工均为多技能工，可以完成任何任务；（3）一个作业元素仅能被分配到工作站，一个作业元素只能在一个工作站内完成该作业元素的全部内容；（4）产品作业元素的优先关系已知，并且作业元素加工的优先关系不可变动。

该问题数学模型如下：

式中：CT为混流生产线的实际生产节拍；C*为混流生产线的理论节拍，C*=T∕D；Pre(i)为依据作业元素的优先关系，先于作业元素i完成的作业元素集合。

式（1）表示在相同权重下求取最小生产节拍和负荷指数；式（2）表示产品在生产线中最小生产节拍；式（3）表示生产线的负荷指数，式（4）表示每个作业元素都只能被分配到一个工作站进行加工；式（5）作业元素的分配必须遵守优先关系集合；式（6）表示工作站的作业时间不得大于理论节拍时间；式（7）表示作业元素分配的决策变量，1表示作业元素i被分配到第k工作站到，0则表示作业元素i未被分配到k工作站。

2 双种群遗传算法

传统的遗传算法中，只有一个初始种群开始操作、交叉和编译遗传，也称为单种群的遗传算法。虽然这种算法简单快捷，但是它很容易陷入局部最优解而且搜索空间有限，因此需要在这种算法的基础上扩大搜索空间，能够跳出局部最优解，所以需要一种改进的遗传算法要在不止一个的种群之中来开展操作[11-12]。

双种群遗传算法思路是两个子种群使其各自进化，再选择合适的节点，使其按照设定的规则进行种群间的交流，这种方式使用起来并不算复杂，而且可以扩大了搜索的空间而避免了陷入局部最优的缺点。其中这两个子种群都有它各自的作用，种群1 中的交叉概率Pc和变异概率Pm的值较大，这个种群称为探测子种群，主要是在进化过程不断地超越平面，克服过早收敛，使算法可以保持较高的搜索效率；种群2 的交叉概率Pc和变异概率Pm的值较小，被称为开发子种群，主要可以在局部范围内寻找优秀个体，并把这些个体保持下来。

2.1 编码设计

编码直接决定了遗传算法后续的操作，如选择算子、交叉算子和变异算子的实现，遗传算法的计算性能是受编码直接影响的。应对不同的实际问题，应采取恰当的编码方式，这样才不会产生大量的非可行解，使得计算过程变得十分冗余。通过优先关系图来设计编码方式，以保证种群解的可行性，编码设计思路如图1所示。

图1 优先作业关系编码

2.2 译码设计

译码的思路如下：对未知的生产节拍，进行节拍预估，一般是预估一个理论节拍CT*，然后以一定的增量去进行试探计算。

步骤1：初始化节拍，计算理论节拍令CT*等于这个理论节拍。

步骤2：以CT*为暂定节拍，并将作业元素按照作业元素优先关系图的逻辑关系将m个作业元素分配到n个工作站中。可以得到每个工作站的时间：T1，T2，…，Tk，…，Tn，如果这些工作站的时间小于CT*，那么CT*就是这个状态下的最小节拍，搜索就停止，如果不是那么进行下一步计算。

步骤3：计算潜在增量Δ1,Δ2,Δ3,…,Δn，其中Δi是第i+1 个工作站的第一作业元素的时间(i= 1,2,3,…,k,…,n)。令目前的工作站中作业时间最大 的 作 为 实 际 节 拍CT，CT*= min{Tk+ Δi} ，如 果CT≤CT*那么CT就是这种分配方案下的最小节拍，搜索停止；如果不符合条件就返回步骤2继续分配作业元素。

2.3 适应度函数设计

本生产线平衡建立模型第一目标是最小生产节拍，本文通过平衡率指标来映射生产节拍，第二目标函数则是负荷指数，所以构建的适应度函数为：

2.4 选择算子设计

采取轮盘赌方式进行选择，将种群中的个体分别计算遗传到下一代的概率，再计算每个个体的累计概率，当个体适应度越大被选中的概率也就越大。

2.5 交叉算子设计

交叉算子采取的是两点三段交叉，首先在父代染色体选取两个交叉点，将这交叉点两段之间的基因截取，在父代2中寻找相同基因片段的排序，将父代2中排序的基因投放至父代1 的交叉点之间形成子代1。子代2 的形成，同理可得。如图2所示。

图2 交叉示例

2.6 变异算子设计

采用单点交叉，在父代染色体中获取变异点，变异点之前的基因保持不变，变异点之后的基因根据删除后的优先关系矩阵重新编排。如图3所示。

图3 变异示例

3 案例应用

3.1 现有门体预装生产线的平衡分析

目前A 公司的门体预装生产线的生产模式是可变品种的批量生产，取该生产线生产量最大的3 种产品BD330、BD144、BD96，其日需求量分别为500、500、250，A 公司的日有效工作时间为10 h，各种型号的工序加工时间如表1所示。

表1 工序加工时间

BD330、BD144、BD96的理论节拍分别为72 s、72 s、144 s，生产平衡率分别为0.531、0.373 和0.509，现场测得BD330、BD144、BD96 的实际生产节拍分别为77.35 s、77.35 s和60.26 s，仅BD96的实际生产节拍在计划节拍内，在计划期内只有BD96 可以完成预期的计划。剩下两种产品都只能通过加班加点的方式来进行产品产量的补偿。

3.2 门体的作业元素划分

进行混流生产线平衡的研究要将在生产线上生产的产品最小作业单元划分出来，根据A 公司门体预装生产线的实际生产情况，按照作业元素划分的原则，使每个作业工序划分到不能进行下一步划分的程度划分作业元素时，遵循的原则如下。

（1）工序在被拆分之前可以进行标准时间测量。

（2）若遇到不能再进一步拆解的工序，那么该工序就是最小的作业单元。

（3）某些工序存在特殊的加工方法，在拆分工序后也必须保持加工方法。

考虑实际的生产情况和划分作业元素遵循的原则，将作业元素划分如表2所示。

表2 作业元素划分表

3.3 绘制出综合优先关系图

过各个产品的作业元素优先加工顺序表以及对应的加工时间，再通过各产品的作业元素优先加工顺序表和各产品之间的需求比例制作出混合作业元素的时间表，进而绘制出综合优先关系图，如图4所示。

图4 综合优先关系

3.4 混流生产线改造

根据综合优先关系图，按照关系图中的作业元素的加工顺序逻辑，一个作业元素是另外一个作业元素的紧前工序则标注1，若不是紧前工序则标注0，按照这样的规则建立综合优先关系矩阵。

基于平衡模型和双种群遗传算法，matlab 编程求解，将现有的门体加工作业元素进行重新分配，将各作业元素分配至固定的工作站中。

作业元素分配的结果如下：

工作站1：作业元素1→2→4

工作站2：作业元素3→5

工作站3：作业元素6

工作站4：作业元素7

工作站5：作业元素8→10→13

工作站6：作业元素9→14→12→11

工作站7：作业元素15→16

工作站8：作业元素17

3.5 改造效果

通过混流改造后，计算可得混流生产线的平衡率为0.859、节拍为48.16 s，平滑指数为3.375。进行混流改造后实际生产节拍远低于各个型号产品单独生产时的实际生产节拍，平衡率也相比于之前各产品单独生产时有了较大幅度的提升。

4 结束语

本文通过对A 公司生产线研究，对其生产线进行混流改造，通过建立生产线平衡问题，应用双种群遗传算法对其进行工序的重新编排，求解出较优的工序安排解，改造后优化了生产效率，提高了生产效率，

研究表明针对多样化的产品，在工序以及结构相似的情况下，进行相同工序的合并，相似工艺结构的产品合并，进行混流改造，可以满足客户需求，有效地提升生产效率，降低企业生产成本。同时，利用双种群遗传算法对工序的重新编排，可以扩大搜索空间，防止陷入局部最优，对混流生产线平衡问题优化有重大意义，该方法和技术可以推广到其他类型的混流生产线设计与改造上。