作业车间调度问题(job-shop scheduling problem, JSP)最早由GAREY提出，并被证明是一个NP-Hard问题^[1]。柔性作业车间调度问题(flexible job-shop scheduling problem, FJSP)是JSP的拓展问题，不同于JSP，FJSP中一道工序可在多台机器上加工，也已经被证明为NP-Hard问题^[2]。因其复杂性、不确定性和多约束性等特点，学者一般会选用智能优化算法来求解车间调度问题，例如遗传算法^[3]、灰狼算法^[4]、蚁群算法^[5]等。

近年来，大量学者对FJSP进行了深入的研究，比如石小秋等^[6]以最小化完工时间为优化目标，提出一种自适应变级遗传杂草算法求解FJSP。李明等^[7]针对具有顺序准备时间(sequence dependent setup time, SDST)和关键目标的低碳FJSP，给出了一种有效策略加强对关键目标优化的同时兼顾非关键目标的持续改进，提出了一种新型帝国竞争算法求解该问题。但是上述文献没有考虑到工件的批次和批量，引入批次和批量之后的FJSP更加贴近实际，有着重大研究价值。徐本柱等^[8]提出了基于工序分批调度的概念，建立了以关键路径工序为中心的分批调度模型并证明了该模型的有效性。李聪波等^[9]以车间总能耗最低和完工时间最小为优化目标建立了多工艺路线柔性作业车间分批优化调度模型，并采用多目标模拟退火算法对模型进行优化求解。

在实际生产中，工件的加工是制造过程的最底层，加工完成的工件需要组装为组件再由组件组装为成品，而无论是组件或者成品都有其物料清单(bill of material, BOM)需求。因此，把装配过程考虑到调度问题中是有必要的。柔性装配作业车间调度问题(flexible assembly job shop scheduling problem, FAJSP)是在FJSP的基础上考虑工件的装配关系约束的更为复杂和常见的问题。在FJSP中完工时间是指最后一个工件的最后一道工序的加工完成时间，而在FAJSP中完工时间是指最后一个成品的装配工序的完工时间。学者Nourali等^[10-11]最早建立了FAJSP的混合整数规划数学模型，并在静态环境中以makespan为优化目标提出一种粒子群算法进行求解。但是其并没有考虑到动态环境因素，相比于静态车间调度问题，动态车间调度问题(dynamic job-shop scheduling problem, DJSP)与实际的生产环境更为相似。DJSP在静态调度的基础上需要考虑各种突发事件，比如机器损坏、紧急插单、工件交货期改变或者物料延迟等，其中机器损坏是动态事件中常见的事件之一，也是本文主要研究的动态事件。针对动态调度，Zhang等^[12]提出了一种名为混合多智能体/蚁群算法(hybrid MAS/ACO, HMA)的结合了多智能体系统协商和蚁群优化的方法，并利用实验证明了该方法在求解DFJSP上的有效性和可行性；刘爱军等^[13]对遗传算法进行改进并结合滚动窗口再调度技术，设计了基于事件和周期驱动的重调度策略用于解决DFJSP；Baykasoǧlu等^[14]利用贪婪随机自适应搜索算法，给出了一种具有机器容量约束和建立次数依赖于序列的FJSP和DFJSP的求解算法并验证了其适用性。针对FAJSP的动态调度，杨小佳等^[15]考虑现实生产中存在的随机扰动，采用了完全反应式与预测−反应式两类动态调度策略，并提出了相应的优先度规则算法和周期性滚动遗传算法用于求解该问题。

目前DFJSP已有大量研究，但是考虑到工件批量和装配因素的研究却十分匮乏。基于上述分析可知，综合考虑批量加工与装配联合调度的FAJSP具有重大的研究价值，本文将该问题描述为：柔性加工与装配作业车间分批联合调度问题。本文以最小化最大完工时间为优化目标，在考虑机器故障的基础上，建立了柔性加工与装配作业车间动态调度模型，并利用改进遗传算法进行求解。

