基于NSGA-Ⅲ算法的多目标集成工艺规划与调度问题研究

张伟伟，李旭光，文笑雨，张静，史文隽，张卫正

(郑州轻工业大学 计算机与通信工程学院,河南 郑州 450002)

0 引 言

工艺规划和车间调度是制造系统中非常重要的两个子系统[1]，影响着制造系统的效率，将两个系统集成并进行优化，可以大幅度提高生产效率[2]。此外，企业在生产过程中往往需要考虑成本、效率、能耗等多个优化目标，对多目标集成工艺规划与调度(integrated process planning and scheduling，IPPS)的求解方法进行研究，不仅能提高制造产业效率，而且有利于减少生产过程的碳排放，因此，研究多目标IPPS具有非常重要的应用价值。

多目标IPPS问题存在多种柔性特征，问题的解空间很大，求解非常困难，是一个典型的NP难问题，传统的数学方法很难解决该问题[3]。近几十年，进化算法飞速发展，越来越多的学者使用进化算法解决多目标IPPS问题，如NSGA-Ⅱ算法[4]、人工蜂群算法[5-6]、聚类差分进化算法[7]、免疫自适应遗传算法[8]等。使用进化算法求解多目标IPPS问题已成为近年来研究的热点，截至目前，国内针对多目标IPPS问题的研究主要以机器负载指标和时间指标为主，很少考虑能耗、碳排放等绿色指标，且研究以单目标、两目标为主。随着气候变化加快，环境问题引起全球关注，以节能减排为目标的IPPS问题逐步受到广大学者的重视，但研究主要以模型建立为主[9-11]，对求解方法的研究较少。因此，本文从减少工业制造过程的碳排放出发，建立以碳排放、完工时间和总拖期为优化目标的IPPS问题，针对多目标IPPS问题求解方法研究的不足，提出一种集成变邻域搜索的NSGA-Ⅲ算法，对多目标IPPS问题进行优化求解，并通过实例对算法进行测试，测试结果验证了所提算法的优越性能。

1 IPPS问题描述与模型建立

1.1 IPPS问题描述

多目标IPPS问题的定义[13]：n个工件在m台机器上加工，从工件的可选择工艺、制造资源中确定工件在机器之间的传递序列、开工时间和完工时间，最终生成满足各个目标的调度方案。

多目标IPPS问题需要解决3个问题：(1)在工艺规划阶段，确定每个工件的加工顺序；(2)在工序的可选择机器中确定加工机器，生成一条明确的工艺路线；(3)在车间调度阶段，确定所有工件的全部工序在机器上的开始时间和结束时间。本文研究的多目标IPPS问题，调度方式为作业车间调度。柔性工艺规划通过某工件的加工信息(表1)进行说明。该工件有5个加工特征(F1～F5)，在5台机器上进行加工(M1～M5)，不同特征有不同的可选加工工艺。如特征F3有两个可选工艺(O4～O5,O6～O7),每种工艺都需要两道工序才能完成。每道加工工序有多台可选加工机器，例如工序O1有2台可选机器(M1,M2)。特征约束中，特征1必须在其他特征前加工，特征2必须在特征4前加工。

表1 某工件的加工信息Tab.1 Processing informations of a job

1.2 IPPS模型建立

本文在研究多目标IPPS问题时，作如下假设[5,11]：(1)工件间没有优先级关系，且每个工件同一时刻只能在一台机器上加工；(2)每台机器同一时刻只能加工一个工件，且完工前不能被打断；(3)工序的加工时间包含该工序在机器上的准备时间；(4)考虑工件在机器间的传输时间，传输过程产生的碳排放仅与电动叉车的使用时间相关；(5)考虑机器上不同工件的转换时间；(6)机床在一次调度中只启动、关闭一次，且机床启动、预热和关闭产生的碳排放为常量；(7)机器上加工任意工件运行功率相同；(8)机器上使用同一类型的冷却液。基于以上假设，本文研究以生产过程碳排放最小、最大完工时间最小和总拖期最小3个目标的优化问题，其多目标优化模型如式(1)～(4)所示[5,11]。

minf=[f1,f2,f3]T，

(1)

f1=Ctime=maxci，i∈[1,n],

(2)

(3)

(4)

