基于装配关系复杂性测度的多目标混流装配线平衡优化

张志颖，刘 鑫，聂迎春

（河北工业大学 经济管理学院，天津 300401）

0 引言

装配线平衡问题(Assembly Line Balancing Problem，ALBP)是运用优化方法，在工序优先关系和节拍等约束条件下将工序合理分配到工作站，使线上运营和生产系统流畅合理[1]。当前，市场需求正向着个性化和多元化的方向发展，产品的多样化和规模化对制造企业的产能提出了新的要求。为提高企业产能，装配线的平衡问题受到了国内外学者的广泛关注与研究。随着制造系统逐渐趋向于智能化和柔性化，装配线系统也变得更加复杂。国内外学者对装配线平衡的研究也从单品种到混流[2～4]，从简单的设备、工艺、工人三方面演变成要额外考虑物料供应[5]、产品需求[6]、能源消耗等[7]不确定性因素的复杂系统。复杂的装配线系统不仅包含更多的工序，其工序间的装配关系也蕴含着更大的信息量[8]。这说明在装配线平衡研究过程中，仅考虑线上工人操作等因素对生产效率和成本的影响只能保证装配线局部最优。因此，需要探究装配关系的复杂性对装配线的影响，量化系统的不确定性，以提供更具实践意义的解决方案。

制造系统复杂性指制造系统难以被理解、描述、预测和控制的状态，可分为结构复杂性、过程复杂性和控制复杂性[9]。相关研究多集中于运用信息熵进行复杂性测度和从宏观上构建制造系统中各类复杂性的理论框架。如Fujimoto[10]针对装配多个阶段设置相应的复杂性，运用信息熵对其进行度量；Sivadasan等[11]基于供应商-客户系统操作操作复杂性，提出一种测量供应商-客户系统信息需求的方法，并从信息论角度对该系统操作复杂性建立数学模型求解。何非等[12]将制造系统复杂性中结构复杂性进一步划分成装配关系复杂性、装配工艺复杂性和系统配置复杂性，并以最小装配关系复杂性差异度为优化目标建模求解。Efthymiou等[13]则对制造系统复杂性的建模方法进行了综述，分析制造系统复杂性对生产过程产生的影响。

直到近几年，关于制造系统运行优化的研究逐渐增加，更多学者开始深入研究实际生产过程中复杂性对装配系统的影响。赵小松等[14]将工作站装配复杂性作为人员疲劳等因素的诱因，以最小化装配系统复杂性为优化目标建立模型并求解，提升工作站可靠性。刘亮等[15]发现并行装配过程在实现产品多样化的同时，制造复杂性则随之提高，为解决该矛盾，提出考虑制造复杂性优化和顾客选择的并行装配系统设计方法。刘雪梅等[16]指出装配过程中的不确定性会导致操作时间波动，于是基于信息熵提出工位复杂度度量方法，建立操作时间不确定的数学模型，减少不确定性因素干扰的同时平衡工位复杂度。李爱平等[8]提出了新的装配关系复杂性度量方法，基于此建立多目标装配线平衡优化模型，运用模糊聚类算法改进求解的遗传算法交叉环节，从装配关系复杂性角度提高装配线效率。

可见，上述研究将复杂性引入装配线平衡优化问题中，探究多种因素对装配线系统的影响并建模求解，提升装配线的可靠性。但针对混流装配线平衡问题，考虑结构复杂性中装配关系复杂性对生产效率影响的研究较少，而且缺乏对装配关系复杂性度量方法的研究。

因此，本文考虑装配关系复杂性对混流装配线平衡的影响，基于信息熵提出混流装配线装配关系复杂性的度量方法，然后以生产节拍、装配线平滑指数、装配关系复杂性平滑指数建立一个多目标混流装配线平衡优化模型，并运用第二代非支配排序遗传算法（Nondominated Sorting Genetic Algorithm 2，NSGA 2）求解。最后，结合某公司泵体混流装配线实例分析验证优化方法，为该问题在企业实际工程中应用提供参考。

1 问题描述

Becker等[17]认为装配线平衡问题主要分为四类，生产节拍一定，最小化工作站的数量；工作站数量一定，最小化生产节拍；生产节拍和工作站数量一定，求装配线可行解；生产节拍与工作站数量待定，求装配线可行解。本文研究属于第二类装配线平衡问题，工作站数量不变，最小化生产节拍。

装配关系复杂性描述装配产品所需要开展的各项任务及其任务之间关系复杂性的程度，其大小取决于产品装配任务的数量及其各任务间的先后顺序关系[12]。可见，装配线上各个工作站作业之间的排序和数量均会影响该工作站装配关系复杂度。若某工作站中装配关系复杂度越高，则产品的装配过程越繁琐，一定程度上提高了工人的劳动强度，且当装配过程出现错误时，将耗费更多的时间和精力检查问题工序的来源。因此需要量化装配关系复杂性，使各工作站负荷均衡，减少装配错误。

