基于遗传算法的汽车装配线快速自动平衡方法研究

摘 要：在关于汽车装配线平衡问题的研究中，普遍存在建模与装配线实际情况偏差大等问题。本文根据汽车装配线的工艺特点建立符合装配线实际需求的第一类平衡问题的数学模型，该模型引入操作区域、车身高度以及装配约束条件等因子。以该模型为基础设计了基于工位动态分割的遗传算法，并采用Java语言验证了该算法，开发装配线快速自动平衡软件。算法不仅解决了装配平衡问题与实际运行状态不符的问题，而且以此为基础，开发了便于企业使用的软件工具。本文以某段整车装配工艺为对象，对算法和软件进行验证，取得了良好的效果。

关键词：装配线平衡；遗传算法；自动平衡

中图分类号：U 466" " " " " " " 文献标志码：A

随着汽车市场竞争日益激烈，车企必须具备柔性灵活的生产能力，提高效率，降低成本，从而提升竞争力。装配线平衡是进行产能调整的主要方法。以前装配线平衡研究与真实的汽车装配线偏差较大，缺乏成熟的生产线平衡工具，对企业的实际指导意义有限。本文设计了更符合整车装配线实际需求的数学模型和遗传算法，在该算法基础上开发了装配线自动平衡分析软件，使企业能够对装配线进行工艺调整，从而灵活调整产能，推广价值较高。

1 装配线第一类平衡问题建模

装配线的平衡问题分为3类[1]，本文研究的问题属于第一类，即给定装配线的生产节拍CT，在满足任务分配的约束条件的前提下使分配后的岗位数量最少，从而缩短工艺流程，降低生产成本。

汽车装配线平衡的基本概念如下。

生产节拍CT：相邻2个车身通过相同位置的间隔时间。生产节拍是企业根据对市场需求的预测确定的，由生产总时间以及生产总量计算得到。

任务Wi：染色体的第i个基因，即该序列的第i项任务。

任务集合S：1条装配线上包括的全部工作任务的集合。

任务作业时间：完成第i项装配任务所需时间，单位为s。本文的作业任务时间均采用时间测量方法（Method Time Measurement，MTM）进行评估，任务最佳作业时间为5 s ～ 20 s ，便于作业重组。

岗位Pk：其包括若干项任务的装配岗位，1个岗位对应1名作业者。

岗位作业时间Tk：第k个岗位所承担的所有任务作业时间之和，如公式（1）所示。

（1）

式中：Tk 为第 k 个岗位所承担的所有任务作业时间之

和；S（k）为第k个岗位所承担的任务集合；tm为第m项任务的作业时间。

岗位负荷率Lk：第k个岗位作业时间与生产节拍的比例，Lk=Tk/CT。Lk越大，作业重组水平越高。

操作区域：根据员工的作业位置将车身划分为6个操作区域，操作区域为左侧、右侧、前部、后部、内部和底部，车身操作区域划分如图1所示，每项任务对应1个操作区域。

车身高度：在整车装配线中，不同线体会根据工艺特点设置不同的吊具高度。车身高度不同，定义车身高度属性，高度={高，中，低}。每项任务对应一个车身高度。

任务关系矩阵：不同操作任务存在装配先后关系，本文采用任务关系矩阵P来记录任务之间的装配先后关系，如公式（2）所示[2]。

（2）

式中：如果执行任务j前已完成任务i，则P（i，j）=1，否则P（i，j）=0。

基于上述基本概念，第一类装配平衡问题的模型可描述为在满足约束条件的前提下，将任务集合S包括的所有任务分配至一系列岗位上，目标是寻求岗位数最小的任务分配方案，如公式（3）所示。

Minimize f（S，P，CT）=Nr " " " " " " " （3）

式中：f为任务集合的分割算法，本文采用遗传算法；S为全部任务集合；CT为生产节拍；Nr为分割后的岗位数；Minimize为算法，目标是寻找岗位数最小的解。

