一种基于改进NSGA-II的多目标绿色柔性作业车间调度方法＊

郑锦灿 邵立珍 雷雪梅

（①北京科技大学自动化学院，北京 100083；②北京科技大学顺德创新院，广东 佛山 528399；③北京科技大学信息化建设与管理办公室，北京 100083）

柔性作业车间调度问题（flexible flow job shop scheduling problem，FJSP）是传统作业车间调度问题基础上的扩展，它是一类经典的NP-hard问题。在传统作业车间调度问题中，每个工件由一道或多道具有固定加工顺序的工序构成，且每道工序的加工机器是唯一的。FJSP允许一道工序有多台可供选择的加工机器，且在不同机器上的加工时间可能存在差异，这更符合柔性制造系统的实际情况。传统的FJSP通常仅考虑单一的目标函数，如最小化最大完工时间或者经济性能指标等。但是随着社会经济的快速发展和人们的环保意识不断的提高，单纯的经济指标已经无法满足绿色生产的需求，能耗、碳排放等一系列绿色生产指标正越来越受到企业的重视[1]。因此，多目标柔性绿色作业车间调度问题应运而生。

不同于单目标FJSP，多目标FJSP中多个性能指标需要被同时优化。许多学者采用智能优化算法求解该问题。Li M等[2]提出了一种两层帝国竞争算法求解具有目标重要性约束的多目标优化问题。Msc M 等[3]应用分布式估计算法求解了多目标随机调度问题。杨帆[4]提出了一种多种交叉混合的交叉方法和一种基于元胞数组的解码方式，提高遗传算法的全局搜索能力。梁晓磊等[5]构建了以机器效率最大和最大完工时间最小为目标的调度模型，并使用改进的遗传算法求解。Chang H C等[6]提出了一种混合遗传算法（hybrid genetic algorithm，HGA），使用田口方法来优化算法的参数，还提出了一种新的编码机制解决了无效工件的分配问题。

在多目标调度问题的求解中，如何防止算法陷入局部最优是研究的一个热点。文笑雨等[7]设计了N5邻域结构，并提出了改进NSGA-II求解方法。张国辉等[8]考虑了完工时间，机器负载以及环境碳排放的柔性低碳调度模型，在NSGA-II算法基础上引入邻域搜索策略得到了高效可行的调度解。Frutos M等[9]构建了最小化完工时间和总成本的多目标模型，在遗传算法的搜索过程中引入模拟退火算法跳出了局部最优。陈辅斌等[10]结合实际生产过程中加工时间、机器负载、运行成本等情况，建立了多目标调度模型，引入免疫平衡原理改进NSGAII算法，避免了算法陷入局部最优。

虽然上述的研究取得了一定的成果，但是针对多目标FJSP的研究，仍存在如下问题：①现有的FJSP模型大都集中于最小化完工时间和机器总负荷，忽视了能耗指标，模型无法满足实际的绿色生产需求；②在智能优化算法中，随机选择的初始化策略影响着算法的求解性能，但现有的智能优化调度算法对种群初始化策略关注较少，且解易于陷入局部最优。

基于上述考虑，本文首先建立了一个多目标绿色FJSP模型。模型中，除了考虑传统的经济指标，还考虑了能耗指标。其次，提出了一种改进的快速非支配排序遗传算法（improved non-dominated sorting genetic algorithm II，INSGA-II）求解该模型。

1 多目标柔性作业车间调度问题

1.1 问题描述

FJSP的数学描述[11]为：有n个相互独立的工件 J ={J1,J2, ··· ,Jn}在m台不同的机器构成的机器集M={M1,M2, ···,Mm}上加工，每个工件包含一定的工序，以工序集 O ={Oi,1,Oi,2, ···,Oi,ni}的形式表示，预先给定所有工序在可选机器上的加工时间进行加工。

在建立具体的数学模型之前，根据实际的生产加工情况做出如下假设：

（1）同一时间内每个机器只能加工一道工序。

（2）所有工件的工序加工时间是已知的。

（3）同一工件的不同加工工序具有先后优先级，不同工件的加工工序没有先后优先级。

（4）一道工序一旦开始加工就不能中止。

（5）每个工件在同一时刻内只允许在一道机器上加工。

（6）在0时刻开始所有机器都是可用的，同时机器不会发生故障。

本文中出现的一些符号定义如表1所示。

表1 符号定义表

1.2 模型建立

FJSP的数学模型如下：