单产品装配线可根据工艺流程画出作业优先关系图，从而分析得到作业之间的装配关系。混流装配线则需要将线上所有产品的作业按优先关系综合为一个联合作业优先关系图，继而得到作业之间的装配关系。混流装配线上生产的多种产品工艺相似，但具体工序会有差异，需要将三个产品的作业优先关系图综合为一个联合优先关系图，如图1和图2所示。然后根据产品各自订单数dj占总订单数D的比例，求解出联合优先关系图中作业n的时间ti为：

图1 三种产品优先关系图

图2 联合优先关系图

其中tij是每个产品各自作业的时间，i=1，2，3，…，n，j=1，2，3。若某产品工序不包含某个作业时，在计算该产品作业时记为零，这样混流装配线平衡问题便转化为单一产品装配线平衡问题。

2 模型构建

2.1 装配关系复杂性度量

当前关于装配关系复杂性度量方法的研究主要有两类：一类在梳理各作业先后顺序关系过程中，仅考虑直接前序、间接前序和并序对当前作业装配关系复杂度的影响，忽略了后序与当前作业的装配关系，并且该方法把每个作业自身装配关系复杂度加入其后序作业装配关系复杂度的计算，导致越靠后的作业复杂度越高，这与实际装配线情况不相符[12]。另一类充分考虑前序、并序和后序对当前作业装配关系复杂度的影响，但前序和后序作业中均存在直接和间接从属两种关系，需要加以区分[8]。因此，本文综合考虑直接前序、间接前序、并序、直接后序、间接后序对当前作业影响，给出装配关系复杂性的度量方法。

设装配线产品任意作业为i，共有n个作业。构成所有作业之间装配关系的集合为G={g1，g2，g3，g4，g5}，其中g1=当前作业直接前序，g2=当前作业间接前序，g3=当前作业的并行工序，g4=当前作业直接后序，g5=当前作业间接后序，该装配关系集合可以表示作业在优先关系中的位置特征。

信息熵，作为研究制造系统复杂性度量最重要的手段之一，可用于对一个系统中所包含的信息量和不确定性进行度量。而复杂度是复杂性一个基本特征，一定程度上可用不确定性的测度来表示[18]。因此，本文用信息熵来描述各作业间装配关系复杂程度。当前作业5种装配关系各自的数量占总装配关系数量的比例分别表示为{p1，p2，p3，…，ph}，即p1=g1/(g1+g2+g3+g4+g5)，p2=g2/(g1+g2+g3+g4+g5)，p3=g3/(g1+g2+g3+g4+g5)，p4=g4/(g1+g2+g3+g4+g5)，p4=g4/(g1+g2+g3+g4+g5)，则反映第i个作业装配关系复杂性的信息量为：

其中概率元素ph≥0，，，对数一般取2为底，单位为比特，也可取其他对数底，使用相应的单位。本文对数计算取2为底。

2.2 平衡模型的建立

2.2.1 模型参数

模型的参数和决策变量符号如下：

C为节拍；

n为作业总个数；

N为工作站总数量；

ti为联合作业图中第i 个作业的标准作业时间，i=1，2，3，…，n；

Pre(i)表示作业优先关系集合，先于任务i完成得任务集合；

Hi为第i个作业装配关系复杂度；

H(k)为第k个工作站装配关系复杂度总和，k=1，2，3，…，N；

h为作业间装配关系指数；

ph为作业间不同装配关系占总装配关系数量的概率；

m为混流装配线产品种类；

D为混流装配线产品总订单数；

dj为产品j的订单数量，j=1，2，3，…，m；

tij为j产品第i个作业的标准作业时间；

Gq为种群中第q个个体工作站数量；

P为种群规模；

2.2.2 目标及约束

依据参数和定义可知，第k工作站各作业装配关系复杂度之和为：

本文考虑到各个工作站装配关系复杂性的平衡会影响工人作业效率，降低负荷，提高产品的一次通过率。除最小化生产节拍外，额外加入最小化装配线平滑指数和装配关系复杂度平滑指数[8]为优化目标，可以使装配关系复杂度均衡分配，得到三个优化目标如下。其中最小化生产节拍为：

最小化各个工作站负荷的装配线平滑指数为：

最小化装配关系复杂性平滑指数为：

混流装配线平衡的约束如下：

其中约束(7)是工作站数目不变；约束(8)是每个工作站的总作业时间不能超过生产节拍；约束(9)是每个作业只能分配一次，不可再次分配；约束(10)是各个作业分配过程中必须满足装配的优先关系；约束(11)是作业在工作站分配情况的0/1型决策变量。

3 基于NSGA 2的模型求解过程

3.1 算法流程

本文采用NSGA 2[19]设计求解优化模型。在求解过程中，发现得出的优化方案类型较少，未能完全搜索装配线作业任务的分配情况，为了更好的进行全局搜索，采用类PMX[20]（Partially Matched Exchange）的交叉方式，提高种群多样性，避免过早产生局部最优解。算法具体流程图如图3所示。

