某汽车座椅混流装配线多目标排产优化

姜兴宇，李世磊，田志强，邓健超，韩清冰，刘伟军

(沈阳工业大学 机械工程学院，沈阳 110870)

汽车座椅作为典型的面向订单的多品种大批量产品，其装配线常常处于多型号、多状态、多批次同时在线的混流状态，不同装配工艺频繁切换、不同座椅生产节拍差异大，导致装配周期长、资源利用率低.因此，如何在规定时间内满足不同客户订单需求，提高装配线资源利用率，缩短产品装配时间，提高装配线产能已经成为汽车座椅混流装配线排产优化的核心问题.完工时间与等待时间是研究混流装配线排产问题的经典指标，其长短已成为混流装配线能否保质保量地完成主机厂订单的关键，实际生产过程中考虑产品装配完工与等待时间，既能提高混流装配效率，及时满足客户多样化订单的需求，又能平衡工作站的负载，合理安排生产计划，使其更加符合企业的生产实际.因此，面向订单的汽车座椅排产优化问题的研究具有重要的应用经济价值.

混流装配线排产问题是通过调整产品投产序列以协调生产、提高混装线生产效率的复杂多目标组合优化问题，一直是生产运作和组合优化领域的热点[1-2].1963年，Wester等[3]首次提出混流装配线的排产问题，随后的几十年中，该问题已被证明是组合优化问题中非确定多项式困难问题(non-deterministic polynomial hard problem，NP-hard)，具有计算复杂性高、求解难度大等特点.该算法是求解混流装配线排产问题的重要组成部分.提升算法的求解效率，优化算法求解机制，设计适用于此类问题的高效优化方法，是研究混流装配线排产问题的重要内容.

Ishigaki等[12]构建了以最小化总未完成工作时间为目标的排产优化模型，并提出了适用于该模型求解的改进模拟退火算法；Tahriri等[13]构建了以最小化完工时间和最小化装配数量为优化目标的混流装配线排产模型，并提出了一种改进的遗传算法——模糊自适应遗传算法进行求解；蒙秋男等[14]研究了按工作日历组批、零部件配套约束下的混流装配线排产方案，以最小化完工时间、总提前拖期、总加班时间为目标构建排产优化模型，并设计了空间蚁群算法求解，通过实例验证了排产方法的有效性；韩忠华等[15]构建了以产品完工时间、等待时间、空闲时间等为优化目标的排产模型，设计了一种改进紧致遗传算法求解该问题；李燚等[16]构建了以瓶颈工位负载平衡、最小化工位加工滞后次数为目标的优化模型，提出一种改进蚁群算法进行求解，有效提高了求解过程中解的收敛速度及精度；张炜等[17]以订单紧急度、匹配度和负荷均衡为上层目标，以工位空闲及产品等待时间为下层目标，构建了多目标主从关联优化模型，设计一种结合Pareto前沿解的双层交互式遗传算法求解该模型，结果验证了所提模型及算法的有效性.

综上，学者们已经从排产模型构建、提高算法求解性能等方面对混流装配线排产问题进行了系列研究，取得了一定成效，但还尚不完善，仍存在以下问题：

1)汽车座椅混流装配线装配产品种类多、批量大、不同工艺频繁切换，导致排产模型的建立及资源约束更为复杂，实现统筹考虑产品完工时间和等待时间的优化目标极为困难.而现有大批量混流排产问题的研究较少考虑产品完工时间与等待时间的协同优化冲突，导致装配线生产资源浪费.

2)在求解工艺复杂的多目标排产优化模型时，对求解算法的寻优能力、种群多样性要求较高，传统优化算法如遗传算法等由于进化策略简单、灵活性较差，会出现搜索速度慢且容易陷入局部最优的问题，从而很难获得理想的排产优化方案.针对多目标优化问题，评价方法的科学性、客观性也决定着最终的优化效果.因此，如何提高算法的求解性能并结合科学、客观的评价手段以获取全局最优解是多目标排产优化问题的重点.

