机器故障下的柔性作业车间调度优化

刘道兴

（山东科技大学，山东 青岛 266590）

0 引言

车间调度问题最早是由JOHNSON 在20 世纪50 年代提出的[1]，到了20 世纪90 年代BRUCKER 扩展了车间调度理论，提出柔性作业车间调度（Flexible Job-shop Scheduling Problem，FJSP）[2]，随后众多学者又在FJSP 问题上加入了动态扰动，研究在扰动条件下的车间调度问题。

随着计算机技术的快速发展，启发式算法为解决FJSP问题提供了更好的思路，也逐渐取代了传统的调度规则和数学类方法。陈鸿海等[3]、尹爱军等[4]、景志强等[5]、曾强等[6]对非支配排序遗传算法进行改进研究，解决了相关的车间调度问题，并证明各自的改进在解决调度问题上的可行性。陈魁等[7]利用小生境粒子群优化算法解决了考虑工件运输时间的多目标FJSP 问题。赵博选等[8]使用基于多策略融合的Pareto 人工蜂群算法求解多目标的FJSP 问题。

该文将机器故障下的柔性作业车间调度问题分为2 个阶段：首先，采用智能算法求解出静态预调度方案。其次，在静态调度方案基础上提出了基于2 种重调度策略的组合重调度策略，并验证了该策略在解决机器故障下的FJSP 问题的可行性。

1 问题描述

该文将考虑机器故障的FJSP 问题分为2 个过程，首先是传统的静态FJSP 问题，其次是在静态调度方案基础上发生机器故障后的重调度。

FJSP 问题的具体描述如下：有n个工件在m台机器上加工，工件的工序数和加工工艺已经确定无法改变，并且所有工序在可选机器上的加工时间是确定的，选择不同机器的加工时间也不尽相同。调度的目的就是通过调整工序的加工顺序和选择加工机器找到更优的加工方案，以实现各项优化目标，所有工件生产完成后即调度结束。

研究FJSP 问题时要与实际生产状态相匹配，需要提出以下假设条件：第一，开始时，所有的机器都处于待机状态，且工件加工只能选择一台机器。第二，工艺顺序为确定顺序，在加工时不能发生改变，该工件的前道工序加工完成后才能对后道工序进行加工。第三，出现设备故障时，受到影响的机器停止加工，未受到影响的机器继续加工。第四，发生设备故障时，故障在一定时间内可以维修恢复。第五，工序时间包括加工时间和工作准备时间。第六，工件能在可加工机器上任意切换。第七，前、后工件之间没有约束关系。

2 模型建立

从最小加工总时间、最小机器总能耗、最小机器总负载3 个角度建立柔性作业车间调度优化模型。

2.1 最小加工总时间

最小加工总时间指的是最后一道工序加工完成后花费的总时间最短，是调度方案效率最直接的体现，如公式（1）所示。

式中：i为工件号；ti为工件i的加工时间。

2.2 最小机器总能耗

最小机器总能耗指的是从加工开始到所有工件加工完成机器所消耗的能源最小（包括空载与负载），如公式（2）所示。

式中：j为工序号；qi为工序数；z为机器号；m为机器数；Tijz为工件oij在机器z上的加工时间；oij为工件i的第j道工序；Xijz为决策变量，当工件i在机器z上加工为1，否则为0；Lz、ULz分别为机器z在负载下的能耗与空载下的能耗；CTz为oij在机器z上的完工时间。

2.3 最小机器总负载

总负载最小是指工件在机器上的加工时间最小，其计算如公式（3）所示。

3 问题求解

3.1 静态FJSP 问题求解

针对静态的多目标FJSP 问题，该文采用改进的灰狼优化算法进行求解。狼优化算法（GWO）是2014 年由澳大利亚学者提出的一个群智能优化算法[9]，其主要是模拟狼群的捕猎过程，具有收敛性强、参数少和易实现的特点，在求解车间调度问题上具有很大优势。但是该算法本身也存在一定缺陷。首先，GWO 作为非精确算法，在求解迭代过程中需要挑选一个或多个优秀个体去引导目标优化的方向，而FJSP问题涉及目标较多，个体优劣判断较难，会直接影响算法性能，因此需要采用孙新宇等[10]提出的方法，即引入非支配排序及拥挤度计算，以此来判断算法中的个体优劣。其次，针对GWO 线性收敛易造成局部最优解的问题，在孙新宇法改进的基础上，该文采用了一种非线性收敛因子，避免算法出现局部最优解的问题。

3.1.1 非支配排序及拥挤度计算

采用孙新宇提出的方法，引入非支配排序及拥挤度计算，经过快速非支配排序和拥挤度计算，得到种群中每个个体的非支配序和拥挤度，当且仅当个体i的非支配序大于等于个体j且个体i的拥挤度大于个体j，可得个体i优于个体j。

3.1.2 改进非线性收敛因子

作为群体智能算法，GWO 法有全局搜索和局部搜索2个过程，二者的平衡关乎算法收敛速度，进而影响算法求解的性能。在GWO 中，收敛因子a决定了算法是实现全局搜索还是局部搜索。传统的GWO 中，a随迭代从2 线性递减至0，但实际求解问题时算法的迭代常常不是呈线性的。在迭代初期，收敛因子a应当缓慢衰减，以保证算法实现全局搜索，找到更好的全局解。到了算法迭代后期，收敛因子a应当快速衰减，以保证算法在局部搜索，进而更加准确地找到局部内的最优解。此情况下的a线性收敛策略将无法满足算法迭代规律[11]，因此该文改进了收敛因子a的收敛方式，采用一种非线性收敛方式，如公式（4）所示。

