基于遍历搜索与遗传算法的生产线平衡优化

方景芳 徐艳凯

(兰州理工大学机电工程学院 甘肃 兰州 730050)



基于遍历搜索与遗传算法的生产线平衡优化

方景芳 徐艳凯

(兰州理工大学机电工程学院 甘肃 兰州 730050)

对L公司两类生产线状况进行分析，建立了描述生产线平衡的数学模型，以最小化生产线工作站数和最小负荷平滑指数为目标，对生产线进行优化。对于简单的生产线，通过遍历搜索算法, 首先找出所有可行的作业加工顺序，然后求出最小的工作站数和最小平滑指数及相应的作业加工顺序。对于复杂的生产线，利用遍历搜索得到的结果作为遗传算法的种群，应用遗传算法，求出最小的工作站数和最小平滑指数及相应的作业加工顺序。解决了该公司的生产线平衡问题，也说明了遍历算法和遗传算法在生产线优化中的有效性。

生产线平衡 工作站数 遍历算法 遗传算法 生产线优化

0 引 言

生产线平衡是调整生产线中各工作站的作业，以使各个工作站的作业时间尽可能和生产节拍相等或相近。因为当生产线中的各个工作站的加工时间不平衡时，那么总工作时间较长的工作站中必然存在制品严重积压，而后续的工作站处于空闲状态，从而使整条生产线不能顺畅进行。对生产线平衡的优化，主要解决两类问题[1]，第一类是在给定生产线工作量的情况下，确定生产节拍，对生产线中工作站的数量进行优化，使工作站的数量最小化；第二类是确定生产线的工作站数量，尽可能减小生产线的生产节拍，从而最大化生产线的加工能力。实践中发现，对于个性化定制的产品，客户总是会给出一个加工时间，这样每类产品便有了固定的生产节拍。实际面临一个准时交货的问题，为了保证产品的交货期，使得生产顺利进行，就要进行各工作站时间的平衡，并且在进行系统优化的过程中，还要综合考虑对作业人员进行动素分析、局部仿真，以及对物流路径等进行分析。文献[2]采用工业工程基本方法对生产线平衡进行了分析，并提出了优化方向。文献[3-4]建立了混流生产线的仿真模型，对瓶颈问题、生产线平衡进行了研究。遗传算法属于启发式优化方法，通过建立数学模型来寻找问题的最优解，文献[5-7]在对生产线分析的基础上，设计了遗传算法，结果生产线平衡率得到了提高，解决了生产线的不平衡问题。文献[8-10]在平衡优化的过程中采用改进遗传算法，平衡优化效果明显。本文选择参加生产实践的L公司生产线进行了第一类问题的实验。对于公司A生产线，系统不太复杂，且工段数量不是很大，潜在的作业排序数量也是有限，若应用遗传算法会造成大量重复迭代计算。为了合理解决这类问题，设计了遍历搜索算法；而对于较复杂的平行生产线B生产线，用遍历搜索效率就太低了，这时往往用遗传算法求解，遗传算法能处理群体中多个个体，具有良好的全局搜索性能。所以对L公司的生产线本文采用遍历搜索和遗传算法进行优化研究。

1 L公司A生产线问题的分析

L公司A生产线生产的下拼模块，市场需求量大，并且生产过程中存在加工难度较大、加工效率低的状况。本文选择A生产线下拼模块的6个工作站进行调查研究，并结合标准作业指导书来分析这6个工作站的作业要素。统计数据显示，下拼模块每天生产1件产品，每天生产7小时，所以该段生产线的生产节拍为7小时。而从整条生产线的情况来看，各工序段忙闲不等，各工序间联系不够紧密，严重影响了生产系统效率，需要进行生产线平衡的改善。表1表示该段生产线上各个工作站上的作业时间总和。

表1 各工作站作业时间表 min

按照下式计算该生产线的平衡率：

(1)

得到：

对这一条生产线而言，平衡率达到85%才算合格，平衡损失率应控制在15%以下。过低的平衡率，表明生产线有相当大的改善空间。这段生产线的平衡率仅为59%，远远达不到合格的水平。说明该生产线各工作站之间的作业负荷量很不均衡，平衡率有待提高。

2 数学模型的建立

