乘用车发动机装配线多目标工艺优化

宓为建， 陈竹青， 舒帆

(上海海事大学 物流工程学院，上海 201306)

0 引 言

随着现代工业的不断发展，乘用车的保有量与日俱增，乘用车制造企业在不断追求高产量的同时，愈加注重管理水平的改善.发动机质量是关系到乘用车整体质量的重要因素，因此发动机装配线的工艺问题一直是研究热点.

发动机装配线工艺问题是如何将生产发动机的总流程合理有效地分配到装配线的各个工位上.需考虑的因素很多，如发动机工位的负荷平衡、人机效率的综合平衡、工具工装的配置等.工艺优化问题实质是组合优化问题，由产品设计、工艺设计和制造过程技术决定的作业元素之间先后关系的多种变化，使工艺问题变得非常复杂.[1]

目前，关于发动机装配线工艺合理性的研究集中在装配线平衡问题上，以装配线各个工作站的闲置时间最接近为目标，但在追求高平衡率的同时，也可能以损失产能和增加成本为代价.因此，迫切需要从多角度综合评价发动机装配线工艺的优劣，构建多目标的工艺优化模型并进行求解.

装配线平衡问题分为两类.[2]毛凌翔等[3]和范维博等[4]以最小化工位数量为目标研究第一类平衡问题，力求降低生产线的构建成本；鲁建厦等[5]针对第二类平衡问题进行分析，旨在最小化生产节拍.

两类平衡问题从不同角度、以单一目标为考量进行研究.然而乘用车发动机装配线具有装配工序繁杂、工位数量多、批量要求大、工装工具配备数量大等特点.以工装工具为例，如果工艺设计能减少某些工装工具的配置，可以节省的成本十分可观.基于以上原因，发动机装配线的工艺设计和优化仅考虑平衡问题是不够的，需要综合考虑各个影响因素来研究乘用车发动机装配线的多目标优化问题.

针对装配线工艺优化这类组合优化问题，KLEIN等[6]利用分支定界法进行求解.分支定界法属于数学规划法，仅限于求解小规模问题，对于工序繁多的大规模多目标乘用车发动机装配线而言，则难以求解.范维博等[4]提出运用遗传算法(Genetic Algorithm,GA)求解，但由于乘用车发动机工序过多、工序间优先顺序多变、GA收敛速度较快等，容易陷入局部最优解.

基于此，结合发动机企业工艺设计和优化的实际需求，考虑产能、平衡、成本3大要素，建立乘用车发动机装配线多目标数学模型.同时，针对乘用车发动机装配线的特点，采用结合模拟退火(Simulated Annealing,SA)算法的GASA算法:既可保留GA收敛速度快的特点，又具备SA算法求解能力强的优势，以提高生产效率、降低生产成本为目标，为解决大规模乘用车发动机装配线问题提供可行方案.

1 发动机装配线多目标工艺优化模型构建

1.1 模型假设

1.2 模型建立

模型选取产能、平衡、成本3个指标，构建发动机装配线多目标工艺优化模型，目标函数为

(1)

工序排列以产品的加工顺序为导向，工艺之间的优先关系必须满足，从而形成发动机装配线多目标工艺优化模型的约束条件.加工顺序可表示成工序优先关系矩阵：

优先关系矩阵说明：(1)方阵的行数为工序个数；(2)方阵中元素

2 发动机装配线多目标工艺优化模型求解

2.1 GASA算法设计

不少专家学者使用启发式算法对装配线问题进行求解，如蚁群算法[3]，GA[9-10]，粒子群算法[11]，SA算法[12-13].GA具有收敛速度较快、并行能力强等优点，但存在“早熟”这一缺陷.由于乘用车发动机装配线工序繁多，传统GA会遗漏最优解，因此需要提高其搜索能力.SA算法思想与物理退火思想近似，具有初始解依赖性弱、搜索能力强等特点，但其运行速度慢.[14]根据上述特征，本文将SA算法融入GA中，在保证求解速度的前提下获取最优解.GASA算法流程见图1.

图1 GASA算法流程

