靳彬锋，毕 利，李 浩

（宁夏大学 信息工程学院，银川 750021）

0 引言

柔性作业车间调度问题（flexible job-shop scheduling problem，FJSP）考虑了工件工序调度和机器选择的问题，贴近现实的生产过程，有着重要的应用意义和研究价值[1～5]。在实际的工业生产中，不可预知的事件随时有可能发生，比如紧急插入新的加工工件、原材料短缺或加工机器故障等事件，均会影响生产调度的结果。本文针对加工过程中的机器故障问题，给出了一种基于粒子群算法（particle swarm optimization，PSO）的优化策略。

近些年来，动态的FJSP引起众多学者的关注。高俊宇等[5]就动态车间调度与静态车间调度进行比较，列出动态车间调度问题的干扰种类。陈勇等[6]考虑到加工参数的非确定性和动态扰动等因素，将模糊概念引入到调度模型中，并利用GA算法进行求解。李平等[7]结合工序码和机器码构造了一种双层染色体编码的遗传算法用于解决三种常见扰动类型的动态车间调度问题。李素粉等[8]针对流水车间调度问题的三种情况进行研究，通过预测机器的期望故障来进行计算。Maroua Nouiri等[9]提出了用两阶段粒子群算法求解动态柔性车间调度问题。刘爱军等[10]将动态调度分为基于周期的调度、基于事件的调度和基于周期和事件的混合调度。

上述文献都对车间调度中加工机器故障的问题提供了解决方法，但研究重新调度方法的执行效率和对机器发生故障的概率预期还很少，即加工过程中机器发生故障的概率，以及故障发生时，对相应故障机器上待加工工件的重新调度安排效率的评价。本文设置了稳定性指标对重调度方法的效率进行评价，稳定值越高，说明重新调度的安排对初始化调度的安排影响越小，对优化目标的影响越小，调度效果越好。同时计算加工机器发生故障的概率，对于概率值越大的机器，被选择的概率越低，以保证调度的顺利进行。粒子群算法根据自己的速度来决定搜索位置，收敛速度快[11]。但也具有容易陷入局部最优和早熟问题的缺点，本文提出“淘汰”机制，将部分位置较差的粒子淘汰掉并重新生成相同数量的粒子作为补充，避免了算法陷入局部最优和早熟的问题。

1 柔性作业车间调度问题

1.1 FJSP的数学描述

FJSP可描述为：一组工件序列job={job1，job2，…，jobn}在一组机器序列machine={m1，m2，…，mm}上进行加工。其中每个工件jobi有多步工序。初始化调度的目标就是将工件的工序合理的分配到各个机器上去，在满足相关前提条件下使得目标函数达到最优。具体的假设如下所示：

1）调度开始时，每台机器都可以被使用，即当时间t=0时，每台机器都可以被使用。

2）调度开始时，任一待加工工件的第一步工序都可以被加工，即当t=0时，每个工件都可被加工。

3）每种待加工工件的任一工序在可用机器上的加工时间是确定的。

4）同一待加工工件的所属工序是有先后顺序约束的。

5）工件的加工时间应当包括该工件在机器上的准备时间和加工时间。

6）在相同时间内，每个待加工工件能且仅能在一台可用机器上加工。

7）在相同时间内，可用机器最多只能加工待加工工件的一道工序。

8）从前一个加工机器运输到下一个加工机器的运输时间是确定的。

1.2 符号说明

i：工序的自变量；

j：工件的自变量；

k：机器的自变量；

n：工件的数量；

nj：工件j的工序的数量；

m：机器的数量；

cj：工件j的完工时间；

Oij：工件j的第i道工序；

tijk：工序Oij在机器k上的加工时间；

Xijk：如果工序Oij在机器k上加工，则Xijk=1，否则0；

Sijk：工序Oij在机器k上的开始加工时间；

Eijk：工序Oij在机器k上的完成时间；

T*：最优调度方案的最大完工时间；

MBk：第k台机器的动态（工作状态）损耗率；

MFk：第k台机器的静态（闲置状态）损耗率。

1.3 约束条件

1.3.1 时间约束

cj＞0。工件j的加工时间必须大于0。

tijk＞0。工序Oij在机器k上的加工时间必须大于0。

S0jk≥0并且Sijk≥0。工件j在机器k上开始加工第一道工序O0j时，S0jk不能为负数，同时工件j在机器k上开始加工Oij时，Sijk必大于0。

Eijk≤F1。工件j在机器k上完成加工工序Oij时，Eijk小于等于F1。

1.3.2 资源约束

式(1)表示工序Oij在机器序列1，2，…，m中有且只有一次被选中的机会，同时每一次选中的总和即为工件j的工序数量nj。

1.3.3 费用约束

MBk＞0并且MFk＞0。机器损耗必须大于0。

1.4 目标函数

本文选取的三个目标为：最小化最大完工时间，最小成本和机器最大负荷。具体如下：

1）最大完工时间：

2）最低成本:

3）机器最大负荷：

2 面向机器故障的重新调度方法

2.1 关于FJSP的机器故障描述