基于此，本文针对汽车座椅多批次、大批量混流装配、工艺及节拍差异大导致装配线资源利用率低、交货期长、难以满足主机厂需求等问题，以汽车座椅混流装配最小等待时间和完工时间为目标，设计了一种改进快速非支配排序遗传算法(non-dominated sorting genetic algorithm Ⅱ，NSGA-Ⅱ)对排产模型进行求解，应用改进的灰色关联分析(grey relational analysis，GRA)与理想点接近法(technique for order preference by similarity to an ideal solution，TOPSIS)混合评价方法，对所得Pareto最优解集进行评价，得到最优的排产方案.通过实例分析，验证本文所提模型及算法的有效性和实用性.

1 多目标混流装配排产问题

1.1 问题描述

混流装配线的排产问题主要是根据客户对不同类型产品的需求量，确定产品间的排产顺序，从而满足客户需求的问题.本文研究假设混流装配线已完成平衡设计及改善，优化目标的选取仅考虑排产问题.在静态环境下，混流装配线排产问题可以描述为：在计划完工时间T内生产M种批量为im的不同类型产品i(i=1，2，…，M)，产品i需要按设定的排产顺序依次经过m个工位k(k=1，2，…，m)，通过N道装配工序Uj{j=1，2，…，N}的加工，消耗装配时间tirj{i=1，2，…，M，j=1，2，…，N}完成各道工序的装配，各类型产品可以以任意投产顺序依次装配，而不同类型产品的装配流程及各工位的装配时间均不同，同时可以组成多种排产方案.最后从全局角度研究，将M种产品按固定的比例设定排产顺序，合理安排产品的装配，为企业确定最优的投产顺序，使得排产方案满足一个或多个生产指标要求.

为了解决混流装配线排产问题，需要满足如下的假设条件：1)不同产品的相同任务分配到同一个工作站；2)假设产品装配工序需要的物料都可以连续供应，不存在因物料不足而等待的现象；3)装配线上的产品装配按照先进先出原则进行；4)每一个装配工艺的操作时间是确定的.

为能够在规定时间内满足客户多样化订单，优化混流装配线上产品的投产顺序，并减少在制品在线上的库存成本和人工闲置浪费的成本，同时减少总装配时间，本文排产优化模型的目标定为完工时间和产品等待时间最小.

1.2 优化目标

1.2.1 相关参数及含义

模型中涉及的相关参数及含义如表1所示.

表1 模型中相关参数及含义

1.2.2 目标函数

目标函数设为最小生产单元里所有产品完成装配时的完工时间和产品等待时间最小，即

f=min(T完工，T等待)

(1)

1)完工时间目标

完工时间反映了混流装配线的生产能力，其长短成为混流装配线能否及时满足客户多样化订单需求的关键，其表达式为

T完工=max ETirjk

(2)

2)等待时间目标

当上一个产品在工位进行装配时，下一个产品已经进入该工位，需要等待上一个产品完成作业后才能进行装配，这段时间就是产品的等待时间，其表达式为

(3)

1.2.3 约束条件

目标函数的相关约束条件为

ETijk=BTijk+imtirjk(r=1，2，…，im；j=1，2，…，N)

(4)

(5)

BTirjk=max(ETir(j-1)k，ETi(r-1)jk) (r=2，3，…，im；j=2，3，…，N)

(6)

(7)

(8)

式(4)表示第i个产品在第j个工作站上结束装配时消耗的总时间等于装配消耗时间与第i个产品在第j个工作站上开始装配时消耗的总时间之和；式(5)表示各个工作站的总装配时间小于理论生产节拍；式(6)表示投产中第i个产品在第j个工作站上开始装配时消耗的总时间等于第i个产品在第j-1个工作站上结束装配的时间和第i-1个产品在第j个工作站上结束装配的时间中的较大值；式(7)表示一个工位同一时间只能装配一个产品；式(8)表示任意一个工位的装配时间等于该工序装配M种产品的装配时间的加权平均值.

2 算法设计