式（1）和（2）均是控制约束变量，用来约束指定机器上的加工和工序。式（3）和（4）表示根据每一工件的工艺路线，工序的先后加工顺序约束；式（5）表示每一个工件的完工时间不能超过总的完工时间；式（6）规定每台机器某一时刻只能加工一道工序；式（7）是独占性约束，即规定某一时刻每道工序仅能在一台机器上加工；式（8）和（9）中规定各个参数的变量必须是正数。

模型中的优化目标为：最大完工时间、机器总负荷、能耗。最大完工时间是使用频率最高的基本经济指标；机器总负荷指标和瓶颈机器负荷指标在延长机器的寿命、合理分配资源以及提高生产效率的方面中有着重要的意义；能耗指标作为绿色生产的评价指标引入。计算公式如下：

除了上述的3个性能指标，在进行算法的性能比较时，通常也会引入机器的瓶颈负荷指标进行测试，其具体计算公式如下。

2 改进的NSGA-II算法

INSGA-II算法的流程图如图1所示。该算法基于NSGA-II进行改进，主要包括以下几个部分：编码生成初始种群、解码、快速非支配排序和拥挤度距离计算、交叉变异操作、精英保留策略和学习机制。

图1 改进NSGA-II算法流程图

2.1 混合种群初始化策略

种群的初始化方式与调度的初始解具有不可分割的关系，高效的初始化方式有助于提高算法的收敛速度，通过更少的迭代次数得到问题的最优解。

本文基于机器和工序（machine selection and operation sequence，MSOS)两层编码。如图2，首先随机生成工序染色体P，然后通过工序染色体P确定机器染色体M，图中工序染色体[1, 2, 3, 1, 4, 2, 3, 4, 2]依次代表工序 [O11,O21,O31,O12,O41,O22,O32,O42,O23]，机器染色体[5, 1, 2, 4, 3, 3, 1, 2, 5]依次代表机器[M5,M1,M2,M4,M3,M3,M1,M2,M5]。

图2 MSOS编码示意图

在MSOS编码的基础上采用一种基于全局、局部、随机初始化的非支配选择种群初始化策略。其中，全局选择通过平衡全局的机器负载来实现全局负载最小化；局部选择注重单一工件的工序最小加工时间，从而保证局部工序的加工时间最短；随机选择初始化随机产生总工序长度的工序集，再通过对应工序可选机器集随机选择一个机器形成机器集，保证初始种群具有一定的随机性。具体的初始化方法如下：

步骤1：分别执行局部初始化和全局初始化，产生两个种群数量均为Np的初始父代种群。

步骤2：合并两个初始父代种群，使用快速非支配排序的方法对父代种群进行初始排序筛选，删除父代种群中完全相同的初始个体。

步骤3：在初始个体被删除后，如果剩余的总种群数量少于Np则使用随机方法初始化父代种群进行补充，直到种群的数量等于Np。如果剩余的种群数量等于大于Np，则选择前Np个个体作为父代的初始种群。

2.2 解码

解码操作是指将编码生成的初始种群染色体转换成为可行的调度方案。本文中采用一种考虑机器空余时间的插入式贪婪解码策略[12]，生成主动调度解，从而最大化的利用机器资源。

2.3 交叉与变异

本文采用改进优先工序交叉算子（improved precedence operation crossover, IPOX）和多点保留交叉算子（multipoint preservative crossover, MPX ），以及单点最小加工时间机器突变和倒序变异的混合交叉变异方式来提高算法的寻优能力，同时设置了自适应的交叉变异算子。

2.3.1 基于工序的IPOX交叉

步骤1：将所有的工件p随机分配到两个数据集R1和R2，使得

步骤2：子代C1中复制父代P1包含在R1中的工序基因，子代C2复制父代P2包含在R2中的工件，保持复制前后的工序基因的位置不发生变化。

步骤3：子代C1之中空余的基因位置用父代P2不包含在R1中的工序基因依次填入，子代C2之中空余的基因位置用父代P1不包含在R2中的工序基因依次填入。

IPOX交叉方式的示意图如图3所示。

图3 IPOX交叉示意图

2.3.2 基于机器的MPX交叉

步骤1：随机生成一个长度为总工序数只包含0和1的数组R3。

步骤2：随机选择两条父代机器染色体M1和M2，交换M1和M2在R3数组出现数字1的相同位置，产生子代的机器集。

MPX交叉方式示意图如图4所示。

图4 MPX交叉示意图

2.3.3 混合变异策略