面向机器故障的重新调度方法是在初始化调度的基础之上，考虑到机器在长时间的使用过程中发生故障的可能性较高一些，因此将机器故障作为扰动因素（不可预知发生时间）。重新调度方法需要对这种突发事件具有较好的优化处理能力。本文主要研究机器发生故障时，通过重新调度方法尽量减少故障对生产调度过程的影响。

假设在加工过程中，时间为t时某机器发生故障，则对应的最大完工时间如式(8)和式(9)所示：

式(9)中r表示发生故障的机器个数。

对应的加工成本如式(10)、式(11)和式(12)所示：

2.2 基于机器故障的重新调度策略

在柔性车间调度中，每一道工序可以由多个机器进行加工。因此当某台机器发生故障时，首先将故障机器的修复时间与重调度时间进行比较，如果机器的修复时间小于重调度时间则等待机器的修复然后继续执行之前所做的初始化调度表。如果修复时间大于重调度的时间，那么运用改进的粒子群优化算法对所有受影响的工序进行重排列（故障节点之后的所有未加工的工序）。故障修复时间是从机器发生故障时的时刻t1开始到该机器修好加入调度时刻t2的时间间隔T1。重新调度时间是从机器发生故障时的时刻t1到调度计划重新排程完毕的时刻t3的时间间隔T2。具体流程图如图1所示。

图1 重新调度策略流程图

2.3 稳定性指标

其中robustness指的是稳定性。Freschedule为机器发生故障时重调度所花费的时间，Fschedule为初始化调度所花费的时间，robustness的值越大则说明重调度的效果越好。

2.4 机器发生故障的概率

车间调度过程中机器发生故障的概率Mfr由品牌参数、机器使用率和使用年限共同决定。

式(14)中，γ1（γ1＞1）表示品牌参数，即机器所属制造商的品质信誉，值越大表示该机器的品质信誉越好。γ2（0 ＜γ2＜ 1）表示机器使用率的权值，机器使用率是某单一机器在整个调度过程中的工作时间占全部调度时间的比例。γ3（0 ＜γ3＜ 1）表示机器使用年限Y的权值，即机器按照使用年限进行相应的比率折旧。

3 改进的粒子群优化算法

3.1 粒子编码

算法采用整数编码对所有粒子进行离散化表述。粒子的编码长度由两部分组成，分别是待加工工件的工序编码部分和加工机器编码。工序编码的长度取决于工件的种类以及每种工件的所属工序数量。如果有p种待加工工件，每个工件有nj个工序，则工序编码的长度为：

加工机器编码的长度与工序编码的长度一致且与工序编码的位置一一对应，即粒子的长度为length×2。

以表1所示的一个加工序列为例。

表1 3×3的调度问题

从表1中我们可以得到待加工工件序列、加工机器序列和每个待加工工件的工序，其中待加工工件序列为J=[J1、J2、J3]和可供选择的加工机器组M=[M1、M2、M3]。第一行第一列的M1/M2表示工件J1的工序1只能在机器M1和M2上进行加工，然后根据机器发生故障的概率进行选择。由此，我们可以得到一个初始解即一个粒子的编码：

X=[1 2 1 3 2 3 1 3 2 2 3 1 3 2 2 3 1 1]

该粒子的长度为18，然后对该粒子进行拆分，前一部分即从第一位到第九位为待加工工件的工序编码，后一部分即从第十位到第十八位为加工机器的编码。具体如下所示：

工件的工序编码： Xi= [1 2 1 3 2 3 1 3 2]

加工机器编码： Xm =[2 3 1 3 2 2 3 1 1]

解码过程分别对应工序和机器。首先看待加工工件的工序编码序列Xi，“1”、“2”、“3”分别出现了三次，表示待加工工件J1、J2和J3的加工工序都有三步。以J1举例说明，“1”出现的第一次表示待加工工件J1的第一道工序，“2”出现的第一次表示待加工工件J2的第一道工序，“1”出现的第二次表示待加工工件J1的第二道工序。以此类推即可得到所有相对应的操作序列。

再看加工机器编码序列Xm，“1”、“2”、“3”分别出现了三次，表示加工机器M1、M2和M3各被使用了三次。以M1举例说明，“1”出现的第一次表示待加工工件J1的第二道工序在加工机器M1上加工，“1”出现的第二次表示待加工工件J3的第三道工序在加工机器M1上加工，“1”出现的第三次表示待加工工件J2的第三道工序在加工机器M1上加工。以此类推即可知道“2”和“3”所代表的实际意义。

3.2 粒子位置和速度的更新

在标准的粒子群算法中，粒子在空间中搜索的速度和位置的更新公式如下：

其中w为惯性常数；r1、r2为加速常数（或者加速因子）用来调节学习的步长，r1为自我学习因子，r2为群体学习因子；为区间[0,1]上均匀分布的随机数；是粒子i在第k次迭代中的第d维的位置；是粒子i在第k次迭代中的第d维的个体最优的位置，是群体在第d维的全局最优的位置。是为防止粒子飞出解空间，需要限制

3.3 算法的改进