具有多品种大批量复杂工艺特征的混流装配线排产问题是典型的NP-hard问题，相对于传统流水装配线排产问题，具有装配工艺复杂、目标约束多、求解难度高等特点.在求解此类问题时，智能优化算法是目前求解混流装配线排产问题的一种主要方法，与整数规划、分支定界等精确方法相比，无论在求解速度还是解集质量方面均表现出了更好的特性.但传统的优化算法如遗传算法、模拟退火算法等由于寻优能力不足、进化策略简单，难以获得理想的优化方案[18].NSGA-Ⅱ是Deb等[19]提出的一种元启发式算法，由于其在求解低维问题时具有良好表现，并且求解速度相对较快、容易实现，因此被众多学者应用于求解多目标装配线排产问题.然而，传统NSGA-Ⅱ算法由于采用模拟二进制编码方式，计算拥挤度时未考虑某个淘汰解对邻域解拥挤距离的影响，导致其在求解更加复杂的多品种大批量复杂工艺特征的混流装配线排产问题时速度慢，Pareto解集质量差.因此，本文针对混流装配线排产的实际问题，设计一种改进NSGA-Ⅱ算法用于模型求解.根据不同型号汽车座椅需求量在一个最小循环周期内的投产比例，提出了一种基于最小投产比例的实数编码方法，提高了算法的解码效率；采用一种基于产品的OC(order crossover)交叉策略及多点变异策略，在保证算法种群多样性的同时提高了算法搜索效率；应用一种循环拥挤排序的精英选择策略，避免淘汰解对邻域解拥挤距离的影响，提高算法的收敛速度和鲁棒性，并保证了非劣解的均匀分布.改进NSGA-Ⅱ算法流程如图1所示.

图1 改进NSGA-Ⅱ算法流程

2.1 编码操作及种群初始化

采用基于产品最小投产比例的实数编码方式对染色体进行编码，其长度由最小循环周期内的所有待装产品总数决定，一个基因代表一个产品，目前A、B、C、D、E、F六种座椅需求量为40、40、160、160、120、120，则A、B、C、D、E、F六种座椅在一个最小循环周期内的投产比例为1∶1∶4∶4∶3∶3，编码方式为ACCCDDCBEEDDFFEF，满足编码条件的个体随机分配组成初始种群.

2.2 交叉与变异

基于产品最小投产比例的实数编码后基因与产品一一对应，而且基因由实数表示，故有较大概率在不同基因位置出现相同产品，因此交叉操作选择应用基于产品的OC交叉策略，提高种群的多样性.在初始种群中随机选择两个染色体，作为父代染色体1、2，并将其等分为头部和尾部两部分，在父代1中按照基因排列顺序挑选出与父代2尾部相同的基因，构成子代的头部，子代的尾部为父代2的头部基因，随即产生子代染色体，如图2所示.

图2 交叉操作

在进行变异操作时，采用多点变异策略.在父代基因中任意选取不小于2个基因，保留剩余基因，在相同位置将选中的基因按照先后顺序进行倒序，由此组成变异后的子代，如图3所示.

图3 变异操作

2.3 精英选择策略

整合新生成的子代与父代个体Pareto解，并将其看做一个新的种群，计算新种群中每一个个体拥挤距离；删除新种群中拥挤距离最短个体并重新计算剩余个体拥挤距离；判断剩余个体数是否满足需求，循环删除，直到满足个体数量要求结束算法并输出最优个体集[20].

2.4 基于改进GRA与TOPSIS方法的最优解选取

