柔性作业车间调度问题的多目标优化算法

徐 明，张剑铭，陈松航，陈 豪

(1.福州大学电气工程与自动化学院，福建 福州 350108；2.中国科学院泉州装备制造研究所福建省复杂动态系统智能辨识与控制重点实验室，福建 泉州 362200)

0 引 言

在过去，人们遇到多目标问题时往往通过简单加权的方式把多目标问题转成单目标问题进行求解。多目标问题的加权求解方式虽然简单易行，但却面临求解结果过于单一且加权系数事先难以确定的问题。Pareto方法综合多个优化目标，摒弃加权系数给出一组Pareto最优解结果供选择，使解集变得更为灵活多样[1]。

柔性作业车间调度问题(Flexible Job Shop Problem, FJSP)是典型的多目标优化问题，它对传统作业车间调度问题(Job Shop Problem)作了进一步的拓展，使每个工件都可以在其对应的机器集中进行加工，消除了机器资源的唯一限制，具有更强的适用性[2]。相较而言，FJSP更贴近实际车间的生产，有着重要的现实意义。

近年对于求解FJSP这类多目标问题的研究主要集中在智能优化算法领域。姜天华[3]把遗传算子插入灰狼算法中以增强算法的全局收敛能力，同时加入了变邻域搜索算法提高了局部寻优能力，使算法得到更好的全局最优解。Tang等人在文献[4]中建立包含生产时间间隔的多目标车间调度模型，并将粒子群算法与模拟退火算法进行混合以求解FJSP。程子安等人[5]为解决FJSP问题提出了多种群遗传算法，通过优化种群初始化方法与种群精英个体互换的方式，增强了算法的收敛性能。文献[6]提出了改进的遗传算法，该算法在每次迭代中通过设置解的阈值来选择进入精英库中的个体，使得解集更为多样化。文献[7-9]通过优化遗传算法初始解与使用改进的个体交叉、变异策略的方式大幅提高了解的质量与收敛速度。丁舒阳等人在文献[10]中使用粒子群算法求解FJSP问题时，把包含工序与机器信息的操作算子加入粒子的迭代中，使种群快速收敛。文献[11]针对NSGA-II过早收敛且容易陷入局部最优的问题，加入泊松、平均以及高斯算子以平衡算法全局收敛于局部寻优能力。

传统多目标优化算法求解FJSP问题时往往难以获得满意的解集个数且收敛速度与收敛精度较低。因此改进传统多目标优化算法以获得更优的收敛性能与更多样的解集显得尤为重要。

1 FJSP调度模型

1.1 问题描述

有n个工件需要在m台机器上进行加工，各个工件都有固定数量的工序。工序间有生产次序约束，各个工件在需要加工时应选择合适的加工机器，以便完成生产。其中，各个工序对应的可用加工机器集以及在机器集上的加工时间为已知条件。该问题旨在通过确定适当的机器分配和工序排列来寻找满足完工时间与能耗等优化指标的最佳调度方案。

1.2 FJSP多目标优化模型

本文求解的多目标FJSP同时优化最大完工时间与最大能耗，且满足以下约束条件[12]：所有机器在0时刻开启等待加工，机器上的最后工件加工结束后关机以节约能耗；工件只能在机器集中选择被某台机器加工，加工过程不能中途停止；工件的各个工序必须按次序进行，工件前一道工序若未结束则不可启动下一道工序；同一时刻每台机器上最多操作一道工序，每个时刻一个工件最多也只能被某台机器操作。

1)最小化最大完工时间。

柔性作业车间生产中往往是多个工件同时在不同机器上加工，直到所有工件被加工完成。最后一个工件被加工完成的时间就是最大完工时间，完工时间越小说明调度方案越好。数学表达可用如下公式表示：

f(1)=minCmax=min{Ci|i=1,2，…，n}

(1)

其中，Cmax代表最大的完工时间，Ci代表工件i的完工时间，n是工件总数量。

2)最小化最大能耗。

在现实的车间生产中，不仅机器加工工件时会产生能耗，机器等待加工时的空转也会产生能耗。因此，能耗可分为2个部分，数学表达式如下：

(2)

(3)

其中，Qj表示机器j在这次加工过程中产生的总能耗；Q为m台机器消耗能量的总和。因此，最小化最大能耗的数学描述可表示为：

