基于遗传算法对某公司装配线平衡的研究

Study on Assembly Line of a Company Based on the Genetic Algorithm

摘要: 为了解决装配线平衡这类NP-hard问题，要求将工序合理地分配到各工作站，使各工作站工时尽可能相等以有效地提高生产效率。以某公司遥控车装配线的现状为案例，依据装配线实际情况设置约束条件，建立了数学模型，提出运用遗传算法对装配线进行优化改进，设计了算法流程以及编码、变异、交叉、解码和选择操作，并运用MATLAB编程实现了该算法。并且提出了工作站负荷率折线评价指标，更好的反映出工作站装配能力的发挥空间和装配线平衡理想程度。装配线平衡率由原来的68.6%上升到93.3%，装配线损失率由原来的31.4%下降到6.7%，各工作站负荷率更加平稳，优化效果显著。研究结果表明遗传算法结合MATLAB编程解决装配线平衡问题是可行的、有效的，并且提出的工作站负荷率折线评价指标为装配线平衡问题的研究提供了参考依据。

Abstract: In order to solve the NP-hard problem of the assembly line, it is required to allocate the process reasonably to each workstation so as to make the working hours as equal as possible to effectively improve the production efficiency. Taking the status quo in a company car assembly line as a case, according to the actual situation, we set up an assembly line’s constraint conditions, established the mathematical model of applying genetic algorithm to optimize the new assembly line improvement, designed the process and coding algorithm, mutation, crossover, decoding and the choice of operation; and the algorithm was realized using MATLAB programming. Moreover, the evaluation index of the load index of workstation is proposed, which can better reflect the space of the workstation assembly capacity and the ideal degree of the assembly line balance. The assembly line balance rate increased from 68.6% to 93.3%, and the loss rate of assembly line decreased from 31.4% to 6.7%. The load rate of each workstation was more stable and the optimization effect was significant. Research results show that the genetic algorithm combined with MATLAB programming to solve assembly line balancing problem is feasible and effective, and the work station load rate index put forward for assembly line balancing problem provides a reference basis for the research.

1. 引言

制造业竞争激烈，装配生产线平衡问题早已是制造型企业的核心问题，如何快速响应市场需求是提高制造型企业竞争力的关键。因此，面对这一形势的唯一解决办法就是设计出科学化、现代化的装配生产线——解决企业资源优化配置 [1] 。如何在满足工序之间优先顺序和生产节拍给定的前提下组合分配各工序，使各工作站工时尽可能相等，这就是装配线平衡问题 [2] 。装配线平衡问题是典型的NP-hard问题，问题的复杂度随任务数的增加呈几何级增长，难以在合理的时间完全解决 [3] 。依据陈星宇 [4] 的总结，关于研究装配生产线平衡问题大致分为如下5类：1) 工业工程方法，如程序分析、操作分析以及动作分析等；2) 精确算法，如分支定界法、割平面法、整数规划以及动态规划等；3) 启发式算法，如Johnson启发式算法、CDS启发式算法以及NEH启发式算法等；4) 基于仿真的方法，如通常用的仿真软件有EM-power，Witness以及Flexin等；5) 人工智能算法，如神经网络、模拟退火以及遗传算法等智能求解方法。本研究运用遗传算法对装配线平衡问题进行规划求解。

2. 装配线平衡问题模型建立

本研究在某公司遥控车装配线已知生产节拍的基础上，求最优工作站分配。要求在满足工序间优先关系(图1)的情况下把生产工序合理地、有效地分配到每个工作站，使得整条装配线工作站的数量以及装配线平衡率达到最优。依据相关研究，装配线模型目标函数 [5] 可以表示为：

$\max f\left(x\right)=\frac{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{T}_i}}{m\times CT}\times 100\%$

其中： $T_i$ 表示第i个工序的时间；CT表示生产节拍；m表示工作站的数量。

依据装配线平衡率公式，装配线的瓶颈时间对整个装配线效率有较大影响。装配线在一定的作业周

Figure 1. The assembly procedure diagram of the telecare

图1. 遥控车装配工序关系图