式中：e 为自然数；t为迭代次数；tmax为最大迭代次数。

3.1.3 算法流程

改进后的灰狼优化算法步骤如下。步骤1：设置种群数量、算法参数以及种群迭代次数；步骤2：初始化种群；步骤3：解码得到优化目标的参数；步骤4：根据得到的优化目标参数进行非支配排序和拥挤度计算；步骤5：计算后用灰狼算子更新种群；步骤6：计算个体的适应度，最优的3个为α、β、δ三只狼；步骤7：判断算法是否达到最大迭代次数，是则输出结果，否则转到步骤4。

3.2 机器故障下的重调度求解

在静态预调度方案的基础上，当发生机器故障时，需要及时调整调度策略，以保证生产的稳定进行。该文针对机器故障下的调度策略的调整，采用重调度策略代替单一重调度策略，并结合2 种调整策略的特点，保证在不同情况下重调度策略的适用性。

3.2.1 右移重调度策略

发生机器故障后，直接调整故障机器上正在加工的工序或者将要在故障机器上加工的工序，直到机器可以加工工件，即为右移重调度策略。具体步骤如下：首先，确定故障机器、故障发生时间和故障修复时间。其次，分析确定出预调度中在故障机器上直接加工或者将要加工的工序集合。最后，根据故障的修复时间，将受到影响的工序右移，直到故障修复，满足工件的加工条件后开始加工，形成右移重调度方案。

3.2.2 完全重调度策略

当机器发生故障时，将方案切分，故障前的加工工序不变，将故障后所有机器待加工的工件完全重组，重新编码解码，得到新的调度方案，即为完全重调度策略。具体步骤如下：首先，找到故障发生时间进行切分，确定未开始的需要重新调度的工序集合，其中包括中断的工序和没有开始加工的工序。其次，确定所有机器的开工时间，机器的开工时间为故障发生后的最早空闲时间。最后，采用智能算法对确定好的工序合集进行编码解码，得到新的调度方案，与切分的调度前半部分方案组合即为故障发生后的完全重调度方案。

3.2.3 重调度流程

在重调度阶段，为了探究在不同情况下如何选择重调度策略，并探究组合重调度策略是否优于单一重调度策略，对2 种重调度策略分别进行求解试验。然后将结果进行对比，选取较优的方案作为最终的重调度方案。

4 仿真结果与分析

为了验证方案求解机器故障下FJSP 问题的可行性，采用标准车间调度数据MK01。该算例是一个工件数为10、机器数为6 的10×6 算例。

4.1 静态预调度方案

仿真试验的运行环境为Intel Core i7 CPU，主频2.60GHz，内存16GB，Windows 11，64 位操作系统，试验仿真软件为Python3.6.5，种群大小为100，进行150 次迭代，得到的预调度结果图如图1 所示，排产的甘特图如图2 所示。

图1 改进灰狼优化算法目标函数结果图

图2 中的矩形方块代表算法中工件的解码，即工件加工的顺序，其中的数字代表工件号，某工件按照时间顺序出现的次数代表该工件的第几道工序。部分加工顺序的举例如图3 所示。机器3 中第一个矩形方块中的数字1 代表工件1 的第一道工序，机器6 中第一个矩形方块10 则为工件10 的第一道工序，而机器3 第2 个方块中的10 为第二次出现，则为工件10 的第二道工序。依此类推，解码得到排产的加工顺序，即为可行的静态调度方案，具体如下。

图2 改进灰狼优化算法MK01 甘特图

图3 排产甘特图（局部）

预调度工序集：

预调度工序集对应机器集：

预调度工序集对应机器加工时间集：

4.2 重调度方案

为验证加工机器对加工的影响，本试验在预调度的方案基础上选取机器3 在第15min 发生故障，故障持续时间为6min，在不同的重调度策略下得到的排产甘特图如图4、图5所示。

图4 机器3 故障下右移重调度甘特图

图5 机器3 故障下完全重调度甘特图

从重调度排产甘特图可得，当故障发生在对后续工件加工影响较大的机器3 上时，完全重调度策略要优于右移重调度策略。采取同样的调度策略，当故障发生在机器5 对工件加工影响较小的机器且故障持续时间依旧为6min 时，右移重调度策略的完工时间为51min，而完全重调度策略的完工时间为54min，此时右移重调度策略要优于完全重调度策略。

综上所述，进行重调度时，如果只采用某一种重调度策略，可能在不同条件下会缺乏适应性，因此采用2 种重调度的组合策略，在不同条件下选择不同策略进行重调度，才能保证生产的高效进行。

5 结语

该文将机器故障下柔性作业车间调度问题分为静态预调度和机器故障下的重调度2 个部分。首先，采用了改进的灰狼优化算法，计算得到静态预调度方案。其次，基于右移重调度策略和完全重调度策略的特点，提出了一种组合重调度策略，验证了其比单一重调度策略在解决生产调度问题上更具适应性。

目前该文只考虑了2 种重调度策略，下一步工作需要挖掘更加完善的重调度策略，以提高重调度方案在解决动态调度方面的适应性。