数学理论与实际生产系统相结合，利用生产系统参数进行数学建模，并提出高效的数值求解方法，是生产线平衡优化的基本理论框架。考查一条生产线是否合理，不仅要看其工位的数目是否最小，还要看生产线的负荷是否均衡。以作业顺序图和节拍为基础，寻求生产线工作地数量最小的工作方案，可由式(2)和式(3)来描述：

(2)

minF1=αm+βF

(3)

式中，CT为生产节拍；Sk为第k个工作站的总加工时间；m表示工作站的数量；F表示生产线的平滑指数；F1表示目标函数是工作站数和生产线平衡指数的线性组合，其中α和β用以分配工作站数和平滑指数在优化目标函数中占的比重。为了突出生产线平衡的重要性，本文选取α=0.3、β=0.7。

3 遍历搜索算法求解

3.1 搜索可行的加工顺序

L公司A生产线上工序之间的先后约束关系可由图1来表示。图的遍历，是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。访问顶点所做的操作依赖于具体的工序之间的先后约束关系，利用具体实践，通过C++编程，来达到遍历各个工序节点的目的。

图1 为A生产线的工序约束图

图1中的节点表示工序，连接节点的箭头线表示工序加工先后顺序。从图1中可知，该生产线可行的加工顺序数量有限，直接采用遍历搜索算法即可找出所有可行的加工顺序。

开始搜索之前，先根据工序先后关系图，建立该生产线的优先关系矩阵M。工序优先关系矩阵M=(Mij)n×n，如果第i道工序在第j道工序之前完成，则Mij=1，否则Mij=0。根据优先关系矩阵，搜索可行的加工顺序。首先，判断n是否大于0，如果是，则找出可以排在最前面(前面没有其他工序)的工序，该工序满足下列条件：

在队列中存储工序j；否则返回。然后判断队列是否为空队列。如果为空，退出搜索；否则，输出队首的工序，在M矩阵中删除该工序对应的行和列，工序数减少1。具体搜索过程如图2所示。通过C++编程，对于A生产线，搜索出可行的加工顺序共30种。

图2 遍历算法流程

3.2 把作业分配到工作站

在把作业分配到工作站时采用最大分配原则法。最大分配原则就是在分配作业元素到工作站时，保证该工作站的总工作时间不超过生产节拍的前提下，把尽可能多的作业元素分配给这个工作站。

根据各作业元素的加工时间(如表2所示)，分别对每种可行的加工顺序，首先把每个作业先分配到工作站，记录每个工作站的作业元素、计算工作的总加工时间，统计工作站的数量。最后再计算出每种加工顺序对应的目标函数值，确定最优的加工顺序。

表2 作业元素的加工时间 小时

3.3 运行结果

本文通过C++语言编写算法程序，程序运行的结果显示，A生产线共有30中可行的作业加工顺序。最优的加工顺序如图3所示。优化后的工作站数量是4，较之前的6个工作站减少50%。

图3 A生产线的最优作业先后关系图

每个工作站中的作业元素，工作站的总加工时间见表3。结果表明，采用该模型可以大幅提高整个生产线的平衡性，从而降低了总加工时间。

表3 各工作站作业分配

优化后生产线的平滑性指数F=1.01，生产线的平衡率从59%提高到89%。

实践表明：采用遍历搜索算法来实现生产线中作业的重新排序，以及最小化工作站的数量，算法简单、准确性高。对于作业数量较少，可行的作业顺序数量有限的生产系统，可以用遍历搜索算法得到生产线平衡的最优解。

4 L公司B生产线应用遗传算法求解

L公司B生产线是公司连续梁生产线。因为连续梁是支座组装的重要环节，且连续梁生产线存在效率低下、成本浪费等生产线不平衡现象，所以对连续梁的生产线平衡问题进行展开分析。利用式(1)计算可知，该生产线的平衡率为65%，平衡率比较低，需要改善提高。

对于复杂的平行生产线系统，如公司的B生产线是有25个工序、15个工作站的连续梁平行生产线，作业数量较大，可行的作业排序数量数以亿计，用遍历搜索效率太低，不宜采用完全遍历算法。为了合理解决这类生产线的平衡问题，本文编制了遗传算法。