式中：n为待加工工件总数；m为机器数目；ci为工件i的完工时间；di为工件i的交货期；αe为电能碳排放因子；Econ为机床一次启动、预热和结束的系统能耗；Plr为机床l加工第r道工序的运行功率；PTrl为第r道工序在机床l上的加工时间；Ll为机床l在加工过程中冷却液的消耗量；Tl为机床l上冷却液的使用周期；αc为冷却液的碳排放因子；Pcv为电动叉车的传送功率。

式(1)为3目标优化模型，式(2)为最大完工时间，式(3)为总拖期，式(4)为总碳排放。式(4)中：第一项为机床碳排放，包括机床加工时的能耗，机床一次启动、预热和结束的能耗；第二项为冷却液消耗产生的碳排放；第三项为电动叉车运行产生的碳排放。模型约束条件参见文献[5，11]。

2 基于NSGA-Ⅲ的多目标IPPS问题求解方法

2.1 多目标优化问题定义

相对于单目标问题而言，多目标问题(multi-objective optimization problem,MOP)存在多个相互冲突的目标函数。一个多目标优化问题可以用式(1)表示，其中f1,f2,f3为3个目标函数。由于多目标问题不同目标之间相互冲突，不能通过比较函数值的大小评估解的质量，因此，在解决多目标问题时，通常根据解之间的“Pareto支配”关系[12]区别解的质量好坏。最小化多目标问题的Pareto支配定义为

∀i∈{1,…,m},fi(X)≤fi(X′)；∃i∈{1,…,m},fi(X)

(5)

对于最小化多目标问题中的两个解X和X′，X和Xv的任意目标函数值满足fi(X)≤fi(X′)，且在目标空间中至少存在一个目标函数使得fi(X)

2.2 算法框架

目前，解决多目标IPPS问题的进化算法在选择阶段大多是基于非支配排序的方法，根据种群中个体的非支配等级选择下一代种群。多目标IPPS问题非常复杂，解空间很大，随着目标数增多，会出现大量的非支配解，导致个体选择时计算量非常大，且不能有效保证种群的多样性。在NSGA-Ⅱ基础上，NSGA-Ⅲ算法提出一种基于空间参考点的选择方式,有效地保持了种群的多样性，并且提高了选择过程的效率，适合解决多目标IPPS问题。

NSGA-Ⅲ算法是针对多目标连续优化问题提出的，而IPPS问题是组合优化问题，NSGA-Ⅲ算法不能直接解决该问题。本文在NSGA-Ⅲ算法的基础上进行改进，提出3个关键策略求解多目标IPPS问题：(1)使用简单、高效的编码方式对种群进行初始化，初始化的每个个体都是一条可行的加工路线；(2)根据种群编码方式，使用高效的交叉、变异方式，使算法在搜索过程中可以覆盖整个目标空间，有利于保持种群的多样性；(3)算法中的集成变邻域搜索方法，使用不同的邻域方法，以不同搜索方式加强算法的局部搜索能力。算法框架如表2所示。

表2 算法框架Tab.2 Algorithm framework

2.3 NSGA-Ⅲ算法改进

2.3.1 编码与解码

编码和解码方式会直接影响整个算法的效率，高效的编码和解码方式能使算法的各个部分更容易实现，提高算法的整体效率。本文在工艺规划阶段和调度阶段采用不同的编码方式。在工艺规划阶段采用文献[5]的三段式编码方式，该方法中，每条染色体包含三段不同序列，分别为特征顺序序列、可选工序序列和可选机器序列。该编码方式解码时非常简单，特征顺序即特征加工顺序，只需从可选工艺中确定特征相应的加工工艺，再根据工艺选择相应的加工机器。在调度阶段，采用基于工序的编码方式[15]，该方法是车间调度问题研究中最常用的编码方式，简单高效。在解码过程中，使用文献[16]中贪婪解码方法将编码方案解码为活动调度类型。

2.3.2 交叉和变异操作

在进行交叉和变异操作时，由于工艺规划阶段和调度阶段使用不同的编码方式，所以在两个阶段分别使用不同的交叉和变异方式：在工艺规划阶段，根据该阶段采用的三段式编码方式，继续采用文献[5]中的方法进行相应的交叉和变异操作；在调度阶段，选用文献[16]提出的POX(precedence operation crossover)交叉算子，对新产生的子代种群进行交叉操作；在变异阶段，继续，并沿用该文献中使用的邻域搜索变异算子，对新产生的子代种群进行变异操作。

2.3.3 种群选择

从合并种群中选择新的父代种群时，采用快速非支配排序方法[14]，根据种群中个体的非支配等级将合并种群进行分层，主要步骤如下。

