考虑运输时间的多目标柔性作业车间调度研究

陈 魁，毕 利

(宁夏大学 信息工程学院，银川 750021)

1 引 言

柔性作业车间调度问题(Flexible job shop scheduling problem，FJSP)是经典车间调度问题(Job shop scheduling problem，JSP)的延伸.已知FJSP是一个NP-hard问题.目前，FJSP的求解方法主要集中在群体智能优化算法，如遗传算法[1]和粒子群算法[2]等.

粒子群算法(Particle Swarm Optimization，PSO)相较于遗传算法具有收敛速度快、容易实现等优点，在求解FJSP中被广泛应用.丁舒阳[2]提出了一种离散粒子群优化算法求解FJSP，将不同的交叉策略引入PSO使其离散化.Shao[3]通过PSO的全局搜索与模拟退火算法的局部搜索相结合求解FJSP的帕累托解，采用拥挤距离来识别粒子的适应度.Song[4]采用多目标粒子群算法中加入变邻域搜索策略提高了PSO的开发能力，通过分配规则和调度规则提高初始粒子的质量.Edilson[5]将PSO和随机重启爬山算法结合求解多目标FJSP.Rim[6]在求解FJSP时，提出了一种两级粒子群优化算法，将FJSP的两个子问题机器选择和操作排序分成两层处理.Huang[7]提出了一种基于教和学的混合遗传粒子群优化算法来解决多目标FJSP.仲于江[8]提出了一种将小生境技术和PSO相结合求解多目标FJSP的优化方法，基于小生境技术计算粒子的删除概率对非支配解的外部存档进行更新.Li[9]提出了一种求解多模态优化的小生境粒子群算法，在该算法中加入平衡因子，使得小生境划分更均匀.

工件移动是柔性制造动态性的最直接体现，考虑工件运输时间的FJSP更贴切实际生产[10].赵宁[11]建立了考虑运输时间的关键链优化方式，将运输时间集成到经典FJSP的析取图模型中，结合邻域搜索算法实现快速寻优，获得FJSP在考虑运输时间下的近优解.田旻等[12]设计了粒子群遗传混合算法求解考虑运输时间的FJSP，并在种群初始化阶段设计了一种考虑运输时间的初始化方式.Zhang[13]提出一种左移插入解码的改进遗传算法求解运输时间约束的FJSP.Dai[14]提出改进遗传算法求解在考虑运输时间下的最小能耗和完工时间的FJSP.Huang[15]结合免疫遗传算法和变邻域搜索算法，提出了一种混合算法求解考虑运输是时间和劣化效应的FJSP.Huang[16]将遗传算法与模拟退火算法相结合，解决了考虑运输时间的MOFJSP.

综上，在大多数研究中，PSO求解多目标FJSP时算法全局搜索能力不足，并且未有效解决PSO的早熟问题；考虑运输时间的FJSP求解仅在解码时考虑运输时间，而忽略了运输时间对粒子初始解质量的影响.本文考虑到多目标FJSP的解空间分布，建立基于Pareto支配的多目标优化模型，设计了一种PSO和小生境结合的算法来求解具有运输时间的多目标柔性作业车间调度问题.算法改进主要体现在3个方面：首先，在初始化阶段就考虑工件的运输时间，初始化选择工件的加工机器时动态选择完工时间最短的机器；其次，在粒子群算法的优化过程中，引入邻域搜索算法增强PSO的局部探索能力；再次，提出了一种无须共享半径的小生境划分技术，克服了利用小生境技术划分粒子种群时共享半径难以确定的问题，并通过该技术将粒子群均匀划分成多个小生境，提高PSO的全局搜索能力，有效避免PSO的早熟问题.最后，通过在Kacem数据集上做考虑运输时间的多目标FJSP仿真实验，证明本文方法在求解不同规模运输时间下的FJSP时的优越性.

2 问题描述与建模

2.1 问题描述

考虑运输时间的FJSP可以描述为：有n个工件在m台机器上进行加工，每个工件至少有一道工序，每道工序可以在至少一台进行加工，同一工件在不同机器之间的运输时间是确定的.该问题一方面要受到工序顺序和设备资源约束，另一方面受到工件在不同机器间传输时间的约束[12].因此，合理地安排工序的加工顺序，并为工序选择合适的加工机器，可以使考虑工件运输时间的FJSP的目标达到最优.为简化待研究的问题，本文采用如下假设：

1)工序的加工过程不能中断；

2)同一时刻同一机器只能加工一道工序；