1.   问题描述与数学模型

1.1   问题描述

本文研究的是柔性加工与装配作业车间分批联合调度问题，包括静态、动态调度问题，其中静态调度问题可以描述为：给定一组待生产的产品，其装配结构已知，同一车间中有 $m$ 台不同的加工机器用来加工工件， ${a_m}$ 台不同的装配设备用来装配工件， $n$ 种工件在 $m$ 台加工机器上加工，各工件包含多道工序且工序顺序固定不变，每道工序可在多台不同的机器上加工，各道工序在不同机器上的加工时间可能不同。完成加工的工件均由装配设备装配，这里本文提出装配柔性，类推工件加工柔性，即同一组件可选择不同的装配设备进行装配，在不同设备上的装配时间可能不同。调度的目标是为每一道加工工序和装配工序分配机器与设备，使成品的最终完工时间最小。

动态调度在静态调度的基础上考虑到车间紧急事件的影响，系统对该事件做出应急反应。针对动态调度问题的研究来分类，可将其分为3类：周期性重调度、事件驱动重调度以及周期性和事件驱动混合重调度^[16]。本文考虑机器故障，为了及时响应动态事件，采用基于事件的重调度策略。

1.2   数学模型

本文将在以下假设说明的前提下建立上述问题的数学模型：

1) 本文采用等量一致分批策略^[17]；

2) 一道装配工序同一时刻只能在一台装配设备上进行装配；

3) 在整个调度作业过程中最多只有一台机器发生故障；

4) 机器故障后可以经过维修时长 $ {L_t} $ 后继续投入使用；

5) 机器故障时加工到一半的工件视为废品，应取出一个新的备用工件重新加工；

6) 各种工件、组件最终组装成同一种成品。

①相关符号定义

$i$ ：工件号， $i = 1,2 \cdots ,n$ 。

$k$ ：加工机器号， $k = 1,2, \cdots ,m$ 。

$ {B_i} $ ：工件 $i$ 的总批量。

$b$ ：加工批次号。

$ {B_{ib}} $ ：工件 $i$ 的 $b$ 批次的批量。

${O_i}$ ：工件 $i$ 的工序数。

$j$ ：加工工序号， $j = 1,2, \cdots ,{O_i}$ 。

${P_{ibj}}$ ：工件 $i$ 的 $b$ 批次的第 $j$ 道加工工序。

$u$ ：装配设备号， $u = 1,2, \cdots, {a_m}$ 。

$z$ ：组件号， $z = 1,2, \cdots ,d$ 。

$c$ ：成品号， $c = 1,2, \cdots,f$ 。

${\text{R}}{{\text{Z}}_z}$ 、 ${\text{R}}{{\text{C}}_c}$ ：当前预组装件 $z$ 和成品 $c$ 的数量。

${A_{zu}}$ 、 ${A_{cu}}$ ：组件 $z$ 和成品 $c$ 在装配设备 $u$ 上的装配工序。

②约束条件

式(1)为目标函数，即最小化成品的最大完工时间：

式中： ${C_{\max }}$ 为最大完工时间； ${{T}}_{{\text{C}}_u}$ 为成品在装配设备 $u$ 上的装配完工时间。

式(2)为各工件各批次的加工工序之间的约束关系：

式中： ${{t}}_{{\text{SP}}_{ibj}}$ 和 ${{t}}_{{\text{FP}}_{ibj}}$ 分别为 ${P_{ibj}}$ 的开工时间和完工时间。

式(3)表示加工工序 $ {P_{ibj}} $ 在同一时刻只能在一台加工机器上加工：

式中 ${X_{kibj}}$ 取值为0或1，若 $ {P_{ibj}} $ 在机器 $k$ 上加工， $ {X_{kibj}} = 1 $ ，否则 $ {X_{kibj}} = 0 $ 。

式(4)为划分批次后的总工序数， ${p_i}$ 为共件 $i$ 的批次数。

