基于NSGA-Ⅱ算法的液压元件多目标柔性作业调度研究*

杨俊茹 李 贺 李瑞川 刘长誉 荆本雨③ 李 宁③ 张 建④

(①山东科技大学机械电子工程学院，山东 青岛 266590; ②齐鲁工业大学机械与汽车工程学院，山东 济南 250301;③山东海卓电液控制工程技术研究院，山东 日照 276800;④日照海卓液压有限公司，山东 日照 276800)

液压元件制造业作为国家工业体系的基础产业之一，影响着我国制造业发展水平的高低。液压元件的生产模式由原来的种类少、订单大逐步向种类多、订单小转变，并逐渐成为一种常态化的成产模式，该生产模式的极大地增加了生产管理的复杂性与难度[1-2]。

生产调度作为液压元件制造车间管理的核心环节，是指将生产任务转化为切实可行的生产计划，同时对生产计划进行实时的监督和反馈，对制造效率、生产周期等都具有较大的影响[3-4]。液压元件的生产模式为离散型、柔性化的生产模式，所以液压生产车间调度问题为多目标柔性作业车间调度问题(MOFJSP)[5]。

设计合适的生产调度算法可以实现原材料、加工设备等的最优利用，常用的智能调度优化方法有遗传算法(GA)[6]、模拟退火算法(SA)[7]、蚁群算法(ACO)[8]、粒子群算法(PSO)[9]和禁忌搜索法(TS)[10]等。其中，遗传算法因运行简单，随机性强、易拓展、鲁棒性强以及全局搜索迅速等优势在车间调度问题中应用广泛[11]。但是，传统的遗传算法存在很多不足，如收敛时间长、部分范围搜寻力低、缺乏标准等，因此，许多学者基于改进的GA算法对调度问题进行了研究。李耀华等[12]提出了一种基于自适应GA算法的航材优化调度方法,能够实时解决民用飞机不同维修任务，优化物料调度。张立果等[13]提出了一种求解多目标问题的双层改进遗传算法，基于完工时间、机器负载和机器总负载三因素完成了实例验证，表明算法具有很高的可靠性。王召阳等[14]以遗传算法为基础，提出了一种带有权重的生产调度算法，根据同一机器不同零件和同一零件不同工序分为多种情况，分别得出对应的加工和等待时间，根据零件加工权重，得到调度最优解。

本文针对目前的研究现状，采用带精英策略的非支配排序改进遗传算法来解决液压生产车间内的多目标柔性作业车间调度问题，运用工序和设备组合式进行编码的办法，充分表示工件的制造过程，基于工序和设备分别制定交叉和变异策略。通过实例分析，从最大完成加工时间、设备负荷率和生产成本3个指标对调度优化结果进行评价，验证了本改进算法的实用性和有效性。

1 车间调度模型

1.1 问题描述

以某企业液压元件制造车间为平台，进行生产调度问题的描述。该液压元件多目标柔性化车间调度问题可表达为：n个零件{J1,J2,…,Jn}、q台设备{M1,M2,…,Mq}，每个零件包括mn(m≥1)道工序，每道工序Oij可在设备Mp(p∈[1,q])上进行加工，需要对n个零件选择加工装备和制定加工顺序，保证加工效率的最优化。

同时需满足以下约束条件：

(2)工序Oij在设备Mk上加工过程不能中止。

(3)零件的工艺路线预先设定，零件的加工必须严格遵守工艺路线，不能跨工序进行加工。

(4)每个零件只在某一指定设备上加工一次，同种零件加工优先级相同。

选择不同的生产调度方案，往往使得车间加工设备负荷率、加工成本及加工时间等指标差异巨大，极大地影响车间加工效率。选择合适的调度方案，对于指导现场生产具有重大的意义。

1.2 数学模型

本文中的调度问题是指在满足约束条件的前提下，基于加工时间、设备总负荷与成本3个指标进行多目标液压元件生产车间调度的模型评价，其中参数定义如表1所示。

表1 参数定义

构建适应度函数，如式(1)所示[15]：

f=min{g(Tmax,L,C)}

(1)

1.2.1 最大完成加工时间

在一批生产计划中加工完成最后零部件的时间最短，此评价指标对产品的加工周期与生产所用的总时间有重大影响，其数学表达如式(2)所示：

Tt=min (max(Tti)),i=1,2,3,…,n

(2)

作业车间调度的结果是具体的生产计划，即确定工件i的第j批的l工序在第m台设备上的开工时刻如式(3)所示：

(3)

完工时间点如式(4)所示：

(4)

1.2.2 设备总负荷率