期内完成一个产品，即生产周期，是由装配线上作业最长的工作站决定的，无论其他工作站作业速度多快也只能在瓶颈作业内传送产品。如果瓶颈时间过长会导致装配线上其它工作站停工待料，造成一定的工时损失与浪费成本。因此降低瓶颈工序标准作业时间，使装配线各工作站生产均衡是装配线平衡率提高的关键。

模型约束条件为：

1) $S_i\cap S_j=\varnothing$ ，( $i\ne j$ ； $i,j=1,2,\cdots ,m$ )即同一个工序不能被同时分配在不同的工作站中。其中 $S_i$ 表示第i号工作站， $S_j$ 表示第i号工作站， $\varnothing$ 表示空集。

2) ${\displaystyle \underset{k}{\cup }{S}_k}=E$ ， $k=1,2,\cdots ,m$ ，即一道工序只能被分配在一个工作站中， $S_k$ 表示第k号工作站， $E$ 表示全集。

3) $T\left(S_k\right)\le CT$ ，( $k=1,2,\cdots ,m$ )即各工作站作业时间不大于装配线的节拍。其中 $S_k$ 表示在符合优先关系矩阵A的前提下，各工序分配到第k个工作站的工序集合。

4) 作业元素优关系先矩阵： $A={\left(a_{ij}\right)}_{n\times n}$ 。

其中， $a_{ij}=\{\begin{array}{l}1作业元素i是j的直接先行元素\\ 0作业元素i不是j的直接先行元素\end{array}$

$A=\left(\begin{array}{cccccccccccc}0& 1& 1& 1& 1& 1& 1& 1& 0& 0& \cdots & 1\\ 0& 0& 1& 1& 1& 1& 1& 1& 0& 0& \cdots & 1\\ 0& 0& 0& 1& 1& 1& 1& 1& 0& 0& \cdots & 1\\ 0& 0& 0& 0& 1& 1& 1& 1& 0& 0& \cdots & 1\\ 0& 0& 0& 0& 0& 1& 1& 1& 0& 0& \cdots & 1\\ 0& 0& 0& 0& 0& 0& 1& 1& 0& 0& \cdots & 1\\ 0& 0& 0& 0& 0& 0& 0& 1& 0& 0& \cdots & 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& \cdots & 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& \cdots & 1\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& \cdots & 1\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& 0& 0& 0& 0& 0& 0& 0& \cdots & 0\end{array}\right)$

3. 装配线平衡遗传算法设计

遗传算法(Genetic Algorithm，简称GA)是以生物遗传和进化机理为基础，从问题域可能潜在解集的一个种群开始，将可能解看做是群体的染色体或个体，并将每一个染色体进行编码操作，模拟生物进化过程对群体反复进行遗传、变异与交叉的操作。根据适应度函数对染色体进行评价，同时以全局并行搜索方式来搜索优化群体中的最优染色体，以求得满足要求的最优解 [6] 。图2是本研究规划的遗传算法流程图。

3.1. 编码

编码是应用遗传算法时首要解决的问题，针对不同的问题有不同的编码方式。遗传算法的运用过程中，编码的优劣对选择、交叉、变异等遗传操作有直接影响。本研究采序列编码方式：n个工序则编码的长度为n，基因1至n的整数按照顺序排列。如n = 5，则一个合法的染色体可以表示为如图3。

Figure 2. Flow chart of genetic algorithm

图2. 遗传算法流程图

Figure 3. A legal chromosome

图3. 一个合法染色体

3.2. 初始种群

根据编码方式，采用随机法产生初始种群。

3.3. 变异

变异是以小概率发生在少数基因位上的变化，它决定了遗传算法的局部搜索性能，避免收敛于某一局部最优解。本研究的变异操作采用两点互易方法，这种变异操作的实现较为简单，能提高运算效率，步骤如下：Step 1，随机产生两个自然数r1、r2；Step 2，交换第r1位和r2位的基因。如r1 = 2，r2 = 4时，染色体变异操作如图4所示。

3.4. 交叉

交叉是按照较大概率从群体中选择两个染色体，交换两个染色体某个或某些部位来获得新染色体，从而推动整个群体进化。本研究采用两点交叉法，步骤如下：step 1，随机选择两个染色体作为父代染色体；step 2，在1到n之间随机产生2个自然数r1和r2；step 3，交换两个父代染色体r1至r2之间的基因片段获到两个子代染色体，为避免子代染色体冲突进行修订处理。如r1 = 2，r2 = 4时，染色体交叉操作如图5所示。

3.5. 解码

本研究解码操作是依据工序约束对编码进行转换，然后依次安装节拍约束将工序填入各个工作站中，将染色体转换成满足适应度的值。问题可以划分两个部分：求工作站数和装配线平衡率，首先在给定生产节拍的条件下，根据工序之间优先关系求得工作站的工序划分，同时得到工作站数；其次，根据工作站上工序的划分求得工作站工作总时间计算装配线平衡率。

Figure 4. Mutation operation

图4. 变异操作

Figure 5. Cross operation

图5. 交叉操作

3.6. 适应度函数

适应度函数是用来表明染色体或解的优劣性，是进行自然选择的唯一标准。在遗传算法中针对目标函数制定出适应度函数来衡量群体中各个染色体的优良。适应度较优的染色体遗传到子代的概率就较大；而适应度较差的染色体遗传到子代的概率就相对小。本研究的目的为达到装配线平衡率最优，因此选用上述的装配线平衡率作为适应度函数。

$F\left(p\right)=\frac{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{T}_i}}{m\times CT}\times 100\%$

