动态环境下的柔性作业车间调度问题研究

张 琦， 张 彬

（沈阳建筑大学 机械工程学院， 辽宁 沈阳 110168）

0 引言

柔性作业车间调度问题 （flexible job-shop problem，FJSP）是目前最常见的车间调度类型。而在实际的生产制造车间中，在加工过程中会出现多种突发的动态事件，如人员短缺、交货期提前、设备损坏、紧急插单、生产材料短缺等事件的发生。 并且突发事件在现代生产车间中发生概率越来越高，因此对于动态环境下的FJSP 问题研究有着极其重要的意义。

近年来动态环境下的FJSP 问题的研究成为了热点。文献[1]针对带有设备故障的动态调度问题，其提出了一种两阶段的粒子群算法。 文献[2]针对动态环境下的FJSP问题， 提出了一种滚动窗口与模拟退火算法相结合的求解方法。 文献[3]针对设备故障，新工件的到达两类动态时间的发生，提出了一种混合重调度策略，并通过改进多差分进化算法对其进行求解。 文献[4]提出了一种双层深度Q 网络的在线重调度方法，来解决带有新工件到达的动态FJSP 问题，并通过与现有的调度规则和调度方法进行了比较，验证了该方法的通用性。 文献[5]针对作业取消、新工件到达、设备发生故障、工作时间变化的四种情况，提出了一种基于蒙特卡洛树搜索算法的重调度方法，来解决该动态环境下的FJSP 问题。 文献[6]通过将遗传算法与集成仿真相融合的方法对有生设备故障事件发生的动态环境下调度问题进行求解。

综上所述， 目前针对动态环境下的FJSP 问题研究，多数学者针对设备故障和新工件到达， 这两类动态事件的动态调度进行研究， 同时这两类事件是生产车间中最为常见的事件， 因此本文针对这两类动态事件提出了一种基于改进离散粒子算法的动态调度方法。

1 动态柔性作业车间调度数学建模

1.1 动态柔性作业车间调度问题描述

动态柔性作业车间调度问题（Dynamic flexible job shop scheduling problem，DFJSP）可描述为：有n 个待加工工件，可在m 台设备上加工。 所有工件的各条工艺路线已知并且唯一。 车间生产是一个动态的环境，生产订单也不是连续性的到达。 本文对实际加工过程中新工件到达、加工设备故障两类动态事件的处理，当动态发生时，要对现有调度方案进行及时合理调整，即根据现有系统状态，进行设备再分配以及工序再排序， 以使现有方案与新方案有序衔接在满足约束条件的情况下，优化某些性能指标。动态柔性作业车间调度需满足以下约束条件： 同一工件的各道加工工序之间有着明确的加工顺序； 各不同工件的工序无先后顺序；在一段时间内一台设备只加工一个工序；工件开始加工，无法中断；每道工序只能在设备上加工一次；在加工设备发生故障时，正在该设备上加工的工序可以中断；若因设备故障而重调度时，在该设备上正加工的工件，需重新进行加工。

1.2 动态柔性作业车间调度问题数学模型

上述由n 个待加工工件和m 台可选加工设备组成的动态FJSP，优化目标为最大完工时间，数学模型如下：

式中：M={Mh｜1≤h≤m}表示设备集合；J={Ji｜1≤i≤n}表示工 件 集 合；Ci表 示 工 件Ji的 完 工 时 间；O={Oij｜1≤i≤ni}表示工件的工序Oij集合；Mij={Mh｜Xijh=1}表示工序Oij的可选设备集；Tijh，Tijs表示工序在设备上的加工时间；Sijh，Segs表示工序Oij在设备Mh，Ms上的加工开始时间；Eijh，Eegs表示工序Oij，Oeg在设备Mh，Ms上的加工结束时间；Xijh=1 表示工序Oij在设备Mh上加工；Yijegh=1 表示工序Oij优于工序Oeg进行加工；TD表示重调度时刻。 式（1）为最小化最大完工时间；式（2）为同工件的不同工序有先后顺序；式（3）为工序在加工中，不能停止；式（4）为在任一时刻，在各台设备上只能加工一道工序；式（5）表示在重调度时刻，工序正在加工，设备需进行调整方式。

2 动态调度策略

