如何提高效益和降低成本是制造企业永远追求的目标。相关资料研究表明，在制造过程中，90%以上的时间将消耗在运输、等待加工等非切削过程中^[1]，因此制造企业需要合理进行生产调度才能缩短加工时间、降低生产成本和提高效益^[2]。作为制造企业车间生产管理的核心内容，生产调度在很大程度上是企业能否盈利的关键环节。生产调度的任务在于如何为每一个工件的工序在有限的加工机器上确定其加工顺序，以使一个或者多个目标达到最优^[3]。其中，柔性作业车间调度问题(Flexible job shop scheduling problem, FJSP)由于突破了机器约束条件的限制，每一个工件的不同工序可以在多台机器上进行加工，选择不同的加工机器所得到的优化结果不同。因此，FJSP更加符合实际的生产，对其更具有重要的指导意义。大多数对柔性作业车间调度模型的研究都是在静态环境下进行的，如黄志清等以完工时间和能量消耗为优化目标，对基于改进算法的柔性作业车间集成调度进行研究^[4]。然而，实际的调度过程中经常会出现一些随机的因素，如紧急订单的加入、订单取消、订单优先级改变、机器故障等，在这种情况下静态调度模型不再适用于实际的生产环境。所以，动态环境下柔性作业车间调度问题开始得到许多学者的关注。刘爱军等^[3]提出基于事件和周期驱动的混合再调度策略，并利用自适应遗传算法求解多目标柔性作业车间动态调度，通过生产实例仿真验证了该模型和算法的有效性和可行性。刘国宝等^[5]提出了基于事件和周期混合驱动的滚动时域优化策略，并进一步通过算例验证了该方法的有效性。文献[6]以工件延期及完工时间为目标，对机器故障和工件随机到达等动态作业车间调度进行研究。Liu等^[7]对模糊处理时间的动态柔性作业车间调度进行了研究。Kundakc和Kulak考虑到机器故障、新工件插入及加工时间变化的动态事件，以最小完工时间为目标，利用混合遗传算法进行求解，仿真结果表明该算法的有效性^[8]。Zhang等^[9]以新工件的加入、机器故障为动态事件，利用混合遗传禁忌搜索算法对多目标动态车间调度进行优化。刘明周等^[10]结合滚动时域窗口，利用混合粒子群算法对作业车间动态重调度问题进行研究并通过具体案例验证所提出方法的有效性。上述文献对动态柔性作业车间调度问题的研究，基本上都是基于滚动时域优化策略，利用固定周期驱动的重调度策略，然而并没有考虑到可变重调度区间对动态调度优化目标的影响。

基于上述分析，针对FJSP问题，本文建立了以完工时间最小化为优化目标的柔性作业车间调度模型。提出基于可变重调度区间的动态调度策略，并利用改进遗传算法进行求解。提出一种改进的种群初始化方法，进一步提高初始解的质量。仿真测试案例验证了所提出动态调度算法的有效性，从而为生产实际提供参考。

1 柔性作业车间调度模型

柔性作业车间调度可以描述为：有n个工件(J₁, J₂, J₃, …，J_n)在m台机器(M₁, M₂, M₃, …，M_m)上加工，工件J_i包含一道或者多道加工工序，每个工件的各个工序之间满足工艺的顺序要求，同时每道工序可能有多台机器可以被选择。FJSP研究的就是如何为每道工序选择一台加工机器，以及如何确定每台机器上的多个工序的加工顺序及加工开始结束时间，这种顺序不仅要满足工件工序之间的工艺顺序约束，还需要满足机器的占用约束，以最优化某个或者某些性能指标^[2]。另外，工序的装夹时间包含在工序的加工时间中，不考虑工件的运输时间。

首先对相关数学符号说明如下：

n—工件总数；

J—工件集合，其中J={J_i|(i=1, 2, 3，…，n)}；

m—机器总数；

M—机器集合，其中M={J_i|(i=1, 2, 3，…，m)}；

O_ij—工件J_i的第j道工序；