遗传算法本质也是搜索算法。这种算法把每个潜在解当作一个染色体个体，然后通过个体的交叉和变异，产生新的个体(潜在解)。使个体进化到越来越好的区域，最后求得问题的最优解。以下是遗传算法的实现过程。

4.1 B生产线工序的编码

B生产线各工序总时间24.2小时，生产节拍为2.5小时，该生产线的紧前工序和紧后工序可由工序约束图4来表示。

图4 B生产线的工序约束图

上述每个作业元素对应一个基因位。为了应用遗传算法，对作业元素进行统一编码。即对每一作业分配一个唯一从1到25的数字符号，对作业元素进行标识。

本文为数据元素定义了数据结构。

struct Process

{

char Title[20];

int Num;

float Time;

};

其中，Title字段存储作业的名称，Num字段为作业的编号，Time字段为作业的加工时间。

4.2 初始种群选择

首先根据生产线的工序约束图建立工序优先关系矩阵M=(Mij)n×n。借助于遍历搜索算法，搜索出部分可行的加工顺序。把搜索的加工顺序数量设置为2千万个，程序运行了1.5小时。从搜索出的加工顺序中，随机取出一部分，作为一个初始种群。

4.3 个体交叉

交叉是将种群中的个体染色体搭配成对，并以一定的方式交换它们之间的基因位，得到新的个体。在进行交叉操作时本文采用了两种方法，第一种方法采用固定点操作法，任意选择两个适宜的个体作为交叉对象(父个体)，两个个体在固定的基因位置进行交叉基因码操作，形成两个新个体；第二种方法是随机点交叉法，即使用固定长度的二进制符号串来确定要交叉操作的基因位置。为了简单说明两种交叉操作过程，本文采用只有8个工序的生产线为例进行说明。生产线中作业的先后顺序如图5所示。

图5 某生产线的工序约束图

对于两个个体，如果在奇数点进行固定点交叉。子个体1中偶数点位基因继承父个体1中相应位置的基因，奇数点位置的基因按照在父个体2中顺序保留。按照相同的方式得到子个体2。结果如表4所示。

父代1：

父代2：

子代1：

子代2：

表4 工序图个体

如果按照随机点交叉方式操作，在交叉前需要随机生成一个长度等于基因数量的二进制数。在子个体1在二进制数为1的点位上继承父个体1的基因，其他位置的基因按照在父个体2中的顺序继承。子个体2按照相同的方式得到。结果如表5所示。

二进制串：

父代1：

父代2：

子代1：

子代2：

表5 个体交叉示意图

4.4 个体变异

为了扩大遗传算法的搜索空间，避免得到局部最优解，需要进行变异操作。变异是将强行改变个体染色体中的某些基因位上的值而形成新的个体。由于每一个作业对应一个编码，因此实际操作中可随机交换两个基因得到新的个体。由于生产线中作业加工顺序的限制，变异后的个体可能不符合实际生产要求，因此需要对变异后的个体进行检验，判断其是否满足优先关系矩阵的逻辑关系，并且只有当变异的新个体优于旧个体时，才能把其更新为新的个体。变异操作仍以图5为例来说明，如果在2和3位置交换基因，变异的结果如图6所示。

图6 个体变异示意图

4.5 B生产线工序的译码

染色体个体中每个基因对应着一个工序，每个个体对应一种作业加工顺序。已知该生产线的生产节拍2.5小时，对每种加工顺序，根据作业的加工时间，采用最大分配原则的方法把各个作业元素分配到每个工作站，然后计算目标函数值。为此，本文定义了工作站数据结构，存储每个工作站的信息。

struct Station //定义工作站数据结构

{

int work[N];

int p;

float time;

};

其中，work字段存储作业的编号，p字段指示作业的个数，time字段存放该工作站的总加工时间。

4.6 B生产线优化结果

由于采用搜索算法得到了部分可行的作业加工顺序，从这些加工顺序中选出部分作为初始种群，因此本文的初始种群的规模可以调控。

在程序运行前，设置染色体的交叉概率为0.9，变异概率为0.1，设置种群的规模从50逐渐到20 000，遗传的代数从5 000逐步增加到50 000代；比较了各种运行结果，验证了遗传算法有很好的收敛性。最终优化结果如表6，最优的作业加工顺序如图7所示。