3)每道工序在不同机器上的加工时间是确定的；

4)如果同一工件的前后工序在不同机器上加工，需要考虑工件的移动时间，否则，不需要考虑移动时间；

5)每个工件的首道工序之前和末道工序之后不考虑运输时间.

表1为一个柔性作业车间调度问题实例的加工时间表；表2为该实例的工件在机器之间的运输时间.

表1 加工时间表

表2 运输时间表

2.2 数学模型

符号说明：

Oij表示工件i的第j道工序；

Oi(j-1)表示工序Oij的前一道工序；

Oi′j′表示与工序Oij在同一台机器上加工的前一道工序；

Pijh表示工序Oij在机器h上的加工时间；

Thk表示机器h与机器k之间的运输时间；

Sijh表示工序Oij在机器h上的开始加工时间；

Cijh表示工序Oij在机器h上的加工完成时间；

Cj表示工件j的完工时间；

Cmax表示所有工件的最大完工时间；

本文综合考虑FJSP的最大完工时间(Cmax)、机器最大负载(Wm)和机器总负载(Wt)，建立最小化目标的数学模型，该模型的目标函数为公式(1)～公式(3)：

(1)

(2)

(3)

约束条件：

Cijh=Sijh+Pijh·xijh

(4)

Sijh=max(Ci(j-1)k+Tkh，Ci'j'h)

(5)

公式(4)表示工件按照工艺顺序进行加工，工序的完工时间等于开始时间和加工时间之和；公式(5)表示在加工过程中工序受工艺和运输时间的约束，只有当机器不被占用且工件到达机器时才能开始加工.

2.3 多目标优化

本文采用基于Pareto支配的多目标优化方法，其中Pareto支配的定义为：对于决策空间中的两个决策变量a和b，对∀i∈{1，2，…，G}有fi(a)≤fi(b)，且∃i∈{1，2，…，G}使得fi(a)

为测试算法的性能指标，令算法A得到的Pareto解集为PFA，所有算法得到的Pareto解集为PFT，解集PFT中解的个数为nT；算法的非支配性指标QS和收敛指标GD定义如下：

1)解的非支配性QS：令解集PFA和解集PFT的交集有mA个，则算法A得到Pareto解集的QSA指标定义为：

(6)

公式(6)可知，若QSA的值越接近1，则算法A求得解的非支配性越高，在所有算法求得非支配解集中占的比例越大.

2)当代距离指标GD：令解集PFA中解的个数为nA，解集PFA距离真实非支配解前沿PFT的距离GDA定义为：

(7)

公式(7)中Di表示解集PFA中第i个解到PFT中最近点的欧式距离，可知GDA的值接近0说明算法A求得解集到真实Pareto前沿距离越小，解集PFA收敛效果越好.

3 小生境粒子群算法求解考虑运输时间的FJSP

3.1 编码与解码

本文采用仲于江[8]提出的整数编码实现PSO在非连续域上求解问题.粒子编码分为两个向量，即机器选择向量MS和工序排序向量OS，其中，OS向量中从左到右工件号p出现的次数q表示该工件的工序号，记为Opq；MS向量从左到右按工件的工序顺序排列，元素值表示对应工序所选择的机器号.

以表1的3*3FJSP为例，对某个可行解进行粒子编码如图1所示，图1中OS向量表示加工顺序，MS向量表示对应工序所选择的加工机器，例如MS向量的第1个元素“1”表示工序O11选择在机器1上加工.

图1 粒子编码

在对粒子进行解码时，先根据OS向量得到待加工工序，再根据MS向量找到该工序选择的加工机器，在机器上从左向右寻找空闲时间段，若该时间段可以满足开始时间和加工时间的要求，将工序放在该时间段加工，如果没有满足要求的空闲时间段，则将工序放到机器末尾加工.

3.2 动态初始化

初始解的优劣直接影响算法的求解效率和求解质量[12].考虑到运输时间会直接影响初始解的优劣，本文设计了一种动态初始化的方法，在初始化过程中考虑加工时间和运输时间，为每道工序选择完工时间最短的机器进行加工.具体方法为，随机初始化OS向量，从左向右依次选择OS向量中的工序，为当前工序选择完工时间最短的机器记录到MS向量的对应位置；其中机器选择向量MS确定方法的伪代码如图2所示.

图2 MS向量的伪代码

3.3 离散粒子群算法

基于丁舒阳等[2]提出的离散粒子群算法(Discrete Particle Swarm Optimization，DPSO)，本文引入自适应惯性权重，设计一种自适应DPSO的粒子位置更新方式，如公式(8)所示.