T_ijk—工件J_i的第j道工序在机器k上的加工时间；

S_ijk—工件J_i的第j道工序在机器k的加工开始时间；

E_ijk—工件J_i的第j道工序在机器k的加工结束时间；

n_i—工件J_i的工序数；

C_i—工件J_i的完工时间。

如果O_ij在机器k上加工，则x_ijk=1；否则x_ijk=0。

以最大完工时间最小为优化目标，建立柔性作业车间调度数学模型如下

$ \mathit{f}\text{=min}{{\mathit{C}}_{\text{max}}}\text{=min(max}_{\mathit{i}\text{=1}}^{\mathit{n}}\text{(}{{\mathit{C}}_{\mathit{i}}}\text{))} $

(1)

同一个工件的相邻工序之间必须满足先后顺序约束，因此，FJSP必须满足以下工序顺序约束

$ {{\mathit{E}}_{\mathit{ijk}}}\le {{\mathit{S}}_{\mathit{i}\left( \mathit{j}\text{+1} \right)\mathit{{k}'}}} $

(2)

式中：∀i∈[1, n]，∀j∈[1, n_i-1]，∀k, k′∈[1, m]。

机器占用约束表明机器k加工一个工序完成后才能加工其他工序

$ {{\mathit{E}}_{\mathit{ijk}}}<{{\mathit{E}}_{\mathit{{i}'{j}'{k}}}} $

(3)

式中：x_ijk=1，x_i'j'k=1，∀i∈[1, n]，∀j∈[1, n_i]。

加工过程中工序不允许中断，有

$ {{\mathit{E}}_{\mathit{ijk}}}{{\text{-}}}{{\mathit{S}}_{\mathit{ijk}}}\text{=}{{\mathit{T}}_{\mathit{ijk}}} $

(4)

式中：x_ijk=1，∀i∈[1, n]，∀j∈[1, n_i-1]，∀k∈[1, m]。

在同一个时刻同一个工序只能允许在一台机器上加工，有

$ \sum\limits_{1}^{\mathit{m}}{{{\mathit{x}}_{\mathit{ijk}}}}\text{=1} $

(5)

式中：∀i∈[1, n]，∀j∈[1, n_i]，∀k∈[1, m]。

$ {{\mathit{T}}_{\mathit{ijk}}}\ge \text{0, }{{\mathit{S}}_{\mathit{ijk}}}\ge \text{0, }{{\mathit{E}}_{\mathit{ijk~}}}\ge \text{0} $

(6)

式中：∀i∈[1, n]，∀j∈[1, n_i]，∀k∈[1, m]。

2 基于可变重调度区间动态重调度策略

动态作业车间调度是指在执行优化后的静态调度过程中，遇到譬如紧急任务插入、设备故障等动态事件时，系统能够做出及时响应，对加工任务进行再调度，以适应动态的加工环境。目前常用的动态重调度策略有基于周期性重调度、基于事件驱动重调度、基于周期与事件驱动相结合的重调度3种。基于周期的重调度能够根据每个加工周期的生产情况，全局对调度过程进行考虑，但它不能对动态事件及时有效得进行处理。基于事件的重调度对动态事件反应及时，但该策略缺乏从全局观方面进行考虑与分析。基于周期与事件驱动相结合的重调度策略则将两者很好地融合，但是该方法得到的结果也不一定是最优的。

基于以上分析，针对FJSP问题，本文提出基于可变重调度区间的重调度策略，即在动态事件发生以后，只对一定范围内的工件进行重调度，范围的大小根据动态事件直接影响到的工件来确定，其他区间中不被动态事件直接涉及到的工件的加工顺序不变，工序所在的加工机器也不变。

确定重调度区间的步骤如下：(1)确定动态事件影响到的工件；(2)将影响到的工件从调度区删除；(3)将剩余未受影响的工件合并；(4)将动态事件影响到的工件和未影响到的工件在一起进行重调度；(5)确定重调度后受动态事件直接影响到的工件的开始时间t₁与完成时间t₂；(6)重调度区间即为[t₁, t₂]。

以表 1的加工信息为例，首先利用遗传算法获得柔性作业车间静态调度的一个调度方案：2—3—2—2—5— 1—2—4—2—5—3—3—3—3—5—3—3—5—1—1—4—1—2—1—4—3—1—2—4—5—7—3—2—6—9—8—6—4—10—6—5—3—5—10—8—1—7—9—4—3—2—1—9—2—10—5—7—8—1—4(数字表示工件号，该数字在此序列中出现的次数表示其加工工序)，调度甘特图如图 1所示。自定义动态事件为机器M₁损坏且不可修复，直接影响到的工件有2，7，8和9，发生时刻为5时刻，如图 2所示。利用本文提出的可变重调度区间的动态调度策略获得的重调度方案如图 3所示。从图 3可以看出，工件5的第2道工序进行了后移，工件3的第3道工序和工件1的第1道工序进行了后移，使得不受动态事件直接影响的工件的加工顺序不变，工序所在的加工机器也不变。这里给出的只是一种基于可变重调度区间动态重调度策略方案，但是该方案并不一定是最优的，因此需要进一步通过优化算法对其进行优化处理。

3 改进遗传算法求解柔性作业车间动态调度 3.1 编码与解码

编码主要用来确定各工序所在的加工机器和加工顺序，因此采用双层编码方式可以很好地进行表达，具体表现形式如图 4所示。机器部分确定工序所在的加工机器，工序部分确定工序的加工顺序。举例：若工序O₁₁，O₁₂，O₁₃，O₂₁，O₂₂，O₂₃所在的加工机器分别为M₃，M₁，M₂，M₂，M₁，M₃，工序的加工顺序为O₂₁，O₁₁，O₁₂，O₂₂，O₁₃，O₂₃，则编码为312213211212，如图 5所示。解码为编码的逆操作，即根据编码确定工序的加工机器和工序的加工顺序的过程。

3.2 初始化种群

相比传统的作业车间调度问题，FJSP是一类更复杂的NP-hard问题。种群初始化的好坏对于遗传算法求解FJSP影响很大，而以往大都采用随机种群初始化方法进行初始种群的生成，但是这种方法提供解的质量往往不一定有保证。

本文提出以初始化机器、初始化工序和随机初始化相结合的方法对种群进行初始化，具体方法如下。

(1) 初始化机器

由于优化目标是完工时间，因此优先考虑加工效率高的机器，即对于加工的工序，优先选择加工时间少的机器。此阶段不考虑工件的加工顺序，具体步骤如下：(a)读取工序的加工时间表T；(b)求每道工序的最小值T_min；(c)根据T_min利用式(7)确定选取各工序的加工机器的概率；(d)根据各个工序所在加工机器的选取概率随机选择机器；(e)重复步骤(d)直到机器编码部分完全初始化。

$ {{\mathit{p}}_{\mathit{i}}}\text{=}\frac{\frac{\text{1}}{{{\mathit{T}}_{\text{mi}{{\text{n}}_{\mathit{i}}}}}}}{\sum\limits_{\mathit{i}}^{\mathit{apq}}{\frac{\text{1}}{{{\mathit{T}}_{\text{mi}{{\text{n}}_{\mathit{i}}}}}}}} $

(7)

(2) 初始化工序

当机器部分初始化以后，开始对工序部分进行初始化。按照顺序，从工序编码的第一位开始。每选择一个工件，则形成一个调度方案，根据选取可选工件后的完工时间来确定编码的初始值。由于优化的问题是完工时间，所以选取工件后的完工时间越小，选取此工件的概率就越大。(a)读取当前加工信息表a，具体描述如图 6所示；(b)计算选取可选工件后的完工时间mak_cur；(c)根据式(8)确定选取各工件的概率；(d)根据概率确定选取的工件；(e)重复(d)直到工序编码部分完全初始化。

$ {\mathit{p}_\mathit{i}} = \frac{{\frac{1}{{{\rm{ma}}{{\rm{k}}_{{\rm{cu}}{{\rm{r}}_\mathit{i}}}}}}}}{{\sum\limits_\mathit{i}^\mathit{n} {\frac{1}{{{\rm{ma}}{{\rm{k}}_{{\rm{cu}}{{\rm{r}}_\mathit{i}}}}}}} }} $

(8)

(3) 随机初始化

随机初始化步骤如下：(a)随机选取可选的加工机器；(b)从可选工件集中随机选择加工工件；(c)重复(a，b)，直到种群完全初始化。

3.3 选择操作

选择操作是种群中适应度值大的个体将被选择进化到下一代种群中，适应度值小的个体被淘汰掉，它反映了“优胜劣汰”的进化精髓。本文采用常用的轮盘赌法进行选择操作。

3.4 交叉操作

对工序的交叉操作采取张超勇提出的POX交叉^[11]。POX交叉过程如下：将工件任意分成J₁和J₂两个集合，交叉操作时，父代1保留集合J₁中基因的位置不变，其他位置基因则由父代2中J₂集合中相应位置基因来依次填补，具体实例如图 7所示(其中J₁由工件1和4组成，J₂由工件2和3组成)。

对机器的交叉操作在此采取任意产生0-1的方法。具体过程为：随机生成一个由0-1组成的染色体，该染色体的长度等于机器染色体的长度。保持两个机器染色体上的基因与0位置相对应的不变，交换两个机器染色体上与0位置相对应的基因，具体实例如图 8所示。

3.5 变异操作

利用随机选择一个基因位置，然后顺序交换两个基因片段，以保证解可行，具体实例如图 9所示。

对机器部分变异则采取依次后移基因的方法(最后一个基因则移动到首位置上)，以保证解可行，具体实例如图 10所示。

最终得到利用改进初始种群的遗传算法及可变重调度区间求解柔性作业车间动态调度流程图，如图 11所示。

4 实验与结果分析

为了证明本文提出的改进初始化种群方法的遗传算法和动态调度策略的有效性和可行性，利用文献[12]中的案例对柔性作业车间动态调度问题进行验证。遗传算法的参数设置：种群规模100，进化代数100，交叉概率0.8，变异概率0.1。

表 2显示的是利用本文提出的初始化方法和随机初始化方法获得的初始种群的性能对比结果。从表 2中可以看出本文提出的初始化种群方法可以获得优质的个体。

图 12是利用传统随机初始化种群方法获得适应度值的优化结果，图 13是利用本文改进初始化种群方法获得适应度值的优化结果。从图中可以看出，利用未改进的方法需要近80代才能获得最优解40，而利用本文改进的初始化种群的方法仅需要40多代便可获得最优解35。利用本文算法得到的静态调度最优解的甘特图如图 14所示。本文方法比文献[12]中利用改进算法获得的静态调度的最优解还减少了2个时间单位，所以本文提出的初始化种群方法是有效性。

另外，假设在时刻20机器6出现故障，利用本文改进的遗传算法和可变重调度区间方法进行动态重调度，动态事件发生后的重调度方案如图 15所示，动态重调度的结果对比如表 3所示。

从表 3重调度结果对比不难看出，运用本文所提出的基于可变重调度区间的动态调度策略后，之前需要在故障设备上加工而未完成的工件能够直接转移到具有相当加工能力的设备上进行加工，而没有必要等待故障设备修复之后继续加工，从而使完工时间大大减少。从表 3也可以看出，利用本文重调度策略和改进遗传算法后得到的任务完成时间比企业实际完成时间缩短了47.8%，比文献[11]的调度策略提高了5.4%，从而验证了本文所提出算法的可行性和有效性。

5 结论

(1) 提出了改进初始化种群的遗传算法，进一步提高了初始化种群解的质量。

(2) 建立了柔性作业车间动态调度数学模型，提出了可变重调度区间的动态重调度策略，具体对比案例验证了所提出算法的可行性和有效性，进一步对生产实际提供很好的指导作用。