本文采用基于工序的倒序变异方式以及基于机器的单点最小加工时间突变的混合变异策略。基于工序的倒序变异，通过随机在工序染色体选择两个变异位置，然后倒序交换这之间的染色体片段。基于机器的单点最小加工时间突变，通过随机选择一个工序染色体位置，找到其对应的机器染色体片段，将对应的机器染色体片段替换为该工序在可选机器集中具有最小加工时间的机器。

2.4 自适应交叉变异算子

本文中采用基于迭代的自适应交叉变异算子来控制交叉和变异的概率。Pc(i)和Pm(i)分别表示每代的交叉和变异的概率，其具体的计算公式如下。

2.5 快速非支配排序与拥挤度算子

多目标优化问题的多个目标函数之间往往存在冲突，本文采用非支配排序和拥挤度算子对各个解集进行分层排序，从而区分出解集的优劣。

2.6 改进的精英保留策略

传统NSGA-II采用隐性的精英保留策略，这样容易导致后代出现大量的解处于第一非支配等级，同时解集之间的相似度也会较高。

本文提出一种动态调节的改进精英保留策略，控制算法迭代产生的后代种群，引入一个分布函数来限制父代种群中的精英数量，该分布函数通过两种策略进行动态调节。

当算法的迭代规模较小时，子代非支配等级为1的精英数量较少。此时希望尽可能的保留父代迭代得到的精英解，让子代继承这些优良特性。而针对第2-N个非支配的等级的种群，则使用比例系数λ1进行选择，如果某一支配等级选择后种群数之和超过了N，则该非支配等级依据拥挤比较算子选择个体数量，维持种群数量N保持不变。将这一阈值设定为子代非支配等级为1的精英数量小于父代种群规模的50%， λ1=0.5。此时精英保留策略如图5，其中Pt和Qt分别表示当前代数的父代种群和子代种群，Pt+1和Qt+1分别表示下一代的父代种群和子代种群。Pt+1的计算公式如下:

图5 第一种条件下的改进精英保留策略

当算法迭代到一定的规模时，子代非支配等级为1的精英数量已经较多，算法的迭代可能陷入停滞。此时使用比例系数 λ2来选择所有非支配等级的种群，以更多的比例接受一定程度的劣解，提高后代种群的多样性，防止算法陷入局部最优，同时我们也需要控制种群数量。设置 λ2的参数为0.6，此时精英保留策略如图6，Pt+1的计算公式如下。

图6 第二种条件下的改进精英保留策略

2.7 学习机制

NSGA-II的交叉变异算子在一定程度上可以防止算法陷入局部最优。为了提高算法的可靠性，采用一种基于最优个体的学习机制，针对算法迭代产生的优良种群进行邻域搜索，具体的执行过程如下：

步骤1：选择一条父代迭代后生成解集中支配等级为1的染色体P_1。

步骤2：在染色体上随机生成两个位置点A和B，记录两点之间的片段做为父代优良的基因片段。

步骤3：分别打乱A点左侧的基因片段和B点右侧的基因片段，重新组合生成新的染色体P_2。

步骤4：检查P_2染色体的调度的可行性，如果产生了不可行调度的解，则为其不可行工序在可选机器集中分配一台机器加工。确保染色体能够生成可行调度解后计算P_2目标函数值和非支配等级。

步骤5：比较P_1和P_2的目标函数值和非支配等级，如果P_2优于P_1则使用P_2替换P_1来调整新的父代种群。

学习机制的示意图如图7所示。

图7 学习机制示意图

3 算法仿真测试与分析

本文算法基于Matlab R2015a进行编程，并在Windows 10，AMD Ryzen 7-5800H，CPU 3.2 GHz，内存16 GB，64位操作系统上运行。设置算法的初始种群数量为100，最大迭代代数为200，交叉算子Pc的范围为[0.4,0.8]，变异算子Pm的范围为[0.01,0.1]。

3.1 改进初始化策略的有效性

为了验证本文所提出的改进初始化策略的有效性，使用随机初始化的NSGA-II算法和采用非支配选择策略INSGA-II算法做对比，以Brandimarte基准算例中的MK04数据集为例，设定目标函数为最小化最大完工时间，最小化瓶颈机器负荷，最小化总负荷，其余的所有参数均保持一致，两种算法各独立运行20次，选取最优的结果绘制进化曲线进行对比。