在GA中嵌入使用SA算法[15]，可选择性地拒绝基因不符合要求的后代，确保最优解被保留到最后，其实现步骤如下：

步骤1初始化.设定初始温度、终止温度、终止次数等参数.

步骤2变异[16].可随机产生一个变异点，把父代染色体分成两部分.保留前部分，将后部分的染色体根据优先矩阵重新排列组合，得到子代染色体.因为后半部分染色体的产生取决于优先矩阵，所以可以保证染色体的可行性.

步骤3判断.分别计算父代及子代染色体的能量值，记为E1和E2.若E2-E1<0，转步骤6；否则，转步骤4.

步骤4概率计算.根据Metropolis准则，粒子在温度T时趋于平衡的概率为P=e-ΔE/(KT)，其中E为温度T时的内能，ΔE为内能改变量，k为Boltzmann常数.

步骤5判断.随机产生一个范围在0～1之间的数，若大于上述概率，转步骤7；否则，转步骤6.

步骤6接受变异后的子代染色体取代父代染色体，转步骤2，达到内循环终止条件后转步骤8.

步骤7拒绝变异后的子代染色体，转步骤2，达到内循环终止条件后转步骤8.

步骤8根据降温幅度产生新温度，循环上述步骤，到达外循环终止条件后停止.

2.2 基于GASA算法的模型求解过程

2.2.1 编码与译码

首先针对工艺优化对象进行遗传算法的编码.工艺优化主要解决两方面问题：排列工序及分配工位.编码用于解决工序排列的表达方式.考虑到乘用车发动机工序数量多，为了便于表达，本文采用自然数编码[17]：将每个工序唯一对应一个自然数，则自然数的排列顺序(称为染色体)为加工工序的先后次序.例：“1 3 2 4 6 8 7 5”即为一条染色体，表示先完成工序1，然后依次完成工序3，2，4，6，8，7，最后完成工序5.根据编码方式及关系矩阵，计算机随机产生一组群体，群体中每条染色体都是问题的可行解.

译码用于处理工位分配，译码方式如下：

步骤1计算平均加工时间Tavg，取Tavg及maxti中的较大值为最小理论节拍,

(2)

式中：m为工序数量；ti为第i个工序的耗时；n为工位数量.

步骤2以最小理论节拍为依据，将工序分配到n-1个工位，剩余工位全部分配至第n个工位.

步骤3计算每个工位的耗时Tj1(j1=1,2,…,n)以及经过增量处理的耗时Tj2=Tj1+tj1+1(j1=1,2,…,n;tj1+1为分配至第j1+1个工位的第1个工序的时间).

步骤4计算maxTj1以及minTj2，若maxTj1≤minTj2，那么minTj2为最小节拍，此分配方案为最优分配；否则以minTj2为最小理论节拍，返回步骤2.

2.2.2 适应度计算及染色体选择

适应度函数的建立取决于目标函数，根据前文所述，目标函数由3部分组成，因此适应度函数也相应分为3块,

(3)

式中：φ1，φ2，φ3与式(1)目标函数一致；α1，β1，γ1分别为各部分适应值的权重，与目标函数一样，采用自适应权重法.

本文采用轮盘赌方法[17]进行染色体的选择.根据个体的适应度值计算其选择概率

式中：Pi为适应度值选择概率；fi为某个染色体的适应度值；N为种群规模.

2.2.3 交叉与变异

交叉的目的在于产生更优良的染色体，其关键之处在于如何保持染色体的可行性，即交叉后工序的排列仍然符合工序优先关系矩阵.

本文采用两点交叉法，交叉过程如下：

步骤1随机产生两条父代染色体.

步骤2随机产生两个交叉点，将每条父代染色体分成3段.

步骤3保留第1段和第3段染色体，将一条父代染色体中间部分的工序按其在另一条父代染色体中的顺序进行排列，形成子代染色体.

从步骤3可以发现，由于交叉后子代染色体中间部分的排列顺序来源于交叉前父代染色体，子代染色体为可行染色体.

接着，按照上文算法设计所述，结合SA算法进行染色体的变异操作，其中内循环终止条件为迭代到一定的次数，外循环终止条件为达到设定的最低温度.经过上述步骤，新种群将取代旧种群.