约束条件如下。任务的先后顺序满足任务约束矩阵；任意岗位的作业时间须小于等于生产节拍，如公式（4）所示。

Tklt;CT" " " " " " （4）

当任务结合时操作区域应满足以下5个优先原则。1）操作区域相同的2项任务为第一结合优先级。2）虽然操作区域不同，但是操作区域同属于（左侧，前部，后部）或者（右侧，前部，后部）的任务为第二结合优先级。3）虽然操作区域不同，但是操作区域同属于（左侧，前部，后部，内部）或者（右侧，前部，后部，内部）的任务为第三结合优先级。4）底部区域的作业不能与其他操作区域的作业结合。5）左侧区域的作业不能与右侧区域的作业结合。如果同时满足上述多项优先原则，则先执行高优先级。车身高度属性不同的任务不能进行结合；如果某项任务为独占岗位任务，则该任务必须单独分配至一个岗位中，该岗位只能包括这一项任务；如果某项任务的绑定岗位属性不为空，则该任务只能分配至指定岗位中。该约束针对装配线中不可移动的设备操作类任务，例如燃油加注等，避免再调整已固定设备。

2 构建遗传算法

2.1 编码设计

将所有任务排列成1个符合任务关系矩阵的序列，该任务序列即对应1条染色体，每项任务对应1个基因，染色体长度即基因数量等于任务数量，任务集合编码成任务序列如图2所示[3]。编码后的1条染色体即1个任务序列，该序列共有n项任务。

2.2 初始化种群

为了提高种群质量，本文采用半随机的方式生成初始化种群。从无前序任务的任务集合或有前序任务但是前序任务已经被分配完毕的任务集合中，按照操作区域优先级原则进行任务分配，包括以下5个步骤。1）从任务集合S中挑选无前序的任务，或者挑选虽然有前序任务但是前序任务已经被编入染色的任务放入待选任务集合A中。2）判断终止条件。如果待选任务集合A为空，那么终止。3）从待选任务集合A中随机选择1个任务Wi编入染色体。4）更新任务关系矩阵P，令P（i，j）=0，j=1，2，...，n，n为任务总数量。5）转至步骤1），循环执行上述步骤，直至任务集合S中的所有任务都编入染色体中，该染色体为种群的一个个体。

上述产生种群个体的过程并不是完全随机的，而是对编入染色体的任务设置了选择优先级，将最有利于进行后期动态分割的任务优先编入个体。种群初始化方法提高了种群个体的质量，缩短了最优解的产生时间。

2.3 解码以及适应度函数

解码过程是将一个任务序列进行动态分割的过程[4]，分割过程须满足模型的约束条件，岗位作业时间Tk须尽可能接近CT，即岗位负荷率Lk应接近100%。分割的每一段任务子序列就是一个岗位。1个包括n项任务的任务序列分割为k个子序列，任务序列分割解码过程如图3所示。适应度函数为f=1/Nr，1个任务序列分割的岗位数越大，适应度值越小。

解码过程有以下3个步骤。1）初始化。新建1个岗位Pk，令Tk=0，k=1。2）从左向右依次遍历序列的每一项任务，假设当前遍历的是第i项任务，那么进行如下判断：判断任务i的操作区域、车身高度、绑定岗位与未封闭的岗位Pk是否发生冲突。①如果冲突，则将Pk封闭并新建岗位Pk+1，将任务i存放至Pk+1，令Pk+1，进一步判断任务i是否为独占岗位或该个体的最后1个任务，如果是，则封闭Pk+1。②如果不冲突，则进一步判断任务i是最后1个任务且Pk+1+tilt;CT，则令Tk=Tk+ti，并封闭Pk；如果任务i不是最后1个任务且Tk+tilt;CT，则令Tk=Tk+ti；如果任务i不是最后1个任务且Tk+ti=CT，则令Tk=Tk+ti，并封闭Pk；如果任务i不是最后1个任务且Tk+tigt;CT，则封闭Pk，并新建岗位Pk+1且令Tk+1=ti。3）重复执行第2）步，直至该个体的所有任务都遍历完毕。