式(5)表示同一时刻一台加工机器只能加工一道工序：

式中 $ C $ 表示一个足够大的正整数，若机器 $k$ 上的 $ {P_1}({P_i}_{_1{b_1}{j_1}}) $ 先于 $ {P_2}({P_i}_{_2{b_2}{j_2}}) $ 加工， $ {Y_{kP}}_{_1{P_2}} = 1 $ ，否则， ${{t}}_{{\text{P}}_1}$ 为 $ {P_1}({P_i}_{_1{b_1}{j_1}}) $ 的单件加工时间。

式(6)表示同一时刻一台装配设备只能进行一道组件或成品的装配工序：

式中： $ R $ 代表 ${\text{R}}{{\text{Z}}_z}$ 或者 ${\text{R}}{{\text{C}}_c}$ ；若装配设备 $u$ 上的 ${A_1}$ ( ${A_{zu}}$ 或者 ${A_{cu}}$ )先于 ${A_2}$ 加工， $ {Y_{uA}}_{_1{A_2}} = 1 $ ，否则 $ {Y_{uA}}_{_1{A_2}} = 0 $ ； ${{t}}_{{\text{A}}_1}$ 为工序 ${A_1}$ 的单件装配时间。

式(7)、(8) 、(9)为加工工序与装配工序的开始时间与结束时间的计算式。

2.   算法设计

遗传算法原理简单，通用性强，不受限制条件的约束，具有隐含并行性和全局解空间搜索能力^[18]，但其缺点是容易早熟收敛。本文选用改进过后的遗传算法解决上述NP-hard问题，辅以邻域搜索来增强局部搜索能力。针对本文问题特性设计出邻域结构N₁，给出一种混合型解码方式进行求解，并在机器故障时提出相应调度策略。

2.1   编码与初始化

染色体的编码是遗传算法的关键，良好的编码方式会提高执行效率。本文采用MSOS编码方式^[19]。染色体总长度为总工序数 $E$ ，如图1所示，由两部分组成，第一部分为基于工序的编码，用来确定各工件各批次各工序的加工顺序，从左往右第一个21表示工件2第1批次的第1道工序，以此类推；第二部分为基于加工机器的编码，用来确定加工各道工序的加工机器。由于装配阶段的独特性，编码中没有给出装配设备号。

图  1  编码

Fig.  1  Encoding

下载: 全尺寸图片

初始解的质量对算法的求解速度和质量极为重要，为提高初始解在机器选择部分中的质量和初始种群的多样性，使用GLR初始化方法^[20]。设置全局选择、局部选择和随机选择的比例分别为0.6、0.3和0.1。

2.2   遗传算子设计

2.2.1   选择

选择是为了使质量高的个体能以更高的几率生存，避免有效基因的损失，从而加快全局收敛性，提高计算效率。本文使用锦标赛选择并辅以精英保留策略，锦标赛选择的操作方法为每次从种群中选出3个个体进行适应度的比较，将适应度高的个体插入到交叉池，如此循环，直到填满交叉池为止。

2.2.2   交叉

交叉是主要的遗传操作，利用父代个体产生适应度更高的新个体，有效增加种群多样性以保证算法的全局搜索能力。交叉的方式有很多，为避免产生非法解，工序部分采用基于工件优先顺序的交叉算子^[21]，基于加工机器的编码则采用两点交叉^[22]。

2.2.3   变异

变异通过随机改变染色体的某些基因来生成新的个体，增加种群多样性，在一定程度上影响着遗传算法的局部搜索能力。本文采用两种变异算子，基于工序的编码采用交换变异算子，即从染色体中随机选择两个位置的基因，然后将它们进行位置交换；基于加工机器的编码则采用单点变异算子，随机选择一个基因位置，然后生成一个不大于该位置工序可选加工机器总数的随机整数，并将其填入所选的基因位置。

2.2.4   邻域搜索