粒子群算法的位置更新是通过粒子的惯性、全局搜索能力和个体记忆三部分组成，分别由惯性常数w，自我学习因子r1和群体学习因子r2三种参数共同来影响。因为惯性常数w的存在，粒子可以搜索未知的区域。算法开始时粒子具有较快的收敛速度，随着迭代的进行，部分粒子进入局部最优解，其他粒子可能会受到影响从而导致解集收敛至局部最优的位置。另外，粒子在最优解附近时，若“速度”过快会导致粒子在最优解附近震荡，使得收敛速度过慢或无法收敛。基于以上两点不足，本文引入“淘汰”机制，经过每一次迭代，将位置较差的粒子淘汰掉用以保持种群整体的优越性，每轮迭代淘汰10%的粒子。同时为了保证种群的规模，每次淘汰结束以后都会加入等量的新生成的粒子。针对最大完工时间最小化的目标，算法描述如图2～图7所示。

图2 种群初始状态

图3 种群迭代变化

图4 淘汰粒子

图5 插入粒子

图6 种群迭代变化

图7 最终结果

图中，中心的小圆圈的范围是所要求的最优解集的边界范围；椭圆形是淘汰适应度值低于要求的解的边界范围，随着迭代次数的增加，该范围会逐步缩小；矩形框为所求问题的边界范围。图2为种群的初始状态，所有的个体都随机分布在矩形范围之内，每个个体都有速度惯性、个体最优（pbest）和全局最优（gbest），所有的粒子根据适应度来改变自己的位置，一次迭代后如图3所示，将所有在椭圆形范围之外的个体全部淘汰掉，如图4所示，以保证种群的优越性。同时，为了保证粒子的多样性，避免粒子都被淘汰掉，在每一次迭代过程中重新生成与淘汰数量相同的粒子并将其加入种群中，如图5所示。再次根据适应度的值改变每个个体的位置并将椭圆形外的那些位置较差的粒子淘汰掉，如图6所示，反复进行淘汰、生成和加入，直至达到最大迭代次数，将中心的圆形范围内的粒子取出即为所求问题的最优解集，如图7所示。

3.4 算法流程图及步骤

改进的算法流程图如图8所示。

图8 改进的粒子群算法的流程图

具体步骤如下：

Step1：初始化粒子群种群；

Step2：得到初始粒子群的适应度以及个体最优pbest和全局最优gbest；

Step3：对粒子的位置和速度更新；

Step4：计算该粒子的适应度；

Step5：判断所有的粒子是否完成更新操作，若完成则进行Step6，否则返回step2；

Step6：更新个体最优解和全局最优解；

Step7：将位置较差的粒子淘汰，并将新产生的粒子加入种群中；

Step8：判断是否满足终止条件，若满足则终止算法，gbest为最优解，若不满足则返回Step2。

4 实验结果

本文使用的计算机操作系统为Windows 7，处理器为Intel（R） Core（TM） i7-3632QM，内存为8G。利用Matlab2014b仿真平台对改进的粒子群算法进行仿真模拟实验，结果如下：

本文分别使用3×4、8×8和10×15三种不同规模的FJSP进行仿真实验。算法参数经梯度下降法[12]实验后设置为：种群数量200，迭代次数200次，速度范围设置v=[-2,2]，惯性常数w=0.15，r1=0.5，r2= 0.7。实验独立运行20次取平均值，结果如表2所示。

表2 算法实验比较

从表2中可以看出，针对不同规模的FJSP，改进的粒子群算法和标准的粒子群算法相比，目标函数求解均有提升。得到的非劣解集仿真结果如图9～图10所示。

图9 标准PSO的非劣解集

图10 改进的PSO的非劣解集

本文选择8×8的调度问题进行求解，其中每个工件有3个工序，如表3所示，其中“-”表示该道工序在该机器上无法进行加工。

表3 实验的原始数据

根据表3提供的数据，采用改进的粒子群优化算法进行初始化调度，得到的甘特图如图11所示，最大加工完成时间为42个时间单位。

图11 改进PSO求解所得甘特图

现在假设机器3在时间点为16时刻时发生故障。得到的传统解决机器故障的重调度甘特图如图12所示。

图12 传统机器故障调度甘特图

图12中，机器故障的持续时间为51个单位时间，最大加工完成时间由初始化调度的42个时间单位增加到86个时间单位。

同时对受影响的工序利用改进的粒子群算法进行重新调度，得到的甘特图如图13所示。

图13 改进PSO求解机器故障甘特图

图13中，最大加工完成时间从86个时间单位缩短到36个时间单位，优化效果明显。

5 结束语

应用PSO算法求解含有机器故障的FJSP，首先在粒子群算法中引入“淘汰”机制来弥补粒子迭代过程中容易陷入局部最优和早熟的不足，然后根据重新调度方法对加工过程中的机器故障问题进行优化处理。最后通过仿真实验对比，证明了改进的粒子群优化算法求解柔性车间调度问题的优越性，对实际生产具有一定的理论意义。同时通过进行故障模拟实验，结果表明本文提出的重新调度策略可以有效的解决具有机器故障的柔性车间调度问题。

由于数据的有限性，还不足以对机器的各类参数进行细化，需要在今后的研究中进行优化。