(8)

F1操作算子表示粒子受当前位置影响的惯性运动，在DPSO中体现为粒子变异.具体操作为分别对OS向量和MS向量进行调整，其中基于OS的变异为：随机交换OS向量中两个位置的元素，实现对工序加工顺序的调整；基于MS的变异为：随机选择一道工序，在该工序的可选机器集中随机选一个与当前机器号不同的机器号替换MS向量中的对应元素，如果该工序只能在一台机器上加工，则不做任何改变.

F2表示粒子受个体的当前最优位置影响进行的粒子运动，F2操作算子在OS向量中进行POX交叉策略，在MS向量中进行RPX交叉策略，其中POX交叉策略和RPX交叉策略的具体操作见文献[2].F3表示粒子受当前全局粒子最佳位置影响进行的粒子运动，F3操作算子采用RPX交叉策略对MS向量进行调整.

公式(8)中ω表示惯性权重，本文采用自适应的ω变化策略，如公式(9)所示，ω的值随进化代数在[ωmin，ωmax]区间内线性减小，公式(9)中t表示当前进化代数，G表示总代数.

(9)

3.4 局部搜索算法

DPSO在粒子运动过程中受自身位置的惯性影响导致算法搜索不稳定，故本文引入邻域搜索算法提高DPSO的稳定性，具体实现为：每代粒子位置更新完成之后，对每个粒子进行局部搜索，即每个粒子生成它的邻域解，如果邻域解比粒子当前解优，则用邻域解代替当前解，否则不做改变.对该邻域搜索算法重复进行Km次，Km即为局部搜索代数.

本文在局部搜索算法中针对工序排序和机器选择设计了不同的邻域解的产生方式.工序排序部分通过倒置、插入和交换操作来移动工序顺序调整OS向量产生邻域.例如，对粒子[31321213]的第3个位置和第6个位置进行倒置操作后的粒子为[31212313]，进行插入操作后的粒子为[31321213]，进行交换操作后的粒子为[31221313].机器选择部分随机选择MS向量中一个位置，确定该位置对应的工序，在其对应工序的可加工机器集上随机选择一台与当前机器不同的机器替换，若该工序只有一台可加工机器，则另随机选择MS向量的一个位置，同上进行机器替换.

3.5 小生境粒子群算法

小生境技术的核心为将种群划分成多个小生境，常见的划分方式是以某一粒子为小生境中心，根据小生境半径确定其他粒子是否在该小生境中.这种小生境划分方式需要确定小生境半径，而且不能均匀划分小生境，在以往的研究中并没有确定小生境共享半径的有效方法.本文设计了一种不需要小生境半径的种群划分方法，具体操作为：先根据小生境数量确定每个小生境应该包含的粒子数S，再求出种群的Pareto解GB，以GB为中心找到与GB欧式距离最近的S-1个粒子，将包含GB在内的这S个粒子划分到一个小生境中；同理，求出剩余种群的Pareto解，在剩余种群划分出S个粒子的小生境；以此类推，直到所有粒子均划分完毕.该小生境划分方式的伪代码如图3所示.

图3 小生境划分的伪代码

粒子群优化初期粒子间分散比较均匀，可通过小生境技术将种群划分为更多相同大小的小种群，保证算法的全局搜索；随着进化代数的增加，需要减少小生境数量使算法收敛到最优解，还需满足当前种群的均匀划分.设计了一种满足上述要求的小生境数量随进化代数递减的方法，假设种群规模P=100，进化代数G=100，对该规模粒子群的小生境数量递减方式的代码如图4所示，图5为该实例的小生境数量变化趋势图.

图4 小生境数递减的伪代码

图5 小生境数递减图

3.6 算法整体步骤

小生境粒子群算法(NPSO)求解考虑运输时间的多目标FJSP时的算法流程图如图6所示.

图6 算法流程图

4 仿真实验

本文采用Matlab R2018b编程，运行环境为Intel(R)Core(TM)i7-7700 CPU @3.6GHz，RAM 8GB；本文在标准算例Kacem数据集的8×8、10×10和15×10三组实例上进行仿真，分别验证动态初始化的有效性和NPSO求解考虑运输时间的多目标FJSP的有效性和可行性.Kacem标准算例没有运输时间，故随机生成0-1、1-5之间随机分布的两类运输时间[16].为便于实验对比，本文采用文献[16]的两类运输时间数据.仿真实验的主要参数设置为：种群规模P=100，进化代数G=100，邻域搜索代数Km=10，学习因子c1=0.5，c2=0.8.