步骤1根据支配的定义判断种群中所有个体的支配关系。

步骤2根据支配关系，将种群中所有非支配个体保存在集合F1中，其余个体放入集合S中，对S中的个体进行非支配排序，并将其中的非支配解放入集合F2中。

步骤3重复上述步骤，直到所有个体都被分层。

将合并种群分层后，采用NSGA-Ⅲ[12]算法的选择方式，从合并种群中挑选新的父代种群。假设种群初始化个数为N，父代种群个数为Pt，交叉、变异产生的新解个数为Qt，合并种群个数为Rt=Pt+Qt，并设St为一个空集。选择过程简述如下。

(2)根据目标数生成均匀的空间参考点，将Fl中个体做归一化处理，计算Fl中每个个体到各个参考点的欧式距离，Fl中的个体与距离最近的参考点建立联系。

(3)计算各个参考点联系的个体数，根据参考点联系个体数的多少，从各个参考点关联的个体中均匀选择K个个体加入下一代，其中K=N-Pt+1。

2.3.4 变邻域搜索

变邻域搜索是一种非常有效的局部搜索方法，也是当前解决车间调度问题常用的一种方法。为加强算法的局部搜索能力，在NSGA-Ⅲ算法中集成变邻域搜索方法。本文使用的变邻域搜索方法包含3个不同的邻域方法[17]，具体如下。

(1)N1为随机全邻域法。在子代个体中随机选择3个不同位置的基因,采用全排列生成5个新个体,从中挑选最好的1个取代原来的个体。

(2)N2为两点交叉邻域法。在子代个体中随机选择2个不同位置的基因，将其互换。

(3)N3为N5邻域法。对于关键路径上的关键块,首块只交换最后2个加工工序,相应的尾块只交换前2个加工工序,所有的中间块分别交换前2个加工工序和最后2个加工工序。

对于产生的子代种群，依次使用3个邻域搜索方法，每种搜索方法重复使用，该方法不能再提高个体质量时，换下一种搜索方法，直到3个搜索方法全部搜索完毕，邻域搜索操作完成。主要步骤如下。

步骤1对子代种群中一个个体x，定义不同的邻域搜索方法Nk，k=1,2,3。

步骤2设置k=1，重复以下步骤直到k=3。

步骤2.1根据邻域搜索方法Nk产生邻域解x′。

步骤2.2从邻域解x′中找出最优的个体x″。

步骤2.3判断x″是否优于x，如果好于x，则x=x″，k=1；否则令k=k+1。

2.3.5 Pareto解集更新方法

调度阶段结束后，产生新的非支配解。判断Pareto解集是否为空，解集为空时，将新产生的非支配解全部放入Pareto解集中；解集不为空时，Pareto解集中的解和新的非支配解合并，找到合并解集中的非支配，替换解集中原来的解。算法主要步骤如下：

步骤1将父代与子代合并，并从中挑选非支配解。

步骤2判断外部Pareto解集是否为空，若解集为空，将非支配解全部放入解集当中；若解集不为空，则跳转到步骤3。

步骤3将新产生的非支配解与Pareto解集当中的非支配解合并，找到合并解中新的非支配解，将Pareto解集重新放入Pareto解集当中。

2.3.6 NSGA-Ⅲ算法求解IPPS问题

基于以上对算法关键操作的描述，本文使用NSGA-Ⅲ算法求解IPPS问题，具体步骤如下。

步骤1设定算法中各个参数。

步骤2输入待求解的IPPS问题，采用上文介绍的编码方法，为每个工件初始化工艺路线种群。

步骤3设置工艺规划阶段算法的终止条件为最大迭代次数，使用上文方法对每个工件的工艺路线种群进行优化，得到工件的工艺路线非支配解集。

步骤4从每个工件的工艺路线非支配解集中为每个工件随机选择一条工艺路线，输入作业车间调度阶段，根据每个工件选择的工艺路线，采用上文介绍的编码方法，初始化调度种群。

步骤5判断NSGA-Ⅲ算法的迭代次数是否达到最大，如果迭代次数达到最大，跳转到步骤8。如果没有达到，则使用上文介绍的方法对调度种群进行优化。

步骤6使用上文介绍的邻域搜索方法，对经过NSGA-Ⅲ算法产生的新调度种群进行局部搜索。

步骤7更新NSGA-Ⅲ算法当前的迭代次数，并跳转到步骤5。