遗传算法作为一种群优化算法，存在早熟和局部搜索能力差的问题。变邻域搜索算法通过不同邻域结构间的系统化切换，可以防止搜索陷入局部最优，增强局部搜索能力^[23]。在柔性加工与装配作业车间分批联合调度问题中，最大完工时间为最终成品的组装完成时间，而组件和成品的组装开始时刻又受到零件最后一道工序完工时间的影响。基于此特点，本文设计了一种针对该问题的工件末工序前移的邻域结构N₁和一种随机的邻域结构N₂。

N₁：在染色体中找到工件 $ i $ 的第 $ b $ 批次的最后一道工序 ${P_{ib{O_i}}}$ ，并将其向前移动到 ${P_{ib({O_i} - 1)}}$ 与 ${P_{ib{O_i}}}$ 之间随机一个位置。对所有工件的所有批次的最后一道工序都执行上述操作，便可提前进行装配操作从而缩减最大完工时间。例如图2中，假设染色体c为某完整染色体片段，工件1和工件3的工序数均为3，将工序11和23的最后一道工序向前移动至其可移动范围，则c'为移动后的一种情况。

N₂：随机选择某个零件i总数基因10%的基因，为这些基因重新分配加工机器。

2.3   基于装配设备负载均衡的混合贪婪解码

车间调度领域的解码方式可以分为三大类：半主动解码、主动解码和全主动解码^[24]，比如传统的贪婪解码属于主动解码。由于考虑到批量装配，而装配设备号未编入编码，所以单一的贪婪解码并不适用于此问题。考虑该问题的特性并希望快速和有效的完成解码，本文设计了一种基于装配设备负载均衡的混合贪婪解码，流程图如图3所示。

图  2  N₁邻域结构

Fig.  2  Neighborhood structure of N₁

下载: 全尺寸图片

图  3  基于装配设备负载均衡的混合贪婪解码

Fig.  3  Hybrid greed decoding based on load balancing of assembly equipment

下载: 全尺寸图片

在工件加工的部分采用贪婪解码，在装配部分提出一种基于装配设备负载均衡的装配设备选择策略，该策略步骤如下：

1) 得到当前需要进行组装的工序 ${A_{zu}}$ (或者 ${A_{cu}}$ )信息；

2) 列出此工序所有可用装配设备 $u$ ；

3) 选择可选设备中完成该装配工序时刻早的设备进行装配，即 $u$ 为使 ${t_{{\text{FA}}_{zu}}}$ (或者 ${t_{{\text{FA}}_{cu}} }$ )取得最小值的设备。

融合上述策略后，基于装配设备负载均衡的混合贪婪解码具体步骤为：

1) 初始化参数，令基因位置 $g = 1$ ；

2) 判断当前基因代表的工序是否为某一工件 $i$ 的最后一步工序 ${P_{ib{O_i}}}$ ，若是则更新工件 $i$ 的完工数，写入矩阵 ${{\boldsymbol{G}}_{jn}}(i,1)$ ， ${{\boldsymbol{G}}_{jn}}(i,1) $ 为 $n \times 1$ 矩阵，记录各个工件当前已完成加工而未参与组装的数目；更新记录完工时间，写入矩阵 ${{\boldsymbol{G}}_{jt}}(i,b)$ ， ${{\boldsymbol{G}}_{jt}}(i,b) $ 为 $n \times {p_i}$ 矩阵，记录各个工件各批次加工完成的时间；否则，令 $g = g + 1$ 并重复步骤2)；

3) 根据BOM结构图判断更新完成的工件数量是否能组装成组件 $z$ ，若能则为此道装配工序分配机器进行组装并更新已完成的组件数，写入矩阵 ${{\boldsymbol{Z}}_{jn}}\left( {z,1} \right)$ ， ${{\boldsymbol{Z}}_{jn}}\left( {z,1} \right) $ 为 $d \times 1$ 矩阵，记录现有各个组件的数目，同时更新 $ {{\boldsymbol{G}}_{jn}} $ ；否则直接转步骤4)。更新 ${{\boldsymbol{Z}}_{jn}}$ 和 ${{\boldsymbol{G}}_{jn}}$ 具体方法为：假设某BOM结构如图4，图中括号里的数字代表组成单件成品或组件需要的组件或者工件的数量，则式(10)、(11)为更新表达式，为方便描述，用M代表括号中的数字。