Pareto最优解集法是一种公认的多目标优化问题的有效求解方法[21].在通过改进NSGA-Ⅱ算法的混流装配线排产优化得到一组Pareto解集后，决策者还面临如何从这组Pareto解集寻求出最满意方案的问题.常见的多目标决策方法有：加权和方法、字典序法、层次分析法、熵值法、数据包络方法(data envelopment analysis，DEA)、多维偏好分析的线性规划方法(linear programming techniques for multidimensional analysis of preference，LINMAP)、TOPSIS法、GRA等.TOPSIS法是通过检测评价对象与最优解、最劣解的距离来进行排序，其结果能精确地反映各评价方案之间的差距，但忽略了各方案的变化趋势，而GRA是运用各个影响因素的样本数据来计算灰色关联度，能够准确分析因素之间的关系，在分析变化趋势和发展态势时有着较强的性能.因此，本文采用一种GRA与TOPSIS的混合评价方法，将静态距离和动态趋势结合起来，对所得Pareto最优解集中排产方案进行评价，具体实施步骤[22]如下：

1)构造向量归一标准化矩阵.对于具有n个评价指标的q个对象，其初始矩阵为

(9)

在此基础上，构造加权规范矩阵，标准化矩阵为

(10)

2)建立最优解与最劣解集合.最优解集合w+、最劣解集合w-由各列中最大元素值、最小元素值所组成，即

(11)

(12)

3)计算各评价对象与最优方案、最劣方案的接近程度，其表达式为

(13)

(14)

4)计算各评价对象与最优方案间的灰色关联系数，其表达式为

(15)

式中，ρ为灰色关联系数，通常取0.5.

5)计算各评价对象与最优、最劣方案间的灰色关联度，其表达式为

(16)

6)整合欧氏距离和灰色关联度，其表达式为

(17)

(18)

7)计算各评价对象与最优方案的贴近程度，其表达式为

(19)

式中，Ei值越趋近于1，说明评价对象越优.

3 案例分析

3.1 企业现状

某汽车座椅装配企业座椅车间主要产品类型包括五座车型的前后排座椅和七座车型的前排、中排及后排座椅，由于汽车消费市场的需求波动导致公司客户的产能调整，原有汽车座椅装配线生产能力过剩，导致生产成本中的直接人工成本比例升高，现将原有整车总装线调整为多种产品型号混流生产.然而，装配线调整后带来的产品需求变化，进而影响生产计划改变，混流装配线需要在一个生产计划周期内装配不同型号的产品，由于不同型号产品存在工序和装配时间的差异，在进行排产装配过程中，出现产品等待时间过长、工人负荷过大的现象，降低了企业实际的装配效率，加大工人工作负荷.针对此类问题，可以通过对产品排产顺序的调整，充分利用工作时间，在装配过程中进行座椅型号的切换，这时就会产生产品投产的排序问题.因此，只有在混流装配过程中合理配置座椅类型、投产顺序、装配数量和装配时间等，才能充分利用混流装配线的装配资源，最大化装配线的装配效率及产能.在实际生产过程中，合理有效的排产方案可以提高装配效率，减少工人工作负荷，以满足客户对订单的需求.

该企业混流装配线共有19道工序，加工6种类型汽车座椅产品，汽车座椅装配车间如图4所示，前、中排座椅混流装配线布局如图5所示.上下两部分对称分别生产左侧与右侧座椅，左右侧座椅生产节拍完全一致，生产时两条线同时进行装配达到同步化生产.其中装配线的左半部分完成靠背和坐垫的装配，右半部分的流水线完成座垫和靠背的结合以及后续装配和整装下线，汽车座椅混流装配时间及综合作业先序图如图6所示.

图4 座椅装配车间

图5 汽车座椅装配线布局

图6 产品装配综合作业先序图

3.2 优化结果

根据企业实际数据，目前车间日计划产量如表2所示，A表示258XT前排，日计划产量40台，B表示258XT中排，日计划产量40台，C表示258GT前排，日计划产量160台，D表示258GT中排，日计划产量160台，E表示JBUB，日计划产量120台，F表示D2SB，日计划产量120台，一个批次加工工件数量为640件，在一个最小循环周期内，A、B、C、D、E、F六种座椅类型投产比为1∶1∶4∶4∶3∶3.

表2 各型号座椅需求