f(2)=minQ

(4)

车间所有可使用的加工机器的功率信息如表1所示。

表1 机器功率表

3)最小化机器总负荷。

在生产加工时，不仅要尽可能地使加工能耗与最大完工时间最小，还要考虑机器的总负荷。因此，工序在选择加工机器时需要权衡机器的加工能耗与机器的加工时间，在能耗相同的情况下选择加工时间短的机器，以使机器总负荷最小化。机器总负荷最小化数学表达式如下：

(5)

其中，Tj表示机器j的总加工时间，Tload表示机器总负荷。

2 基于改进的NSGA-II算法设计

NSGA-II是由遗传算法改进而来，通过加入非支配排序思想使得算法具有运算速度与收敛性方面的优势。且该算法具有一次性获得多个Pareto解的能力，常被用在FJSP问题的求解中[13-14]。本文提出的INSGA-II算法主要将初始化方法、交叉与变异策略、交叉与变异算子进行改进，使算法在解集与收敛性方面得到提升。

2.1 基于机器与工序的分段编码策略

在NSGA-II算法中，针对问题选择恰当的编码方式能够良好地反映问题特征，同时使算法快速收敛并提高求解精度[15-16]。本文采用工序与机器融合的分段编码方式，工序编码部分的实数代表工件号，而相同工件号重复的次数依次代表该工件的工序。机器编码与工序编码是相对应的，表示相应位置工序的机器选择。该种分段编码策略可以保证染色体解的可行性，避免后续繁杂的修正操作。图1为机器与工序编码。

图1 机器与工序编码

2.2 混合初始化方法

在NSGA-II算法中，初始化策略影响着解的好坏与收敛速度，因此种群初始化是一个重要的步骤。混合初始化方法先让工序编码部分全部使用随机初始化方法，然后让对应的机器编码部分一半使用启发式初始化另一半使用随机式初始化。

启发式初始化方法在一开始就为工序选择可选机器集中加工时间最短的那台；随机初始化方法则是给工序随机指定某台可选设备。启发式初始化方法能够取得比随机式初始化方法更快的收敛速度，然而却在一定程度上影响种群多样性进而削弱算法全局搜索能力；随机式初始化方法可以提升种群多样性但是会降低收敛速度与算法稳定性。因此将2种初始化方法结合能够在保证一定收敛速度的同时增强算法全局搜索能力。

2.3 适应度函数与选择操作

根据FJSP模型中的优化目标，算法的适应度函数为：

(6)

其中，f(1)、f(2)、f(3)分别为式(1)、式(4)与式(5)中的最小化最大完工时间、最小化最大能耗以及最小化机器总负荷优化目标函数。因此算法需要衡量3个适应度函数，并根据计算后的适应度对个体进行非支配排序，同时计算处于同一支配层级的个体拥挤度[17]。

算法的选择操作选定二元锦标赛选择策略[18]，其思想为：先将种群进行非支配排序并对处于同一支配层级的个体进行拥挤度计算；然后从种群中有放回地抽取2个个体，选择支配层级高的个体进入子代种群，若支配层级相同则选择拥挤度小的个体；最后不断重复抽取选择操作，直至形成的新种群大小达到原种群的规模。

2.4 基于工序与机器的分段交叉策略

1)工序部分的交叉。

合适的交叉算子使子代继承父代的优良部分，同时提高后续种群的多样性，提升算法的全局收敛性。基于工序优先顺序的交叉(Precedence Preserving Order-based Crossover, POX)的优良特性决定了它更适合应用于FJSP问题[19]。POX交叉如图2所示，首先从所有工件中选择子工件集J1，然后子代1先继承父代1中与J1相同的基因，最后子代1的其余位置则由父代2与J1相异的基因填充。

图2 工序部分的POX交叉

2)机器部分的交叉。