本文选取基于周期性与事件驱动的混合重调度策略与滚动窗口技术对动态FJSP 问题进行处理。 对于加工设备损坏和新工件到达的情况， 应用基于事件驱动的重调度策略能够快速反应并给出新的调度方案。 对于在一段时间内没有动态事件发生的情况， 通过周期性重调度策略预先避免动态事件对生产加工的影响。

（1）设备故障处理策略。 在实际生产车间中，生产设备故障不可避免。 因此， 为确保生产任务的正常有序执行，必须进行再调度。 当加工设备发生故障时，将该设备上的后续工序， 安排至后续工序的其他可选设备上进行加工。对变化后的工序进行重调度，从而整个生产过程得到优化。 当此设备故障修复后再将该设备重新列入到各个工件各道工序的可选设备集中， 再对所有工件的后续工序进行重调度。

（2）新工件到达处理策略。在动态柔性作业车间调度的环境下，新工件到达的情况时有发生。新工件到达情况的发生时，不立即进行重调度，而是等待重调度周期的到达在进行重调度。

3 离散粒子群算法设计

3.1 编码解码

柔性作业车间调度问题涉及工序以及该工序的生产设备分配，所以本文采用设备选择基于工序顺序的整数编码[7]。

3.2 粒子的位置更新机制

本文对文献[8]中的粒子位置的更新公式进行了重新设计，使算法更适用于求解FJSP。 本文在此基础上，离散粒子群算法的更新方式进行设计，位置更新公式如下：

式中：ωt—惯性权重；C1—自我认知系数；C2—社会系数；—个体最优值；gBt—全局最优值；h（）—对粒子执行扰动操做。

公式（6）分为三部分，第一部分函数h（Xit）的作用为交换Xit中的分量（相当于粒子的飞行速度），粒子的速度变化包含粒子Xit的变化中。 此部分的更新应用了的变异操作来对其进行更新操作。 设备部分采用采用随机变异操作，工序部分采用插入式变异操作，以避免非法解的产生，同时减少了算法的运算时间。第二部分函数反映了对自身信息的继承，粒子与个体最优pBit进行交叉操作，工序部分采用文献[9]提出的IPOX 交叉操作。 设备部分采用均匀交叉的方式。 第三部分函数反映了粒子向全局最优粒子gBt的信息进行学习。其执行过程与第二部分函数执行过程相同。

4 实例仿真与分析

4.1 实例仿真

为了验证本章所提方法的有效性，在文献[10]中的案例基础上，依据实际加工车间中的加工环境，增加了设备故障、新工件到达两类动态事件的数据，并对各动态数据分别进行优化调度。 表1 中给出了1 个新到工件的可选加工设备以及对应的加工时间。

表1 新到达工件

（1）案例初始调度方案求解。 实际案例，利用本文所提的离散粒子群算法对该实际案例进行初始调度， 所求得初始调度方案如图1 所示，。 其中最大完工时间为43。在后面的动态调度时将该方案作为初始方案。

图1 动态调度方案甘特图

（2）设备故障重调度。假设设备M4 在时刻30 时损坏，并且无法快速地进行修复，因此需进行重调度，设备故障重调度方案甘特图，如图2 所示。

图2 设备故障重调度方案甘特图

（3）在初始调度方案的执行过程中，在时刻17 有一个新工件到达，并且在时刻18 时，到达周期性重调度时刻，进行重调度，新工件达到重调度方案甘特图，如图3 所示。

图3 新工件达到重调度方案甘特图

4.2 结果分析

通过分别对设备故障、 新工件到达两类突发动态事件的仿真调度试验研究， 在仿真实验结果中能够得出以下结论：

（1）应用基于周期性与事件驱动的混合重调度策略与滚动窗口技术对动态FJSP 求解，所求调度方案能够满足复杂多变的动态生产环境要求。因此，该方法能够解决动态车间调度问题。

（2）当发生突发动态事件后求得的重调度结果中，其完工时间均保持在合理可行的范围内， 其证明离散粒子群算法是求解动态环境下柔性作业车间调度方案的一种可行方法。

5 结论

针对动态环境下的FJSP 问题，首先建立了该问题数学模型， 并针对问题提出了一种基于改进离散粒子群算法的动态调度方法。 该方法结合滚动窗口策略以及基于周期性与事件驱动的混合重调度策略， 以适应动态环境下的FJSP 问题， 并通过对两类突发动态事件的仿真实验，证明了本文所提的方法对求解动态环境下的FJSP 问题的可行性。