式中 ${\boldsymbol{R}}_Z$ 矩阵为对应的预装组件数矩阵，比如在BOM结构的前提下，式(10)中 ${\boldsymbol{R}}_Z$ 与 ${{\boldsymbol{G}}_{jn}}$ 相对应，为 ${\left[{{\boldsymbol{R}}_{\rm{Z}_1}}\;\;{{\boldsymbol{R}}_{\rm{Z}_1}}\;\;{{\boldsymbol{R}}_{{\rm{Z}}_2}}\;\;{{\boldsymbol{R}}_{{\rm{Z}}_2}}\;\;0\right]^{\rm{T}}}$ 。

图  4  BOM结构

Fig.  4  BOM structure

下载: 全尺寸图片

4) 根据BOM结构判断更新完成后的工件数量和组件数量是否能组装成为成品，若能则为此道工序分配设备进行组装并更新已完成成品数量，同时按照式(10)、(12)更新 ${{\boldsymbol{G}}_{jn}}$ 和 ${{\boldsymbol{Z}}_{jn}}$ ；否则令 $ g = g + 1 $ 转步骤2)。

式(10)、(11)、(12)中M表示一个可变参数，与参与计算的工件或者组件有关，比如 ${\boldsymbol G}_{jn}\left(1,1\right)= $ $ {\boldsymbol G}_{jn}\left(1,1\right)-{\boldsymbol{R}}_{Z_{1}}M$ 中M与工件 $ {i_1} $ 相关，则 ${M} = 2$ ，而 ${\boldsymbol Z}_{jn}\left(1,1\right)={\boldsymbol Z}_{jn}\left(1,1\right)+{{\boldsymbol{R}}_{\text{Z}_{1}}}M$ 中 $M$ 与组件 $ {z_1} $ 相关，则 $M = 1$ 。

2.4   机器故障发生后的调度策略

2.4.1   装配设备发生故障

与FJSP中的机器损坏不完全一样，在柔性加工与装配作业车间中除了工件加工机器可能会发生故障，用于装配的装配设备也存在着发生故障的可能性。由于本文引入了柔性装配，若装配设备发生故障，便不必停工等待设备修理，可以进行重调度，选择其他的装配设备进行装配作业，尽可能缩短最大完工时间。

2.4.2   加工机器发生故障

加工机器发生故障时会面临两种情况：

情况一：故障时此机器处于空闲状态；

情况二：故障时此机器正在加工某一批零件。

若为情况一，则根据静态调度的结果，记录当前还未完成加工的工序，在机器损坏时进行完全重调度。

若为情况二，机器损坏时正在被此机器加工的 $ {P_{ibj}} $ 将会被分成两个批次，一批为已经完成了此道工序加工的工件，另外一批为还未来得及完成此道加工工序的工件。此时，由于工件 $ i $ 的批次和批量都发生了改变，原来的染色体便不再合法，因此无法直接进行重调度。需要对染色体进行调整，加入新的基因，使重调度能够顺利进行，关于染色体的调整将结合算例1进行具体说明，算法总流程图如图5所示。

图  5  改进遗传算法总流程

Fig.  5  Improved general flow of genetic algorithm

下载: 全尺寸图片

综上，机器故障发生后的调度策略具体步骤为：

1) 判断在 $ {T_s} $ 时刻发生故障的机器类型，若是装配设备 $ u $ 故障则转至步骤2)；若是加工机器 $ k $ 则转至步骤3)；

2) 判断设备 $ u $ 在故障时刻是否正在组装工件，若是则记录此工序完成组装的组件或者成品个数，转至步骤5)；否则直接转至步骤5)；