图3 NSGA2算法流程图

3.2 编码、初始化种群和交叉变异

本文涉及的混流装配线平衡问题属于JSP问题，需要对作业进行排序，因此编码采用排列编码法更为简单可靠。每个作业对应一个基因位，按照优先关系将n个作业排成一排，N-1个分割点按升序排列到作业之后，组成长度为n+N-1的染色体。其中后面N-1个基因是工作站之间的分割点，可表示当前分配作业的数量。解码则将染色体按照节拍约束和作业排列顺序分配到各个工作站。

初始化种群过程则产生作业随机序列，根据联合优先关系图，对作业进行选择和优先关系检查，将符合优先关系的作业加入集合I中。若选择的作业已经在集合I中，则重新选择作业。

为了提高种群多样性，交叉过程采用类PMX的交叉方式。与传统PMX方法中直接交换染色体交叉部分不同，类PMX则是将A、B两个染色体各自的交叉部分分别放到对方染色体之前，并将A染色体剩余部分和B染色体交叉部分、B染色体剩余部分和A染色体交叉部分进行比对，若有和交叉部分相同的则删除，过程如图4所示。

图4 类PMX交叉过程

变异过程采用倒位变异方式，即在一个染色体上随机选择两个变异点，变异点之间的区域为变异区域，将变异区域倒序排列得到新的变异个体。如在染色体（1 3 |5 8 9 2 6| 7 4）上随机两个变异点为5和6，则将包括5和6之间的区域倒序，变异后染色体为（1 3 |6 2 9 8 5| 7 4）。

4 实例分析

4.1 案例数据

以某液压泵混流装配线为例进行装配线平衡优化，验证本文优化方法的有效性。该混流装配线具有完备的工装和电子设备，但部分工序操作复杂，工作站时间差异较大，且时常出现装配错误导致产品重装或报废的问题，需要优化线效率和产品质量。整个装配线共包含3种产品，65个作业任务，分配到11个工作站。本文选取一个订单周期，根据订单需求计算标准作业时间，并绘制联合优先关系图如图5所示。由于整条产线作业任务数量较多，工艺顺序较复杂，人工得出优化方案较为困难，有必要结合模型优化得到分配方案。

图5 联合优先关系

根据联合优先关系图和式(2)可得各作业任务装配关系复杂度，如表1所示。三种产品订单需求比例为3∶1∶1，结合产品各自作业时间，用式(1)可求得各个作业任务的作业时间如表2所示。

表1 作业任务装配关系复杂度

（续）

表2 作业任务时间

通过式(4)～式(6)计算可得当前混流装配线的生产节拍为596.2s，装配线平滑指数SI≈58.0，装配关系复杂性平滑指数为HSI≈26.5。

4.2 优化结果分析

通过以上数据收集，建立多目标数学模型，用MATLAB2019编程求解。其中NSGA 2算法的参数初始值设定如下：由于作业任务数量很多，设置种群规模P=200，迭代次数M=800，交叉概率Pc=0.7，变异概率Pm=0.3。初始节拍设置为C=680，给予适当的优化空间。经过计算得到优化后的Pareto前沿如图6所示。图上每一个点代表一个Pareto解集，对应三个目标函数值，每个解都至少在一个目标上优于现有方案。目标函数值随迭代次数优化的过程分别如图7～图9所示。从图中可看出，随着遗传代数的增加，三个目标的函数值都明显降低，之后趋于平稳。

图6 Pareto最优前沿解集

图7 生产节拍进化过程

图8 装配线平衡指数进化过程

图9 装配关系复杂性进化过程

通过计算得到数个Pareto解集后，需要简单的人工选择最优解。在所有的优化方案中，综合考虑生产时间，各个工作站之间的负荷差异度，选择C=499.6s，SI≈29.2，HSI≈12.0为最优分配方案，其作业任务分布图如图10所示。与现有方案C=596.2s，SI≈58.0，HSI≈26.5相比，三个方面均有所改进。

图10 最优方案作业任务分布

5 结语

本文为了进一步平衡工作站负荷、提高混流装配线的作业效率，选取装配制造系统中装配关系复杂性的特征，基于信息熵给出装配关系复杂性的度量方法，将复杂性这一抽象的概念定量化，以生产节拍、装配线平滑指数和装配关系复杂性平滑指数为优化目标，建立多目标混流装配线平衡优化模型，并运用NSGA2进行设计求解。通过实例分析可知本文提出的基于装配关系复杂性的多目标混流装配线平衡优化方法可以有效降低生产节拍，减少各工作站之间作业时间和工作负荷的差异，使各工作站装配关系复杂性均衡，实现混流装配线的平衡。后续可进一步考虑装配工位复杂度对装配系统生产效率和产品质量的影响。