3.7. 选择操作

选择操作依据各个染色体的适应度的大小进行选择，本研究的选择策略采用轮盘赌选择法 [7] ，以各个染色体的选择概率与其适应度成正比为原则，适应度较优的染色体遗传到子代的概率就较大；而适应度较差的染色体遗传到子代的概率就相对小。设种群数量为t，种群中第i个染色体适应度为 $f_i$ 。选择操作的步骤如下：

Step1，计算种群的总适应度： $F=\underset{i=1}{\overset{t}{{\displaystyle \sum }}}{f}_i$ ；

Step2，计算第i个染色体被选择的概率： $P_i=f_i/F$ ；

Step3，计算第i个染色体的概率累积： $P_{s,i}$ ；

Step4，取0至1之间的随机数a，若 $a\le P_{s1}$ ，则第一个染色体被选择；否则，若 $P_{s,i-1}\le a\le P_{s,i}$ ，则第i个染色体被选择；

Step5，重复步骤(4)直到选择到第t个染色体结束。

4. 某公司装配线平衡现状分析

某生产制造型公司成立于2014年，规模达到中型水平。公司在成立的第二年通过了国际质量体系的相关认证，公司在产品研发上独立自主并拥有该公司自己的设计技术体系，同时具备生产制造能力，公司主要产品是遥控车。该公司通过程序分析将遥控车的装配分为21个步骤，每一个步骤就是一道工序，也是最小的装配作业要素，并规定各工序间的紧前工序，即工序间的优先关系，通过时间测定的方法规定各工序的标准作业时间。遥控车装配步骤与工序时间见表1。

该公司为了完成装配遥控车的一道或者多道工序，在装配线指定一个工作位置，工人在其中进行操作，这个位置就是工作站，每一个工作站由1~3名工人操作。该公司根据遥控车装配线的实际要求，将21道工序分配到8个工作站。该公司的这种分配方式在实际运用中并没有考虑到工站间的生产能力是否均衡，这种规划造成了在生产时间上浪费同时使公司在费用上造成了不必要的开支。所以本研究针对该公司遥控车装配线平衡问题进行分析改善。遥控车装配线工序分配现状与工作站负荷率见表2。

通过表2可知，第1、2、3道工序分配到了1号工作站，负荷率为0.7；第4、5道工序分配到了2号工作站，负荷率为0.823；第6、7、8道工序分配到了3号工作站，负荷率为0.823，同理可知其他工序分配情况与工作站负荷率。

表2中工作站4工作总时间最长，工作总时间为68 s，是遥控车装配线的生产瓶颈同时也是该装配线的生产节拍。生产瓶颈主要指的是在整个生产节拍中耗时最长的工作站，生产瓶颈不仅制约了整个装配线的产出速度，而且会影响道装配线其他工作站装配能力的发挥。

图6中横坐标表示各工作站，纵坐标表示各工作站的负荷率。工作站负荷率越低表示工作站装配能

Table 1. Telecar assembly procedure and process schedule

表1. 遥控车装配步骤与工序时间表