表6 各工作站作业分配表

图7 B生产线的最优作业顺序图

根据实验结果分析可知，平衡优化后B生产线的部分工序得到了重新分配，工作站的数量由15个减少到12个，各工作站实际操作的时间越来越趋于相等，生产线平衡损失率由原来的59%提高到80%，解决了生产线工序分配不合理的情况，平滑指数F为0.23，优化效果明显。B生产线的生产线平衡问题通过遗传算法优化得到了明显的改善。

5 结 语

本文针对L公司A和B生产线存在的问题进行了分析，应用C++程序语言分别编制遍历搜索算法与遗传算法，对L公司的两条不同的生产线进行了优化。实践表明，对于简单的生产线，可行的作业加工顺序较少，应用遍历算法能够快速准确地对生产线进行优化；对于复杂的生产线，由于可行的作业加工数量数目巨大，不可能进行完全遍历，而把遍历搜索的有限作业加工顺序作为种群，应用遗传算法能够快速地得到优化结果。通过对公司A和B生产线的平衡优化，也表明了遍历算法和遗传算法相结合的优化方法在生产流程优化方面的有效性和精准性。

[1] Becker C,Scholl A.A survey on problems and methods in generalized assembly line balancing[J].European Journal of Operational Research,2006,168(3):694-715.

[2] 邵仁玉.基于工业工程的生产线平衡与优化[J].机械设计与制造工程,2014(48):66-68.

[3] 邱伊健,涂海宁.基于Flexsim与遗传算法的混流生产线仿真与优化研究[J].组合机床与自动化加工技术,2015(8):119-123.

[4] 袁小兰,徐子奇,舒帆.基于遗传算法的发动机装配线平衡问题仿真及优化[J].物流工程与管理,2015,37(7):213-216.

[5] 刘环宇,夏吉庆,施灿璨,等.基于遗传算法对A公司生产线平衡的分析[J].物流技术,2014,33(9):367-370.

[6] 余晓光,严洪森.基于禁忌搜索遗传混合算法的装配线平衡[J].计算机技术与发展,2010,20(5):5-8.

[7] 范维博,周俊,许正良.应用遗传算法求解第一类装配线平衡问题[J].计算机技术与发展,2010,20(2):194-196.

[8] 扈静,蒋增强,葛茂根.基于改进遗传算法的混合装配生产线平衡问题研究[J].合肥工业大学学报,2010,33(7):1006-1009.

[9] 杨威,孟冠军,曹文钢,等.基于改进遗传算法的装配序列优化[J].机械传动,2016(9):67-70.

[10] 张子凯,唐秋华,张利平,等.改进遗传算法求解大规模混流U型装配线问题[J].机械设计与制造,2016(1):137-139.

[11] 吴伟云,乐天.遗传算法中选择算子的述评[J].福建电脑,2012(17):43-44.

[12] 徐学军,陆德谋,李文娇,等.生产线平衡与企业利润关系的研究[J].工业工程,2009,12(4):41-45.

OPTIMIZATIONOFPRODUCTIONLINEEQUILIBRIUMBASEDONTRAVERSALSEARCHALGORITHMANDGENETICALGORITHM

Fang Jingfang Xu Yankai
(SchoolofMechanicandElectronicalEngineering,LanzhouUniversityofTechnology,Lanzhou730050,Gansu,China)

Two kinds of production line of L Company were analyzed and the mathematical model of the each production line was established. The production line was optimized with the aim of minimizing the number of workstations and the load smoothing index. For the simple production line, all the possible job processing orders were found by traversing algorithm, and then the processing order with minimum number of workstations and minimum smoothing index was decided. For the complex production line, the genetic algorithm was used to find the best processing order, with the population from the traversal search algorithm. So the problem of production line balance in the L Company was solved. It is proved that the traversal algorithm and the genetic algorithm are very effective during the optimization of the production line.

Line balance Workstation number Traversal algorithm Genetic algorithm Production line optimization

2016-11-23。甘肃省科技支撑计划项目(1604GKCA020)。方景芳，教授，主研领域：生产流程优化，物流与供应链管理，系统建模与仿真。徐艳凯，硕士生。

TP311.11

A

10.3969/j.issn.1000-386x.2017.08.049