设备负荷率是指制造装备在工作过程中主轴所承受的负载率，如果负载率过高会对设备造成损害，从而影响加工进程，所以设备负荷率是辅助调度方案合理性指标，其数学表达如式(5)所示：

(5)

1.2.3 加工总成本

加工制造一批产品所需要的所有成本称为总成本，其中包括加工成本和原材料成本等主要成本，总成本是企业加工过程中的一个重要因素，所以成本因素是作为调度方案的一个参考和基础，其数学表达如式(6)所示：

(6)

2 NSGA-Ⅱ算法求解MOFJSP

2.1 NSGA-Ⅱ算法

针对多目标问题，采用非支配排序和精英储备策略，实现多目标定位制造，必须在多个目标上达成相对妥协,使得总目标优化。其总体流程图如图1所示。

其具体的运行步骤如下：

步骤1：随机生成个体的初始化种群P0，判断对所有个体的分级排序完成情况，并对未完成的个体进行非支配排序，计算个体非支配前端中的拥挤长度，直到遍布所有个体。

步骤2：对父代种群Pt执行选择、交叉、变异遗传操作，产生子代种群Qt。

步骤3：将Pt与Qt合并产生种群大小为2N的新种群Rt，对Rt执行快速非支配排序操作，得到各级非支配前端F1,F2,...,Fi。

步骤4：计算每级非支配前端Fi中个体的拥挤距离，按照锦标赛选择机制优选出N个个体，组成新父代种群Pt+i。

步骤5：判断进化代数是否大于最大代数，满足终止条件则循环结束，否则Gen=Gen+1然后转到步骤2。

步骤6：结束整个流程，得到Pareto最优的解集。

2.2 编码与解码

2.3 交叉操作

交叉是随机将两条染色体上的几个基因交叉变换得到新染色体的过程。根据上述编码方法，本文采取工序及装备染色体差异交叉，以保障调度解适用性。本文采用两种交叉策略，即基于工序的POX交叉策略和基于设备的MPX交叉策略。

工序染色体基因串POX交叉实施，如图4所示。

(1)根据部件集合分散出非空互补子集H1和H2。

(2)将基因串P1中包含在H1中的工序复制到B1，基因串P2中包含在H2中的工序复制到B2，确保基因位置不变。

(3)将基因串P2中包含在H2的工序复制到B1，基因串P1中包含在H1的工序复制到B2，确保相对位置不变。

设备染色体基因串MPX交叉实施，如图5所示：

(1)随机生成基因串R，R的元素只能为0或1，且与设备基因串P1和P2的元素个数相同。

2.4 变异操作

变异的目标是提高种群多变性，用来阻断算法早期收敛。也需交叉一样需要对工序和设备染色体进行变异。

工序染色体基因串变异操作，如图6所示：

指定一条工序染色体上的某一个基因，无规则与另一个染色体上的一个基因进行替换。

设备染色体基因串变异操作，如图7所示：

(1)随机的在一条染色体上挑选单个设备基因，如图7阴影部分所示。

(2)将挑选的基因变异成别的基因完成基因串的变异。

2.5 选择策略

NSGA-II算法同时对多个任务优化处理，在单任务时，常用的选择方法有轮盘赌、锦标赛等，但是对于多任务进行一起选择时，则根据单体等级差别和同一级别非支配解排列结合法进行选择。对于同等级非支配解排序的个体聚集距离可以用式(7)计算：

3 实例

本文基于某企业液压元件制造车间，利用MATLAB R2016b进行仿真，以11个零件、6台设备为例进行分析。采用NSGA-Ⅱ算法，算法主要参数如表2所示。

表2 算法主要参数

最大完工时间、设备的总负荷率、总成本的最优值的进化过程如图8所示， 实线和虚线分别代表NSGA-Ⅱ算法和GA算法的迭代结果。从优化结果可以得到随着迭代次数的增大，基于NSGA-Ⅱ算法的最大加工时间、设备总负荷以及总成本迭代优化结果明显低于基于GA算法的迭代优化结果，收敛速度快、分布性好。

根据NSGA-Ⅱ算法的优化结果，利用MATLAB 2016仿真软件对生产调度计划进行处理，生成对应的甘特图如图9所示。

4 结语

基于液压元件生产车间实际生产调度状况分析，提出了加工约束条件，建立了多目标柔性作业车间调度问题数学模型。采用带精英策略的非支配排序改进遗传算法(NSGA-Ⅱ)，对液压车间进行了生产调度分析，从最大完成加工时间、设备负荷率及生产成本3个指标对调度结果进行评价，仿真结果与传统遗传算法的比较，结果显示其性能比传统遗传算法更加优异。