由图8～10可知使用非支配选择初始化策略INSGA-II算法在初始解集上均优于使用随机初始化策略的NSGA-II算法，同时其收敛的速度也较NSGA-II有一定的优势。通过对比算法在各个目标函数上的最终解集收敛值，INSGA-II在机器总负荷以及最大完工时间上均优于NSGA-II算法，说明了非支配选择初始化策略在求解该问题上较优。

图8 INSGA-II和NSGA-II完工时间进化过程

3.2 改进精英保留策略的有效性

为了验证本文所提出的改进精英保留策略的有效性，选取使用传统精英保留策略的NSGA-II算法与改进式精英保留策略的INSGA-II算法做对比，其余参数条件保持一致。选取Brandimarte中MK01的数据集进行测试，优化目标为最小化最大完工时间，最小化瓶颈机器负荷，最小化总负荷。两种算法独立运行20次，选择最好的非支配解集个数进行记录，如表2所示。

表2 MK01算例对比表

图9 INSGA-II和NSGA-II瓶颈机器负荷进化过程

图10 INSGA-II和NSGA-II总负荷进化过程

3.3 多目标优化算法对比实验

为了进一步验证本文INSGA-II算法性能，针对Kacem提出的 8×8，10×10和 15×10这 3个基准算例进行测试，并与Alzahrani J S[13]提出的抢占式约束规则（pre-emptive constraint procedure，PCP）算法，Soto C[14]提出的多目标分支界定算法 （multiobjective branch and bound，MBB）以及 NSGA-II进行对比。优化的目标函数分别为最小化最大完工时间F1，最小化瓶颈机器负荷F2，最小化总负荷F3，算例的结果对比如表3所示。

表3 Kacem算例结果对比表

由表中的数据可知INSGA-II算法在求解8*8的算例时得到的非支配解个数为4，多于PCP的3个和MBB的3个以及NSGA-II的2个，且分析数据可知[15,13,73]，[16,12,75]都比PCP的解集[15,13,76]，[16,12,78]更加好。在10×10的算例上，INSGA-II求得的非支配解数量均多于PCP以及MBB和NSGA-II，在15×10的算例上INSGA-II求得的非支配解个数少于PCP的3个，多于MBB和NSGA-II的1个。分析可知，INSGA-II算法能够有效的求解不同规模的多目标优化问题，并得到质量较高的解集。

3.4 优化调度方案决策分析

在MK04数据集测试，由于该数据集不包含能耗信息，故采用计算机随机生成数字的方式，添加机器的空载能耗和加工能耗。10个加工机器的空载能耗和机器能耗在[0.1,0.3]和[0.5,2]的范围内自动生成。生成的数字分别为[0.2,0.1,0.1,0.3,0.2,0.3,0.3,0.2,0.2]，[1.3,0.9,1.7,1.1,1.2,1.9,0.7,0.5]。采用INS-GAII算法优化3个目标函数，即最小化最大完工时间f1，最小化总负荷f2和最小化能耗f3。表3为运行中生成的24个非支配解。

生产决策过程之中，3个指标之间的权重有所差别。由于3个决策目标的值具有不同的量纲，需要将其归一化：

然后归一化的目标函数乘以相应的权重系数进行加权求和得到加权的目标函数：

假设决策者对环境指标要求比较高，希望获得环境友好型的决策，选取的权重系数矩阵W=[0.25,0.25,0.5]，计算得到的最优解目标函数如表4第22条所示，其最大完工时间为86，机器总负载为342，总能耗为390.2，加工信息甘特图如图11所示。

图11 环境友好型决策调度甘特图

表4 MK04算例Pareto最优解集表

4 结语

本文建立了以最小化最大完工时间、最小化机器负荷、最小化总能耗为优化目标的绿色柔性作业车间调度问题模型。为了有效的求解该问题模型，提出了一种改进的NSGA-II算法，设计了一种非支配的初始化策略，并采用插入式的贪婪解码策略进行解码。采用自适应交叉变异算子，结合IPOX交叉和MPX交叉的混合交叉方式，倒序变异和单点最小加工时间突变的混合变异方式，提高算法的搜索能力。针对传统NSGA-II解集多样性差、质量低的问题，设计了基于分布函数的改进式精英保留策略，并通过引入一种基于最优解的学习机制来增强算法的局部搜索能力。最后，通过两个基准测试算例对算法的性能进行了测试，并进行了决策分析，结果表明算法求解多目标优化问题的有效性。

未来研究将考虑不确定环境下的柔性作业车间调度问题，继续探索多目标优化算法的改进策略，提高算法求解的质量和效率。