3 发动机装配线多目标工艺优化案例

以B企业乘用车发动机装配线的核心部分为例，现有5个工位，共需经过38道工序，其先后顺序、工序时间、配备设备数见图2.

图2中，圆圈内的数字表示工序编号，圆圈外的数字表示工序时间，灰色填充表示该工序需要耗资设备才能完成.

在MATLAB环境下，分别用GA和GASA算法进行求解，程序运行图见图3和4.

图2 加工工序

图3 GA运行结果 图4 GASA算法运行结果

图3和4中每根柱子表示每个工位的耗时.对比两张图可以发现GASA算法得到的柱状图的平衡性更佳.

案例结果见表1.从表1可以发现：GASA算法得到的生产节拍小于GA，因而产能增加2.04%；均衡率(方差)下降3.46，能有效平衡工位间的负荷.从而可以证明，由于结合SA算法，GASA算法可避免GA“早熟”的缺陷，跳出局部最优解找到全局最优解.

GASA算法的迭代图见图5.

图5表明，当迭代到一定次数时，适应度值趋于一个值，GASA算法具有很好的收敛性.

表1 案例结果

图5 GASA算法的迭代图

4 结束语

鉴于乘用车发动机装配线平衡所涉及的多个目标之间常常相互冲突，单独优化某一目标往往会造成其他目标的劣化，本文构建考虑产能、平衡、成本的乘用车发动机装配线多目标工艺优化数学模型，并采用GASA算法进行求解.实例验证表明，该模型及算法能在一定程度上优化大规模乘用车发动机装配线的工艺，提高工艺的综合性能.

参考文献：

[1] 彭慧, 徐克林, 侣占华. 采用遗传算法的混流装配线平衡多目标优化[J]. 现代制造工程, 2011(11): 49-55.

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

[3] 毛凌翔, 郑永前. 蚁群算法求解装配线平衡第一类问题[J]. 计算机系统应用, 2010, 19(1): 140-143.

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

[5] 鲁建厦, 蒋玲玲, 李修琳. 基于混合粒子群算法求解装配线第二类平衡问题[J]. 中国机械工程, 2010, 21(4): 420-424.

[6] KLEIN R, SCHOLL A. Maximizing the production rate in simple line balancing: a branch and bound procedure[J]. Eur J Operational Res, 1996, 91(2): 367-385.

[7] 玄光男, 程润伟. 遗传算法与工程优化[M]. 北京: 清华大学出版社, 2004: 97-100.

[8] 陈星宇. 基于改进遗传算法的装配生产线平衡技术研究[D]. 上海: 上海交通大学, 2011.

[9] 宋华明, 韩玉启. 基于遗传算法的装配线平衡[J]. 系统工程, 2002, 20(1): 87-91.

[10] 王红军, 张怀存. 基于遗传的变速箱装配线平衡研究[J]. 微计算机信息, 2009, 25(1): 306-308.

[11] 陈永卿. 基于混合进化算法的装配线平衡问题研究[D]. 杭州: 浙江大学, 2008.

[12] SURESH G, SAHU S. Stochastic assembly line balancing using simulated annealing[J]. Int J Production Res, 1994, 32(8): 1801-1810.

[13] 徐天. 装配生产线平衡分析与研究[D]. 上海: 上海交通大学, 2011.

[14] 王芸凤, 刘明周, 于宝证. 求解装配线平衡问题的混合遗传算法[J]. 合肥: 合肥工业大学学报, 2005, 28(6): 616-619.

[15] 李莉, 丁以中. 轴辐式快递网络的枢纽选址和分配优化[J]. 上海海事大学学报, 2012, 33(2): 33-41.

[16] 郭贝贝, 靳志宏. 现实约束条件下的集装箱多箱装载优化[J]. 上海海事大学学报, 2009, 30(2): 8-15.

[17] 何军良, 宓为建. 基于分布式混合遗传算法的动态泊位分配策略与仿真[J]. 上海海事大学学报, 2012, 33(2): 52-58.