3) 判断机器 $k$ 的当前情况，若是情况1则转至步骤5)；若是情况2，即工序 $ {P_{ibj}} $ 正在被此机器加工，则转至步骤4)；

4) 将 $ {B_{ib}} $ 个工件 $ i $ 划分成已经完成此道工序加工的 $ {B_{ib}}_1 $ 件和未完成加工的 $ {B_{ib}}_2 $ 件两个批次，将新的基因考虑到动态染色体中；

5) 记录现有的已完工工件数、组件数、成品数和所有机器的可开工时间；

6) 根据当前已完成加工的工序和最优静态甘特图得到还未加工的工序，将其考虑到动态染色体中；

7) 初始化动态染色体开始重调度，获得最优方案。

3.   算例分析

为了验证本文算法以及动态调度策略的有效性，以下设计了两个算例进行说明。在MATLAB 2016a上进行算例测试，运行环境为：Windows 10操作系统，3.00 GHz，8 GB RAM。设置算法相关参数：静态初始种群规模为400，动态初始种群规模为200，交叉率为0.8，变异率为0.2，迭代次数为120次。

3.1   算例1

算例1选用文献[25]中提出的问题并适当拓展修改。5种工件的批量分别为20、10、10、30、20，共有10台零件加工机器，3台装配设备。最后组装成一种成品，BOM结构如图4，装配工序信息如表1。

为与文献[25]进行对比，在不同的分批原则上利用本文算法求解该问题，以最小化最大完工时间为优化目标得到的结果如表2。

从表2可以看出，除了在等分2批的情况下本文的最优值与文献[25]相同，在等分3批和等分4批的情况下本文的最优值均优于文献[25]，验证了本文算法的整体有效性，等分4批时本文最优解甘特图如图6所示。

图  6  等分4批时本文最优解甘特图

Fig.  6  Optimal solution of Gantt chart with four equal batches

下载: 全尺寸图片

为了说明本文所提算法和解码在处理机器故障时的可行性，对该算例进行了适当拓展。不失一般性，在等分4批的情况下随机选择机器故障时间 $ {T_s} \in \left[ {55,75} \right] $ ，随机选择故障机器 $ k \in \left[ {1,10} \right] $ 。假设损坏情况为4号机器在 $ {T_s} = 68 $ min时发生故障，故障时长 $ {L_t} = 10 $ min，即4号机器在78 min时可以正常运转。利用本文算法求解得动态调度后的最优解，给出机器4在 $ {T_s} $ 时刻故障后的重调度甘特图(如图7)，可见其在 $ {T_s} $ 时刻之前(红色线条左边)的调度顺序与静态甘特图6一致。

图  7  加工机器4故障后的动态最优解(算例1)

Fig.  7  Dynamic optimal solution after machine four failure (example 1)

下载: 全尺寸图片

结合图例简单说明解码机器故障时染色体的更改原则：进行重调度之前首先判断在 ${T_s}$ 时刻机器 $ k $ 上工件的加工情况。例如：由图7可知，在68 min时机器4正在加工工件4的第4批次的第二道工序(图7中紫红色方块)，此道工序中有3件工件完成了加工，有6件未完成加工，因此工件4在后续加工中由4个批次（批量分别为7、7、7、9）变成5个批次（批量分别为7、7、7、3、6）。进而重调度时需要将基因45也考虑进入染色体编码当中，由于45并未完成第二道工序加工，因此45剩4道工序(绿色方块)在重调度后进行，44则剩3道工序(黄色方块)在重调度后进行。

3.2   算例2

在FAJSP的问题模型下引入批量和动态元素后的问题十分复杂而且本文提出了装配柔性，故而目前暂未寻得相关算例也没有基准测试算例集。在此生成一个参数随机的算例并完成静态与动态调度，用于说明本文所提算法和策略的有效性与可行性。算例2的BOM结构依旧采用图4，分批原则采用等分4批，其他模型参数设置如表3所示。加工工序信息和装配工序信息分别见表4和表5。