2.4 选择

本文采用经典的轮盘赌选择算法[5]，将个体的适应度占种群适应度总和的比例作为个体留下的概率。个体适应度越大，保留的概率越大，其遗传因子会在种群中扩大。个体k选择留下的概率P（k）如公式（5）所示。

（5）

式中：m为种群个体的数量；fk为个体k的适应度；为种群中所有个体适应度之和。

2.5 交叉

本文采用单点交叉法进行染色体交叉操作[1]。步骤一：从种群中随机选取2个待交叉个体X1和X2，随机选取1个基因位k作为交叉点，X1在交叉点k之前的部分保持不变，作为新个体的第一部分，记作X1'1。步骤二：将个体X2中X1'1所含任务删除，剩余任务按原来顺序排列，作为新个体的第二部分，记作X1'2。步骤三：X11'与X1'2按顺序结合，形成第一条新染色体X1'。步骤四：交换X1、X2的位置，用相同方法生成第二条新染色体X2'。步骤五：X1'和X2'替换种群中的X1和X2，完成交叉操作。

2.6 变异

为使变异后的染色体仍然属于可行解，须保证变异后的染色体仍然满足任务关系矩阵要求的装配先后关系，因此本文采用移位变异法[6]，包括以下3个操作步骤。步骤一：随机选择一个待变异的个体以及该个体上的一项待变异任务。步骤二：根据任务关系矩阵从该个体中找到待变异任务的最后一个前X1序任务以及第一个后续任务，这2项任务之间的区间为可行区间。步骤三：将待变异的任务随机插入可行区间，完成个体变异。

3 算法记忆自动节拍平衡软件开发

运用Java对上述改进后的遗传算法进行编程，开发装配线体自动节拍平衡软件，软件主界面如图4所示。

以某整车厂总装车间内饰工艺为研究对象，由于市场需求变化，因此须将该线体从原设计60台/h调整至50台/h，生产节拍由60 s调整为72 s，要求快速制定新生产节拍中的任务分配方案，方案中的岗位数越少，说明该方案越好，产能调整成本越低。应用自动节拍平衡软件进行分析验证，快速自动平衡结果见表1。

程序运行的参数设置如下：种群大小为100，交叉概率为0.6，变异概率为0.01，迭代次数为500。当次程序运行至第4次时产生了较为精益的平衡方案，该方案的岗位数量为4人，平均作业负荷率为90.9%，整车装配线体负荷率水平较高。

利用该软件进行自动线平衡，耗时集中在前期准备任务集合以及任务关系矩阵的过程中，但是每条线体只需准备一次，后续可反复利用；单纯软件运行耗时很短（运行21 项任务、迭代 500 次，耗时约为3 min），效率高于使用传统的人工平衡方法。

4 结语

本文根据整车生产厂装配线的实际工艺特点建立了装配线第一类平衡问题的数学模型，引入更符合整车装配的约束因子，改进了遗传算法，利用Java开发了自动平衡分析软件，取得整车装配线快速自动作业平衡。以某整车厂总装内饰工段工艺为对象进行分析，验证了该软件的可行性和有效性，该软件可广泛应用在制造业装配线体平衡中，推广价值很高。

参考文献

[1]肖中华.基于改进遗传算法的汽车装配线平衡问题研究[D].武汉：武汉科技大学，2010.

[2]邹健.基于改进遗传算法的混流装配线多目标平衡优化及仿真研究[D].锦州：辽宁工业大学，2021.

[3]揣博君.基于改进遗传算法的混流装配线多目标平衡研究[D].哈尔滨：东北林业大学，2018.

[4]吴尔飞.基于改进遗传算法的双边装配线平衡[J].计算机集成制造系统，2007，13（2）：168-274.

[5]王倩.应用改进遗传算法求解汽车双边装配线平衡问题[J].机械工程师，2016（2）：5-8.

[6]李险峰.基于改进遗传算法的汽车装配生产线平衡问题研究[D].北京：北京科技大学，2017.