步骤8更新Pareto解集，判断NSGA-Ⅲ算法的迭代次数是否达到最大，如果迭代次数达到最大，则算法结束，输出Pareto解集，否则跳转到步骤4。

3 结果与分析

上述求解IPPS问题的NSGA-Ⅲ算法使用Visual C++进行编写，运行程序的计算机CPU为Core-(TM)i5-3230M(1.80GHz),4GB内存。

3.1 测试实例

已有文献中缺少考虑绿色制造的多目标IPPS问题测试实例，为了验证算法有效性，以6种工件、5台机器为例进行测试，工件间的调整时间见表3，机器间的转运时间见表4，工件加工信息见表5，机器的能耗信息见表6。

表3 工件间调整时间Tab.3 Adjustment time between jobs h

表4 机器间的转运时间Tab.4 Transmission time between machines

表5 工件加工信息Tab.5 Workpieces processing informations

续表5

表6 机器的能耗信息Tab.6 Energy consumption of the machines

(6)

式中：P*为算法找到的PF；P为算法真正的PF；d(v,p)为P*中的一个解v与P之间最小的欧氏距离；|P*|为P*的数量。

本文中IGD值越小代表结果越好。值得注意的是，在IPPS问题的测试实例上没有真实的Pareto前沿，计算该指标时，将不同算法在同一个测试问题上进行20次测试，然后将测试得到的Pareto解集合并，在合并的解集中找到非支配解，将这个合并解集中的非支配解当作真实的Pareto前沿计算IGD值。

3.2 算法参数设置

电能碳排放因子αe取全国排放因子的平均值0.674 7 kg CO2/kWh，冷却液碳排放因子参考香港中小型企业碳审计工具箱[19]，αc取碳排放因子和处理废液碳排放因子之和，αc=3.05 kg CO2/L。在测试实例时，设定算法的整体最大迭代次数GIPPS为200，算法的其他参数如表7所示。

表7 算法参数设置Tab.7 Parameters setting

3.3 实验结果与分析

为了测试本文算法在不同规模问题上的有效性，从6种工件中随机挑选工件，组成7个不同规模的问题，问题2～7中都会出现相同的工件。在7个不同规模的问题上，本文算法与文献[4]和[8]中的算法进行对比，同时，为了验证本文算法中变邻域搜索的有效性，不包含邻域搜索的NSGA-Ⅲ算法同时参与对比，每个规模的问题进行20次测试。各个算法获得的非支配解如表8所示，由于篇幅原因，只列举了部分非支配解。算法对比的IGD值为20次测试的平均值，如表9所示。本文算法获得的最优解工艺路线见表10，该解对应的甘特图见图1。

表10 问题7的一个非支配解对应的工艺路线Tab.10 Process route corresponding to a non-dominated solution of problem 7

由表8可以看出，不同算法都可以找到比较不错的非支配解，不同算法获得的非支配解之间没有明显的支配关系；由表9可以看出，在问题2～7上，本文算法实验结果的IGD值最小，说明本文算法获得的非支配前沿最接近真实非支配前沿。随着问题规模增大，与其他算法之间的差距更明显，说明本文所提 算法在解决问题规模大的多目标IPPS问题时效果更好；由表9和图1可以看出，本文算法获得的非支配解是可行解，可以指导实际生产。

表8 不同算法获得的非支配解Tab.8 Non-dominated solutions obtained by different algorithms

表9 不同算法实验结果的平均IGD值Tab.9 Average IGD value of the experimental results of each algorithm

续表10

图1 问题7的一个非支配解对应的甘特图Fig.1 A Gantt chart corresponding to a non-dominated solution of problem 7

4 结 语

针对复杂的多目标IPPS问题，设计兼顾碳排放、完工时间、总拖期的多目标集成模型。提出了改进的NSGA-Ⅲ算法，算法采用编码方式、选择方式以及变邻域搜索，使NSGA-Ⅲ算法可以高效地解决组合优化问题。采用7个不同规模的测试实例对本文算法进行测试，测试结果证明了本文算法的可行性与准确性，且在求解大规模多目标IPPS问题时，比现有算法更有优势。该算法策略为复杂的多目标IPPS问题提供了一种有效的解决方案，为智能制造系统的排产优化提供了决策依据。在今后的研究中，将对实际生产中的动态环境进行研究，如机器故障和急件加工的不确定事件，构建不确定环境下的数学模型，并设计更为高效的算法，使研究成果实用性更好，能更好地指导实际生产。