静态调度情况：为验证邻域结构N₁在柔性加工与装配作业车间分批联合调度问题中的有效性。分2种情况各独立运行程序20次得到的结果如表6。

可见同时采用N₁和N₂时的最优值和均值均比单独采用N₂时更好，验证了N₁邻域结构在考虑批量装配问题上的有效性，在一定程度上提高了算法的局部搜索能力和整体性能。利用本文算法多次运行后得到的最优解甘特图如图8所示。

图  8  静态调度最优解对应的甘特图

Fig.  8  Gantt chart corresponding to the optimal solution of static scheduling

下载: 全尺寸图片

动态调度情况：

1) 工件加工机器发生故障：随机选择机器故障时间 $ {T_s} \in \left[ {55,100} \right] $ ，随机选择故障机器 $ k \in \left[ {1,8} \right] $ ，设置故障时长 $ {L_t} = 10 $ min。随机抽取两种情况并利用本文算法解得对应静态调度最优解图8的动态调度甘特图如图9、图10所示。

图  9  加工机器4故障后的动态最优解(算例2)

Fig.  9  Dynamic optimal solution after machine four failure (example 2)

下载: 全尺寸图片

图  10  加工机器7故障后的动态最优解

Fig.  10  Dynamic optimal solution after machine seven failure

下载: 全尺寸图片

① 情况1： ${T_s} = 88,k = 4$ 。

② 情况2： $ {T_s} = 93,k = 7 $ 。

图9和图10中的绿色方块均为重调度后产生的工件的第5批次，红色方块为机器故障时刻正在被加工的工序。由于在机器损坏时，工件4的第3批次还未完成一道工序的加工，因此图9中T_s时刻重调度后将没有43工序块。

2) 装配设备发生故障：随机选择机器故障时间 $ {T_s} \in \left[ {110,160} \right] $ ，随机选择故障机器 $ u \in \left[ {1,4} \right] $ ，设置故障时长 $ {L_t} = 10 $ min。随机抽取两种情况并利用本文算法解得对应静态调度最优解图8的动态调度甘特图，如图11、图12所示：

① 情况1： $ {T_s} = 126,u = 1 $ 。

② 情况2： $ {T_s} = 135,u = 3 $ 。

图  11  装配设备1故障后的动态最优解

Fig.  11  Dynamic optimal solution after assembly device one failure

下载: 全尺寸图片

图  12  装配设备3故障后的动态最优解

Fig.  12  Dynamic optimal solution after assembly device three failure

下载: 全尺寸图片

4.   结束语

本文针对考虑机器故障的柔性加工与装配作业车间分批联合调度问题进行了研究，以成品的最终组装完成时间为优化目标，引入装配柔性，在遗传算法的基础上进行了改进后求解，并得出了以下结论：

1) 设计了一种针对该问题的工件末工序前移的邻域结构N₁，通过算例结果分析可知N₁邻域结构的采用使本文算法的局部搜索能力得到提高，求解质量得到改善。

2) 针对工件加工和组件装配两种不同类型的工序不能单一采用贪婪解码的问题，提出了一种基于装配设备负载均衡的混合贪婪解码，在装配解码部分融入一种基于装配设备负载均衡的装配设备选择策略，成功地解决了本文所研究的调度问题。

3) 针对工件加工机器和装配设备故障问题，提出了相应的调度策略和染色体更改规则用于处理机器故障动态事件。

4) 通过对已有算例和本文自编算例的测试，验证了本文所提算法在处理柔性加工与装配作业车间分批联合调度问题上的可行性和有效性。

针对柔性加工与装配作业车间分批联合调度问题，本文提出了相关解码和策略，但在分批原则上采用的是等量一致分批，动态事件只是考虑了一种。多样的分批原则和其他动态事件的考虑都是进一步研究的方向和要点。