基于MATLAB编程，以汽车座椅混流装配线完工时间、等待时间最小为目标，运用本文提出的改进NSGA-Ⅱ算法对上述案例进行求解，测试环境为：在Windows环境下运用MATLAB对改进NSGA-Ⅱ算法进行编码，CPU为Intel(R)Core 1.70 Hz；内存环境为4 GB.初始种群大小设置为300，迭代次数为200，交叉概率为0.80，变异概率为0.20，得到基于改进NSGA-Ⅱ算法的Pareto最优解集如图7所示.在此基础上，基于改进GRA与TOPSIS混合评价方法对所得Pareto最优解集中各排产方案进行评价，得到最优排产方案如表3所示.

图7 基于改进NSGA-Ⅱ算法所得Pareto最优解集

改进NSGA-Ⅱ算法的运行结果为汽车座椅混流装配线排产提供了众多可行的优化解，汽车座椅装配完工时间和等待时间存在协同优化冲突，对具有多品种大批量特征的汽车座椅混流装配线产品进行排产，在确定座椅批量的基础上，随着汽车座椅完工时间的增加，等待时间呈明显下降趋势，并逐渐达到最优.表3中，编号5的排产方案BCDDECCDDCEFFFEA，当装配一个批量的汽车座椅完工时间为899.08 s、空闲时间为683.28 s时，Ei达到最大值，为0.591 648，更贴近1，故此方案为最优排产方案.

表3 基于改进GRA与TOPSIS方法的最优排产方案选择

3.3 算法有效性分析

为验证本文算法的有效性，分别运用基础NSGA-Ⅱ算法与本文算法对排产方案进行优化，得到算法改进前后帕累托前沿点对比如图8所示.由图8可以看出，两种算法均表现出非支配排序遗传算法固有的收敛速度快的特性，但改进后的NSGA-Ⅱ算法无论收敛速度还是解集质量均要优于基础NSGA-Ⅱ算法.表4为算法改进前后最优解对比.由表4可以看出，在算法改进前后最优的十组解中，经多目标评价决策后的两种算法的评价指标，改进NSGA-Ⅱ算法的各评价对象与最优方案的贴近程度Ei值均大于改进前算法各评价对象与最优方案的贴近程度，多目标整体优化质量提高了1.6%；改进后的NSGA-Ⅱ算法既继承了NSGA-Ⅱ算法收敛速度快的优点，在算法求解过程中，又可以通过循环拥挤排序机制的自适应调节，提高了解的多样性.

图8 算法改进前后帕累托前沿点对比

选择改进前后两种算法最优的前五组解进行比较，对比结果如表4所示.算法改进前后方案目标函数值对比如表5所示.

表4 算法改进前后最优解对比

表5 改进前后排产方案对比

优化后的排产方案为BCDDECCDDCEFFFEA，汽车座椅装配总时间由9.5 h降至7.5 h，减少了21.05%，总等待时间由11.35 h降至9.98 h，减少了12.07%，充分利用了装配线的装配能力，降低了座椅装配的总等待时间，优化效果显著.

通过表4～5、图8可以看出，改进NSGA-Ⅱ算法前沿点均优于基础NSGA-Ⅱ算法前沿点，最优解均匀分布在不连续前沿的各个线段上.改进后的NSGA-Ⅱ算法求解性能有了较大的提升，有效缩短了装配线的等待时间，提高了生产节拍，对于混流装配线排产问题有着更好的适用性，本文所提改进策略提高了算法的求解质量，增强了算法求解性能.

4 仿真验证

在混流装配线排产方案设计阶段，需在装配线投产前对排产方案进行验证，以便检验给定的排产方案是否符合实际生产情况，若在装配线投产后再验证排产方案是否合理，可能会造成企业资源浪费，不能准时完成客户生产订单，因此预先对混流装配线排产方案进行仿真验证尤为重要.运用Plant Simulation仿真软件对给定的排产方案进行仿真分析，动态模拟混流装配线的实际运行状况，完善混流装配线的排产设计.

4.1 仿真建模