Table 2. Status of process distribution and load rate of workstations

表2. 工序分配现状与工作站负荷率

Figure 6. The load line of telecar loading rate

图6. 工作站负荷率折线图

力发挥空间越大，各工作站之间的负荷率数值越平稳，装配线平衡越理想。通过图6工作站负荷率折线图可看出，各工作站负荷率折线呈现不平稳的状态，说明装配线平衡不理想；第5号、6号、7号、8号工作站负荷率偏低，通过科学的工序与工作站分配，装配能力提升空间很大。

其中各工作站负荷率 = $\frac{T\left(S_K\right)}{CT}$ ，( $k=1,2,\cdots ,8$ )。 $T\left(S_K\right)$ 表示第k号工作站总时间，CT表示生产节拍。

依据装配线平衡率公式得到该公司遥控车装配线的装配线平衡率为68.6%，平衡损失率为31.4%。有相关研究 [8] 表明装配线平衡率和企业利润之间的关系在不同阶段呈现着不同的关系：装配线平衡率在89%之前，利润呈现增长趋势；装配线平衡率在89%至97%之间，利润基本呈现平稳的趋势；装配线平衡率高于97%时，利润会呈现下降趋势。该公司装配线平衡率在68.6%，对企业利润有很大的提升空间。

5. 运用Matlab2014a编程求解

本研究基于遗传算法对某公司遥控车生产装配线平衡问题建立模型，在满足工序间优先关系与生产节拍的前提下，对各工序的先后顺序与工作站分配进行调整。并通过Matlab对该模型进行编程求出最优解，在编程中设置生产节拍不大于68，初始种群为50，种群交叉概率为0.7，变异概率为0.1，迭代后结果见图7与图8。

如图7所示，图7的横坐标表示迭代次数，纵坐标表示装配线均衡总目标，即装配线平衡率。本研究运用遗传算法通过设置迭代次数为100，得到装配线平衡率数值为0.933。通过观察图中曲线可知，在迭代次数为18后曲线数值稳定在0.933，达到最优装配线平衡率。

如图8所示，图8的横坐标表示工作站数量与序号，纵坐标表示工作站的工作总时间，直方图中的序号表示21个工序分配到工作站的情况。例如，通过图8可以看出依据遗传算法的执行将21的工序分配到8各工作站中，其中第1号工作站分配有第1、2、9道工序，并且总时间为50 s；第2号工作站分配有第3、4道工序，并且总时间为48s；第3号工作站分配有第6、10、11道工序，并且总时间为48 s。

通过表3分析可知：各工作站得到了重新分配，被安排在各个工作站的工序更加合理。装配线平衡率显著提高，由原来的68.6%上升至93.3%，装配线平衡损失率也由原来的31.4%，下降至6.7%；工

Figure 7. Genetic algorithm iterative curve

图7. 遗传算法迭代曲线

Figure 8. Process allocation

图8. 工序分配情况

作站总时间最大为50 s，因此改善后的生产节拍由原来的68 s缩短至50 s。根据图9改善后的工作站负荷率折线图可以看出，改善后的各工序负荷率较为平稳。通过对遥控车装配线的优化，各工作站的工作时间与工作站负荷率更加平稳，有效的提高了设备的利用率。

6. 结论

本研究基于遗传算法，针对某公司遥控车装配生产线现状建立数学模型，设计了遗传算法流程以及编码、变异、交叉和选择操作，并运用matlab2014a编程求解，使装配线平衡率由原来的68.6%上升到93.3%，装配线损失率由原来的31.4%下降到6.7%，各工作站负荷率更加平稳，优化效果显著；本研究

Figure 9. Improved workstation load rate line chart

图9. 改善后的工作站负荷率折线图

Table 3. Improved process allocation and workstation load rate

表3. 改善后的工序分配与工作站负荷率

验证了遗传算法结合MATLAB编程在解决装配线平衡问题上的可行性和有效性，同时验证了遗传算法在该领域上具有实际意义；提出的工作站负荷率折线评价指标更好的反映出工作站装配能力的发挥空间和装配线平衡理想程度，为装配线平衡问题的研究提供了参考依据。

基金项目

哈尔滨市科技创新人才研究专项资金项目(2014RFXXJ108)。