为避免出现不可解，同时提高种群多样性，机器部分采用均匀交叉方式。均匀交叉如图3所示，首先在Parent1上随机选取r个点位(r

图3 机器部分的均匀交叉

2.5 基于工序与机器的分段变异策略

在本文编码方式下，工序部分可采用常见的两点交换突变，而机器部分由于各个工序对应的可选机器数量不同，为避免染色体修正操作，因此只在非遗传关系的父代子代之间进行个别基因的等位交换，以此达到突变效果(见图4)。具体步骤如下：

图4 工序与机器部分的变异

Step1选取2对复制了Parent1与Parent2基因的染色体作为Children1与Children2。

Step2在染色体基因上随机指定2个不重复的突变位置点。

Step3工序部分：Children1与Children2各自把2个突变位置上的基因进行互换。

Step4机器部分：Children1与Children2按照突变位置从Parent2与Parent1上复制基因。

2.6 自适应交叉、变异算子的设计

交叉算子ρc与变异算子ρm对算法的收敛性能起着重要影响[20]。ρc越大越容易产生新个体并增强种群全局搜索能力，但容易使种群不稳定且使局部寻优能力变弱；ρc过小容易使种群陷入局部最优并降低算法收敛速度。而ρm过大会影响种群稳定与收敛精度[21-22]，过小则容易使算法“早熟”。传统的NSGA-II算法使用数值固定的交叉、变异算子，显然无法满足对FJSP问题的求解。因此设计一种随迭代次数动态改变的自适应交叉、变异算子，数学描述如下：

(7)

(8)

2.7 算法基本流程

INSGA-II算法流程如图5所示。

图5 INSGA-II算法流程图

3 实验结果与分析

实验环境：CPU采用Inter Core i5 2.3 GHz，运行内存为8 GB，软件采用MATLAB R2016a。将INSGA-II算法与其他普通多目标优化算法在同等运行条件下运行，通过比较所获解集验证INSGA-II算法收敛性能与解集的丰富性。

mk01～mk07是由Brandimarte[23]设计的典型FJSP数据集，这7组数据包含不同的工件数、工序数、机器数以及加工时间。为更好地验证算法性能，测试分为双目标与三目标进行实验，其中，双目标采用最大完工时间与最大能耗为优化目标。

1)双目标实验。

表2为INSGA-II算法在mk01～mk07数据集上的实验结果。其中每个方括号代表一个解集，方括号中第一个数字代表最大完工时间，第二个数字代表最大能耗。

表2 mk01～mk07解集

表3为INSGA-II与NSGA-II在mk01～mk07进行实验的结果，选取各自解集中完工时间最小的解来进行对比。从表中可以看出，INSGA-II不但在解集数量上多于NSGA-II,且最大完工时间与最大能耗有明显减少。因此INSGA-II在解集多样化与收敛精度方面要优于未改进的普通NSGA-II算法。

表3 NSGA-II与INSGA-II对比

表4为GA、PSO、INSGA-II在mk01～mk07数据集上各自运行10次的平均运行时间，从表中可见，相较于传统的多目标优化算法，INSGA-II有着更快的收敛速度。

表4 算法运行时间对比

此外，图6为NSGA-II与INSGA-II在mk01数据集上运行得到的Pareto最优前沿解的对比，可以看出，INSGA-II不仅解集更为丰富，且获得的最大能耗与最大完工时间这2个优化目标的解也要更小，可见INSGA-II的全局收敛性能要更优。

注：图中时间和能耗为单位时间和单位能耗，无单位

使用mk01数据集进行实验测试，从INSGA-II算法求得的解集中获取一个调度结果，如图7所示。其中，纵轴为加工机器，横轴为最大完工时间，O2,3表示第2个工件的第3道工序，以此类推。此外，同一机器上的不同工件用不同灰度区分。从图中可看出，使用INSGA-II能够获得较优的调度方案。

注：图中时间为单位时间，无单位

2)三目标实验。

在mk01数据集上进行实验，同等条件下将NSGA-II与INSGA-II进行算法性能对比。三维的Pareto前沿对比结果如图8所示。从图中可以看出，INSGA-II所获解的范围更大，全局性能更好；INSGA-II解的个数也要更多，解集多样性得到了保持；INSGA-II算法寻找到的解集质量也要更优，可见其全局收敛性与局部搜索性要更好。

注：图中时间和能耗为单位时间和单位能耗，无单位

4 结束语

本文在考虑FJSP问题和多目标优化的特点后，构建了以最大完工时间、最大能耗、机器总负荷为优化目标的柔性作业车间调度模型。在模型优化目标下，提出一种改进的多目标优化算法用于该模型的求解。通过该算法可有效解决FJSP问题，得到满意的调度方案，为生产管理者提供多种选择方案。最后在Matlab平台上进行对比实验，验证了所提算法的有效性。