根据表3中的排产方案，建立汽车座椅混流装配线Plant Simulation仿真模型，如图9所示.结合装配线作业完工时间和等待时间，设置传送带长度为3 m，传送速度为0.3 m/s，根据客户订单需求，设置订单源生产节拍为44 s，订单数量为640套.装配路线通过实际工艺路线对各工位进行连接，若不同型号座椅在各自工位分别加工，则通过Simtalk仿真语言进行控制.

图9 汽车座椅混流装配线仿真模型

4.2 仿真结果分析

以目前车间日计划产量640套座椅为例，对算法优化前后的排产方案进行仿真，原批量排产方案如图10所示，部分混流排产方案如图11所示，通过比较排产方案优化前后混流装配线完工时间、设备利用率、生产作业工时等指标，验证所提模型及算法的有效性.

图10 原批量排产方案

图11 部分混流排产方案

4.2.1 完工时间对比

原批量排产方案生产640套座椅完工时间为9.55 h，如图12所示.混流排产方案生产640套座椅完工时间为7.6 h，如图13所示.

图12 原批量排产方案完工时间

图13 混流排产方案完工时间

对比图12～13可知，在装配相同订单的前提下，混流装配线排产优化后装配时间由9.55 h下降至7.6 h，减少了20.42%，同时装配线的运输效率得到显著改善，极大地提升了装配线的装配效率，充分利用了人力、物力等资源，降低了工人工作负荷.

4.2.2 设备利用率对比

原批量排产方案各设备利用率如图14所示，平均设备利用率为33.48%.混流排产方案各设备利用率如图15所示，平均设备利用率为51.54%.

图14 原批量排产方案各设备利用率

图15 混流排产方案各设备利用率

对比图14～15可知，混流装配线排产优化后，工作站的平均利用率提高了18.06%，等待率平均下降了21.27%，堵塞率平均下降了99.26%，显著改善了产品在工作站内的堵塞与等待现象，表明排产优化后的混流装配线可提高工作站利用率，减少堵塞与等待现象.

4.2.3 生产作业工时对比

原批量排产方案各工位平均等待时间如图16所示，其装配线综合等待时间为11.38 h.混流排产方案各工位平均等待时间如图17所示，其装配线综合等待时间为9.95 h.

图16 原批量排产方案各工位平均等待时间

图17 混流排产方案各工位平均等待时间

对比图16～17可知，汽车座椅在混流装配线上的平均等待时间较排产优化前下降了12.56%，累计加工数量得到极大提升，表明混流排产方案可显著减少产品装配时的等待时间，提高装配效率，对改善前原批量排产方案而言，有着明显的效率优势.

运用Plant Simulation物流仿真软件对车间的装配线进行仿真模拟，通过代入现实设备与场地参数，分别对比优化前后的完工时间、设备利用率、等待时间.对比结果显示：混流排产方案明显优于原批量排产方案，完工时间由9.55 h降低到7.6 h，平均设备利用率由33.48%上升到51.54%，设备利用率上升18.06%，等待时间由11.38 h降低到9.95 h.仿真结果表明，本文所提模型及算法能有效缩短装配周期，提高装配线资源利用率.

5 结 论

本文通过分析得出以下结论：

1)本文针对混流装配线客户订单多样化、不同装配工艺频繁切换、不同类型产品装配时间难以统一，导致装配周期长、难以满足客户需求的问题，综合考虑产品最小完工时间、最小装配等待时间目标，构建了面向客户订单的多品种大批量混流装配线排产优化模型.

2)提出一种改进非支配排序遗传算法对上述模型进行了求解，应用循环拥挤排序精英选择策略，解决了NSGA-Ⅱ算法收敛性和解的多样性差的问题，应用改进GRA与TOPSIS的多目标评价方法对排产方案进行综合评价，使得两个目标达到Pareto最优.

3)为进一步验证提出的模型与方法的实用性，应用Plant Simulation对优化前后的排产方案进行仿真验证.结果表明：本文所提模型及算法能有效提高混流装配线的生产效率、降低工人工作负荷、缩短产品装配与等待时间.