4.1 验证动态初始化

验证考虑了运输时间的动态初始化对算法求解质量的影响，具体的实验设计为：分别在0-1和1-5两类运输时间下的3组Kacem实例中通过随机初始化和动态初始化得到两组初始粒子群，将随机初始化得到的粒子群作为对照组.在0-1运输时间下的Kacem算例在两种初始化方式得到的初始解和经过DPSO优化得到的最优解的结果见表3；在1-5运输时间下的Kacem算例通过两种初始化方法得到的初始解和最优解的结果见表4.表3和表4中的值为10次实验的平均值.

表3 不同初始化的初始解和最优解(0-1运输时间)

表3和表4可知，通过动态初始化得到的初始解均优于随机初始化得到的初始解，且通过动态初始化种群经过DPSO优化后的最优解均优于随机初始化种群优化后的最优解.

为了直观体现动态初始化对粒子群算法优化过程的影响，以实例15×10为例，比较两类运输时间下动态初始化和随机初始化两种方式产生的初始种群，在DPSO优化过程中各粒子完工时间平均值的收敛过程.图7表示在0-1运输时间下实例15×10完工时间均值的收敛图，图8表示在1-5运输时间下实例15×10完工时间均值的收敛图；可见通过动态初始化产生的初始种群在DPSO优化过程中的收敛效果优于随机初始化产生的种群.

图7 实例15×10完工时间的收敛图(0-1运输时间)

4.2 验证NPSO求解考虑运输时间的多目标FJSP

验证小生境粒子群算法(NPSO)在求解考虑运输时间的多目标FJSP时的性能，对Kacem的3组案例分别在0-1和1-5两类运输时间下进行仿真，将NPSO与DPSO及Huang[16]提出的GASA进行比较.

表5和表6分别给出了Kacem测试集中8×8、10×10、15×10三组实例在两类运输时间下各算法求得的非支配解集.

表5 各算法在Kacem数据集上的最优解(0-1运输时间)

表6 各算法在Kacem数据集上的最优解(1-5运输时间)

表7和表8为两类运输时间下各算法在Kacem数据集上求解的性能指标对比结果.

表7 各算法求解的性能指标对比结果(0-1运输时间)

表8 各算法求解的性能指标对比结果(1-5运输时间)

由表7可知，NPSO在0-1运输时间下的3组算例上求得的解集的非支配性指标QS均大于DPSO和Huang[16]提出的GASA，说明NPSO算法得到的解集的非支配性较高，解的质量较好.NPSO得到解集的收敛指标GD在8×8和10×10算例中均接近0，在15×10算例中的收敛指标GD为0.57，明显小于DPSO和GASA的1.55和1，说明NPSO得到的非支配解集距真实Pareto前沿的距离最近，该解集相较于其他两个算法得到的解集的收敛性较好.

由表8可知，NPSO在求解1-5运输时间下的Kacem算例时，得到解集的非支配性指标QS均小于DPSO和GASA的QS，说明NPSO算法得到非支配解集的质量最好.在收敛性指标GD的比较中，NPSO和GASA算法在算例8×8上得到解集的GD都接近0，NPSO在算例15×10中得到解集的GD为0.32均小于GASA和DPSO的1.85和2.39，说明NPSO算法得到解集的收敛性较好.

综上，NPSO在两类运输时间下的FJSP算例中得到非支配解集的收敛性和分布性均优于未改进的DPSO和Huang[16]提出的GASA，尤其在求解高维度算例时NPSO得到解的质量更高.

5 总 结

本文针对考虑运输时间的多目标FJSP，提出一种将小生境技术和离散粒子群算法相结合的优化算法，构建了以最大完工时间、最大机器负载、总机器负载为最小优化目标的多目标优化模型.首先，在粒子群初始化阶段，提出了一种动态初始化方法产生考虑工件加工时间和运输时间的初始种群，提高初始种群的质量.其次，针对传统粒子群算法的不稳定性和易早熟现象，采用邻域搜索算法提高粒子群算法在优化过程中的稳定性，并将小生境技术与粒子群算法结合，给出一种以Pareto解为中心多次迭代的种群划分方法，降低全局最优解对粒子位置更新的影响，扩大粒子搜索空间，有效避免算法陷入局部最优解.最后，在Kacem标准数据集上做不同规模运输下的仿真实验，结果表明，动态初始化可提高粒子群算法的优化效率，小生境粒子群算法在求解考虑运输时间的多目标FJSP时是可行有效的.