在薄膜晶体管液晶显示器（thin-film transistor-liquid crystal display, TFT-LCD）的制造流程中，阵列工艺可以被构建为可重入混合流水车间批量流调度问题（re-entrant hybrid flowshop scheduling problem with lot streaming, RHFSP-LS）. 在此工艺中，玻璃基板须遵循既定流程，逐一完成所有子步骤的加工. 由于阵列工艺需要在玻璃基板上铭刻多层电路，玻璃基板须反复重入部分子步骤，致使整个问题呈现出可重入的特性. 目前，阵列车间的生产依赖手工排产，难以应对复杂多变的生产需求，因此亟需高效而精准的调度方法来完成排产工作.

RHFSP通常与特殊约束相结合进行研究. Chamnanlor等^[1]提出结合蚁群优化的自适应遗传算法，求解以最小化最大完工时间为目标的带时间窗约束的RHFSP. Tong等^[2]研究动态RHFSP，设计可变邻域搜索的多目标进化算法来求解问题，提出2种重调度策略来处理动态事件. Lei等^[3]提出精英教与学算法，以求解带瓶颈阶段的RHFSP. 耿凯峰等^[4]提出混合文化基因算法，用于求解考虑调整时间和运输时间的RHFSP，以最小化最大完工时间和总能耗. 将RHFSP与批量流（lot streaming, LS）此类特殊约束相结合进行研究的较少，仅秦红斌等^[5-6]将批处理机与RHFSP结合进行研究. 在TFT-LCD的实际生产过程中，由于玻璃基板扁平的结构特性，通常采用载具装载一定数量的玻璃基板成批次的运输和加工，表现出批量流的生产特性. 本文着眼于可重入混合流水车间批量流调度的问题.

研究的RHFSP-LS可以描述如下：$ N $种待加工产品各对应一个工艺批次，需要在$ M $个阶段上连续地进行加工，至少有一个阶段存在2台及以上的并行机，工艺批次依次经历$ M $个阶段的加工称为完成一个层次加工. 工艺批次在完成第$ 1 $个层次加工后，须重复进入系统完成$ \left(R-1\right) $个层次加工，工艺批次共完成$ R $个层次加工，因此工艺批次的加工具有重入特性. 此外，工艺批次$ j $可以分割成具有相同批量的$ {Q}_{j} $个加工子批，每个工艺批次的加工子批在某一阶段或某一层次完成加工后，可以立即运往下一阶段或下一层次进行加工. 工艺批次可以在不同的层次和阶段同时进行加工，减少机器的等待时间，提高生产效率. 如图1所示为RHFSP-LS的示意图. 调度的任务是合理安排所有工艺批次在各个层次和各个阶段的加工机器及加工顺序，优化目标为最大完工时间最小化和总拖期最小化.

除了流水车间的经典假设，研究的RHFSP-LS还包括如下假设.

1） 相同工艺批次的所有加工子批在某一阶段只能选择同一台机器连续加工，即不同的工艺批次不可混插.

2） 加工子批须经过全部阶段加工后才可重入第一阶段，开始下一层次的加工.

3） 加工子批在相邻两阶段的运输时间和准备时间已包含在加工时间内.

4） 相邻两阶段的缓冲区无限.

5） 不同工艺批次的加工工艺步骤环节一致，但加工的工时参数有差异.

1)目标函数：最小化最大完工时间$ {C}_{\mathrm{m}\mathrm{a}\mathrm{x}} $，即$ \mathrm{m}\mathrm{a}\mathrm{k}\mathrm{e}\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{n} $，如下所示：

(1)$ \min \;C_{\text{max}} = \max\,\, C_{M,j,R,Q_j}. $

式中：$ {C}_{M,j,R,{Q}_{j}} $为工艺批次$ j $的完工时间，$ M $为加工阶段总数，$ j $为加工批次的序号，$ R $为加工层次总数，$ {Q}_{j} $为工艺批次$ j $的加工子批总数.

最小化总拖期时间TFDT，如下所示：

(2)$ \min {\text{ TFDT}} = \sum\limits_{j = 1}^N {{\text{FDT}}_j} . $

工艺批次$ j $的拖期时间的计算公式如下：

(3)$ {\mathrm{FDT}}_j=\left\{\begin{array}{cc}C_{M,j,R,Q_j}-{\mathrm{DT}}_j \text{，}C_{M,j,R,Q_j} > {\mathrm{DT}}_j;\\ 0\text{，} 其他.\end{array} \right.$

式中：$ N $为工艺批次总数，$ {{\mathrm{FDT}}}_{j} $为工艺批次$ j $的拖期时间，$ {{\mathrm{DT}}}_{j} $为工艺批次$ j $的交货期限.

2)约束函数如下：

(4)$ S_{i,j,l,b} \geqslant 0;\;i \in I,j \in J,l \in L,b \in B_j. $

式中：$ i $为加工阶段的序号，$ l $为加工层次的序号，$ b $为加工子批的序号，$ I $为加工阶段集合，$ J $为工艺批次集合，$ L $为加工层次集合，$ {B}_{j} $为工艺批次$ j $的加工子批集合，$ {S}_{i,j,l,b} $为工艺批次$ j $的第$ b $个加工子批在第$ l $层的阶段$ i $上的开始加工时间. 式(4)确定了各批次的子批在任一层次的任一阶段的开始加工时间应为正值.

(5)$ C_{i,j,l,b} = S_{i,j,l,b}+P_{i,j,l}; \; i \in I,j \in J,l \in L,b \in B_j.$

式中：$ {C}_{i,j,l,b} $为工艺批次$ j $的第$ b $个加工子批在第$ l $层的阶段$ i $上的结束加工时间，$ {P}_{i,j,l} $为工艺批次$ j $的加工子批在第$ l $层的阶段$ i $上的加工时间. 式(5)定义了各批次的子批在任一层次的任一阶段的开始加工时间和结束加工时间的关系.

(6)$ \left. \begin{aligned} &S_{i+1,j,l,b }- C_{i,j,l,b} \geqslant 0; \\ & i \in \left\{ {1,2,\cdots ,M - 1} \right\},j \in J,l \in L,b \in B_j. \end{aligned}\right\}$

式(6)定义了各批次的子批在某一阶段加工完成后才能进行下一阶段的加工.

(7)$ S_{i,j,l,b+1} - C_{i,j,l,b} \geqslant 0; \; i \in I,j \in J,l \in L,b \in \{ 1,2,\cdots ,Q_j - 1\} . $

式(7)定义了各批次在某一阶段进行加工时，后一子批须等前一子批加工完成后才能进行加工.

(8)$ S_{1,j,l+1,b} - C_{M,j,l,b} \geqslant 0; \; j \in J,l \in \{ 1,2,\cdots ,R - 1\} ,b \in B_j. $

式(8)定义了各批次的子批在不同的层次进行加工时，只有在上一层次的最后一个阶段加工完成后才可以开始下一层次的首个阶段的加工.

(9)$ \sum\limits_{k = 1}^{O_i} {X_{i,j,k,l} = 1;\;i \in I,j \in J,k \in K_i,l \in L} . $

式中：$ {O}_{i} $为加工阶段$ i $的并行机总数；$ {K}_{i} $为加工阶段$ i $的并行机集合；$ {X}_{i,j,k,l} $为决策变量，当工艺批次$ j $在第$ l $层的阶段$ i $的并行机$ k $上加工时为$ 1 $，否则为$ 0 $. 式(9)保证了各批次的子批在任一层次的任一阶段只能由一台机器进行加工.

(10)$ Y_{i,j_1,j_2,l}+Y_{i,j_2,j_1,l} \leqslant 1; \; i \in I,j_1,j_2 \in J,j_1 \ne j_2,l \in L. $

(11)$ \left. \begin{aligned} & X_{i,j_1,k,l}+X_{i,j_2,k,l} - 1 \leqslant Y_{i,j_1,j_2,l}+Y_{i,j_2,j_1,l}; \\ & i \in I,j_1,j_2 \in J,j_1 \ne j_2,k \in K_i,l \in L. \end{aligned} \right\}$

(12)$\left.\begin{aligned} & S_{i,j_2,l,1} - C_{i,j_1,l,Q_{j_1}}+ \\ & {{W }}(3 - Y_{i,j_1,j_2,l} - X_{i,j_1,k,l} - X_{i,j_2,k,l}) \geqslant 0; \\ & i \in I,j_1,j_2 \in J,j_1 \ne j_2,k \in K_i,l \in L.\end{aligned}\right\}$

式中：$ {Y}_{i,{j}_{1},{j}_{2},l} $为决策变量，在第$ l $层的阶段$ i $上，若工艺批次$ {j}_{1} $早于工艺批次$ {j}_{2} $加工，且2个工艺批次在同一机器上加工时为$ 1 $，否则为$ 0 $；$ {j}_{1} $、$ {j}_{2} $为加工批次的序号；W为无穷大的正数. 式(10)~(12)共同定义了不同批次的子批不能混插，其中式(10)、(11)定义了两批次在同一阶段同一机器进行加工时的加工顺序. 式(10)保证了$ {Y}_{i,{j}_{1},{j}_{2},l} $ 和$ {Y}_{i,{j}_{2},{j}_{1},l} $不能同时为1. 式(11)避免了$ {Y}_{i,{j}_{1},{j}_{2},l} $ 和$ {Y}_{i,{j}_{2},{j}_{1},l} $ 全为0. 式(12)定义了两批次在同一阶段同一机器上进行加工时，后安排加工的批次的首个子批须等前一批次的最后一个子批加工完成后才可以开始加工.

(13)$ X_{i,j,k,l} \in \left\{ {0,1} \right\};\;i \in I,j \in J,k \in K_i,l \in L. $

(14)$ Y_{i,j_1,j_2,l} \in \{ 0,1\} ;\;i \in I,j_1,j_2 \in J,j_1 \ne j_2,l \in L. $

式(13)、(14)定义了决策变量的取值范围.

候鸟优化算法（migrating bird optimization, MBO）由于结构简单、局部搜索能力强和鲁棒性强等特点，被广泛应用于求解混合流水车间的批量流调度问题^[7-8].

与单目标优化不同，多目标优化通常不存在单一的最优解，因为多个目标之间可能存在权衡，即在一个目标上的改善可能导致另一个目标性能的下降. 候鸟优化算法通常用于求解单目标优化问题，个体通过与邻域解集相比较，选取较优解完成进化操作. 当处理多目标问题时，如何选取邻域解集中的较优解成为MBO多目标化时需要解决的问题. 采用非支配排序、加权总和与外部档案集等操作，将MBO多目标化. 如图2所示为MBO多目标化过程的示意图.

在MBO多目标化的过程中，非支配排序被用来对搜索到的邻域解集进行层次化排序，进而精确地识别出非支配解集. 当非支配解集包含多个解时，采用加权总和方法进一步筛选出最优解. 该方法通过为目标函数分配不同的权重，计算加权和，实现排序和优选. 在本文中2个目标同等重要，因此采用相等的权重系数.

此外，为了管理和利用邻域搜索过程中产生的非支配解，引入外部档案集机制. 在个体完成进化和分享操作后，若邻域解集中存在非支配解，则将非支配解添加到外部档案集中. 此操作不仅避免了优秀个体的流失，而且通过保持多样化的非支配解集合，增强了算法的搜索能力.

提出改进多目标候鸟优化算法（improved multi-objective migrating birds optimization, IMO-MBO），解决上述双目标可重入混合流水车间的批量流调度问题. IMO-MBO的流程如图3所示，改进之处主要包括解码机制、种群初始化、基于个体年龄的邻域搜索、逃逸机制等.

在可重入混合流水车间调度问题中，由于工艺批次多次重入生产系统进行加工，导致利用传统的编码方法难以准确地描述该问题的复杂性，采用基于机器分配的元胞矩阵的编码方式^[9]. 假设待求问题的工艺批次总数为$ N $，加工阶段总数为$ M $，加工层次总数为$ R $，则在该编码方式中，每个解由$ N $个二维矩阵{$ {\boldsymbol{A}}_{1},{\boldsymbol{A}}_{2},\cdots ,{\boldsymbol{A}}_{{N}} $}组成. 其中，矩阵$ {\boldsymbol{A}}_{j} $的维度为$ M\times R $，其元素$ {\boldsymbol{A}}_{j}(i,l) $表示工艺批次$ j $在第$ l $个加工层次、第$ i $个加工阶段上的并行机选择. $ N $个矩阵的排序表示各个工艺批次在首阶段的加工顺序.

在编码机制中，已经确定各工艺批次在整个加工过程中的机器分配方案和首阶段的加工顺序，但在后续阶段各机器上的加工顺序未确定，因此在解码时需要解决该问题. 考虑到不同工艺批次的加工子批不可混插的情形，在已有的研究中大多采用“子批优先”或“批次优先”的解码策略. "子批优先"是基于工艺批次在前一阶段首个加工子批的完工时间来确定其在后续阶段的加工先后顺序，即首个加工子批越早完成，其在下一阶段的优先级越高. 相对地，“批次优先”依赖于工艺批次中最后一个加工子批的完工时间，优先处理在前一阶段较早完工的工艺批次.

当采用“子批优先”的解码策略时，若在所有阶段都严格遵守此策略，则有可能错失较优解. 如图4所示，工艺批次1和3均被安排在阶段3的机器1上进行加工. 当在阶段3采用“子批优先”策略时，工艺批次1较早地完成了阶段2的加工，但由于工艺批次3的加工子批1在阶段2优先完工，工艺批次1须等待工艺批次3的所有子批全部完成加工后才能进行加工. 若在阶段3采用“批次优先”策略，则工艺批次1可以提前进行加工，不仅使总完工时间提前了1个单位，工艺批次1的完工时间也提前了5个单位，而代价仅仅是工艺批次3的完工时间延后了1个单位.

提出“子批优先”+“批次优先”的解码策略，在除最后一个加工层的末阶段的其余阶段采用“子批优先”策略，在最后一个加工层的末阶段分别采用“子批优先”和 “批次优先”策略进行求解，取适应度较好的方案作为最终的调度结果. 由于本文解决的是多目标优化问题，在全局各个阶段分别采用2种策略解码后，选择较优者进行下一阶段的解码，不仅缺乏比较的依据，而且得到的解可能并非最优解. 若针对各个阶段列举出所有情况再进行求解能得到最优解，但计算难度会大幅增加. 采用提出的组合策略，既不会影响整体的加工安排，也可以通过非支配排序或加权总和方法得到较优解.

MBO算法作为基于邻域搜索的群体智能算法，主要依靠种群中的个体在搜索空间中的移动和领导解与跟随解之间的信息交互来获取最优解. 分布均匀且分散的初始种群有助于算法在解空间中进行更广泛的搜索，降低算法早熟收敛到局部最优解的风险. Logistic混沌映射是典型的混沌映射系统，具有随机性和遍历性的特点. 采用Logistic混沌映射，使初始种群在解空间中分布均匀且分散. 具体的操作方法如下.

1）构建$ {P}_{\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}}-2 $个混沌序列结构体$ {{\boldsymbol{Z}}}_{s} $，结构体包括2个矩阵，分别是$ M $行$ N\times P $列的机器分配矩阵和1行$ N $列的工艺批次排序矩阵. Logistic混沌映射的函数表达式为

(15)$ {{\boldsymbol{Z}}_{s+1}} = \mu {{\boldsymbol{Z}}_s}\circ ({\boldsymbol{1}} - {{\boldsymbol{Z}}_s}). $

式中： $ {{\boldsymbol{Z}}}_{s}\text{中的元素均为} [0,\mathrm{ }1.0] $的混沌变量，其中s为混沌序列的编号，$ s=\mathrm{1,2},\cdots ,{P}_{\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}}-2 $，$ {P}_{\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}} $为初始种群的大小；$ \mu $为控制变量，$ \mu \in (0,\text{ }4.0] $.

2）通过Logistic混沌序列映射到解空间，生成初始种群$ {{\boldsymbol{X}}}_{s} $. $ {{\boldsymbol{X}}}_{s} $的机器分配矩阵通过如下映射函数映射至解空间：

(16)$ {{\boldsymbol{X}}_s} = \left\lceil {{{\boldsymbol{Z}}_s} \circ {\boldsymbol{O}}} \right\rceil . $

式中：$ {\boldsymbol{O}} $为各阶段并行机数量的矩阵，其维度与Z_s相同，每一行的元素为对应阶段的机器数量；$ \left\lceil {\,\,} \right\rceil $表示向上取整函数，工艺批次排序矩阵由混沌序列对应部分从小到大排序的序号生成.

为了避免生成质量较低的初始种群，降低算法的收敛速度，参考文献[10]，采取NEH算法生成初始种群的部分个体. 利用基础NEH算法，可以解决以最小化最大完工时间为优化目标的调度问题，由于本文为多目标优化问题，优化目标为最小化最大完工时间和最小化总拖期. 对NEH算法进行改进，以工件的交货期从小到大的顺序生成序列表，作为工艺批次排序的依据，将该算法记为NEHEDD（earliest due date）算法，将基础NEH算法记为NEHLPT（long processing tim）算法. 基于上述算法生成初始种群的2个个体并与基于Logistic混沌映射生成的初始种群进行融合，将适应度最高的个体置于领导解位置，其余个体随机排列在左右队列.

在种群巡飞的过程中，个体通过邻域搜索实现自我进化，设计合适的邻域结构，可以使种群朝着期望的方向进行搜索. 采用贪婪插入、贪婪交换、贪婪变异和最优变异4种邻域结构. 贪婪插入和贪婪交换是针对工艺批次排序进行邻域搜索，贪婪变异和最优变异是针对机器分配方案进行邻域搜索. 对于每种操作产生的邻域解集进行适应度计算，从中挑选出适应度最好的解作为该操作生成的最终邻域解.

贪婪插入. 随机选择工艺批次$ j $，将其从原始批次排序序列$ \varphi $中删除，得到$ {\varphi }{{{'}}} $；将工艺批次$ j $重新插入到$ {\varphi }{{{'}}} $的所有可能位置，调整机器分配矩阵，生成$ N-1 $个不同于原始解的邻域解.

贪婪交换. 随机选择工艺批次$ j $，分别将工艺批次$ j $与工艺批次排序序列的其他所有位置的工艺批次进行交换，调整机器分配矩阵，生成$ N-1 $个不同于原始解的邻域解.

贪婪（最优）变异. 随机从工艺批次中选择批次$ j $，改变其在某一阶段所有层次的机器安排，生成所有（$ N-1 $）个不同于原始解的邻域解.

考虑到本文编码方式的特殊性，对于解空间中的一个解，其机器分配方案可生成邻域解的数量远多于工艺批次排序可生成的邻域解的数量. 设计基于个体年龄的邻域搜索机制，公式如下所示：

(17)$ \theta = \left\{ {\begin{array}{*{20}{c}} {{P_{\text{f}}}}，&{1 \leqslant {\rm {Age }}\leqslant {A_{\min }}} ；\\ {{P_{\text{f}}}+\dfrac{{{P_{\text{u}}} - {P_{\text{f}}}}}{{{A_{\max }} - {A_{\min }}}}({\rm {Age }}- {A_{\min }})}， & {{A_{\min }} < {\rm {Age }}\leqslant {A_{\max }}}; \\ {{P_{\text{u}}}}，&{{A_{\max }} < {\mathrm{Age}}}. \end{array}} \right. $

式中：$ {\mathrm{Age}} $为个体的年龄，在种群初始化时，将个体的年龄设为1，若在后续的巡飞过程中，个体未能通过邻域搜索进化，则将个体的年龄加1，反之则将进化后的个体的年龄设为1；$ \theta $为进行邻域搜索时执行变异操作的概率，$ {P}_{\mathrm{f}} $为$ \theta $的下限，$ {P}_{\mathrm{u}} $为$ \theta $的上限，$ \left[{A}_{\mathrm{m}\mathrm{i}\mathrm{n}},{A}_{\mathrm{m}\mathrm{a}\mathrm{x}}\right] $为$ \theta $发生线性变化的年龄区间. 设$ r\text{为} [0,\mathrm{ }1.0] $的随机数，若$ r < \theta $，则执行变异操作，若贪婪变异产生的邻域解的数量大于$ N- $1，则执行最优变异，反之执行贪婪变异. 该策略能够避免因邻域搜索产生的邻域解的数量过多而导致搜索效率的下降；当不执行变异操作时，按照均等概率执行贪婪插入或贪婪交换.

个体可以通过动态调整邻域搜索策略，适应问题解空间的特性. 当个体年龄较小时，由于批次排序的邻域解较少，将搜索重点放在精细调节排序上，以快速找到质量较高的解. 随着个体年龄的增大，若排序优化未能显著改善结果，则算法逐渐转向机器分配方案的邻域搜索. 此处邻域解的多样性较高，能够在广阔的搜索空间中探索新的可能性.

基于探索机制^[11]的启发，提出结合外部档案集的逃逸机制. 由于在邻域搜索的过程中引入个体年龄的概念，设定个体年龄上限为$ {A}_{\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{t}} $. 当一个解在连续$ {A}_{\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{t}} $代内未发生进化时，则认定其达到局部最优，并因此触发逃逸机制. 当逃逸机制启动时，在外部档案集中随机选择一个个体（记为个体2），并将其与达到年龄上限的个体(记为个体1)进行交叉操作. 采用顺序交叉（order crossover, OX）策略，生成新的子代. 选取子代中的较优者，以替代原个体1. 为了避免优秀个体的流失，原个体1将被存入外部档案集中. 如图5所示为顺序交叉策略的一个示例.

该机制不仅在个体陷入局部最优时提供了有效的逃逸策略，而且通过外部档案集的利用，确保算法能够继承并发掘既有解中的优秀特性，保证了解的质量和多样性.

根据文献[12]中的算例生成机制生成本文所需的算例集，工艺批次数量、加工子批数量、重入层数、加工阶段数量、每个阶段并行机数量、加工时间及工艺批次交货期限由表1的数据离散均匀分布随机生成. 其中$ {\mathrm{ATPT}} $为所有工艺批次加工时间总和的均值，PT为各工艺批次加工时间总和的集合，$ {{\mathrm{P}}}{{\mathrm{T}}}=\{{{\mathrm{pt}}}_{1},{{\mathrm{pt}}}_{2}, \cdots, {{\mathrm{pt}}}_{N}\} $，计算公式如下.

(18)$ {\mathrm{p}}{{\mathrm{t}}_j} = \sum\limits_{l = 1}^R {\sum\limits_{i = 1}^M {({P_{i,j,l}} {Q_j}), j \in J} } . $

(19)$ {\mathrm{ATPT}} = N^{-1}{\sum\limits_{j = 1}^N {{\mathrm{p}}{{\mathrm{t}}_j}} }. $

根据表1中参数的取值范围，随机生成5个小规模算例和5个大规模算例进行实验.

选取多目标优化问题中常用的反转世代距离^[13]（inverted generational distance, IGD）作为评价指标. IGD是综合性指标，能够同时衡量解集的多样性与收敛性. IGD反映的是真实帕累托（Pareto）前沿上的点到非劣解集的平均距离，IGD越小表示解集越逼近或覆盖真实Pareto前沿. 在计算IGD指标时须使用真实Pareto前沿，在本文中真实Pareto前沿是未知的，因此使用的真实Pareto前沿是通过融合所有对比算法的Pareto前沿重新非支配排序得到的.

参数的设置在元启发式算法的各项特性中起到了重要作用. 为了得到IMO-MBO的最优参数，采用正交实验法，设置IMO-MBO的主要参数. IMO-MBO共有7个参数需要设置，分别是$ {P}_{\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}} $、$ G $、$ k $、$ t $、$ [{P}_{\mathrm{f}},{P}_{\mathrm{u}}] $、$ [{A}_{\mathrm{m}\mathrm{i}\mathrm{n}},{A}_{\mathrm{m}\mathrm{a}\mathrm{x}}] $、$ {A}_{\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{t}} $. 由于$ k $和$ t $须满足关系式$ k\geqslant 2t+1 $，参数$ k $和$ t $不满足实验设计的要求，参考文献[7]将$ k $设为3，$ t $设为1. 其他参数设置4个水平，具体如表2所示.

根据$ {L}_{16}\left({4}^{5}\right) $正交表，以大规模算例N17M8R3（数字为对应的取值，如17表示工艺批次总数N的取值） 为对象设置16组实验. 在MBO中，种群大小和一次巡飞过程种群的迭代次数会影响邻域搜索的次数，因此本节的16组实验均运行300 s后停止，每组实验运行20次计算IGD的平均值，具体结果如表3所示. 参数水平的IGD平均值排序如表4所示.

从表4可见，$ {P}_{\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}} $对算法的影响较大，较大的种群规模可能降低个体的邻域搜索频率，从而减小算法的搜索深度并有可能忽略部分优质解. 由于分享机制的存在，种群规模较小可能会导致算法早熟并陷入局部最优，选择中等种群规模，以平衡搜索深度与搜索广度. 一次巡飞过程中种群的迭代次数$ G $的取值具有相同的原理，迭代次数的增加能够增大领导解向跟随解分享优质邻域解的机会，加速算法的收敛速度，但过大的迭代次数又会使得种群的多样性下降. 其他因子的IGD平均值越小，表示算法性能越好，因此IMO-MBO的参数组合为：$ {P}_{\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}}=51, $$ G=10 ,$$ \left[{P}_{\mathrm{f}},{P}_{\mathrm{u}}\right]=\left[\mathrm{0.3,0.7}\right] ,$$ \left[{A}_{\mathrm{m}\mathrm{i}\mathrm{n}},{A}_{\mathrm{m}\mathrm{a}\mathrm{x}}\right]= \left[\mathrm{4,6}\right] ,$ $ {A}_{\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{t}}=8 $.

为了验证所提改进策略的有效性，通过消融实验设计8种变体算法，与原算法进行对比. 各算法所采用的策略如表5所示. 表中，数字1、2和3分别表示解码策略采用“子批优先”+“批次优先”、“子批优先”和“批次优先”，字母$ a $、$ b $、$ c $和$ d $分别表示种群初始化策略采用Logistic混沌映射+NEH算法、Logistic混沌映射、随机+NEH算法和完全随机. 当不采用基于个体年龄的邻域搜索策略时，个体在进行邻域搜索时，采用等同概率使用插入或变异策略.

针对生成的10个算例，每种算法独立运行20次，算法的终止条件为种群巡飞10次. 每运行一次得到一组IGD，对于每个算例所获得的20组指标取均值，结果如表6所示. 表中，数字右侧的“+”、“*”分别为IMO-MBO与MBO4、MBO3与MBO5的指标较优者的标识；对IGD所得的数据采取置信水平为95%的Wilcoxon符号秩检验，所得的p如表7所示，p≤0.05表示参与对比的2种算法间存在显著差异. 针对IGD指标而言，IMO-MBO显著优于MBO6、MBO7和MBO8，说明基于个体年龄的邻域搜索和逃逸机制有助于增强算法的鲁棒性和收敛性，将所提的各项策略组合后对于算法的性能有较大的提升. 针对解码策略，IMO-MBO、MBO1与MBO2无显著差异，但IMO-MBO在部分算例上远优于MBO1，如N7M4R1和N17M8R3，说明与“子批优先”策略相比，针对特殊问题在末阶段采取“子批优先”+“批次优先”的组合策略，有助于获得更好的最终解. 针对种群初始化策略，IMO-MBO显著优于MBO3，说明NEH算法能够为种群提供部分的优质初始解，有助于加速种群的收敛过程. IMO-MBO与MBO4、MBO3与MBO5无显著差异，但针对大部分算例的IGD指标而言，IMO-MBO略优于MBO4，MBO3略优于MBO5，说明Logistic混沌映射有助于增强算法的鲁棒性. IMO-MBO显著优于MBO5，说明种群初始化策略能够为算法的后续搜索提供优质的初始解集，有助于提高最终解的质量.

为了验证数学模型的有效性，采用$ \varepsilon $-约束法将多目标优化问题转化为2个单目标优化问题，分别以多目标问题的一个目标作为优化目标，另一个目标作为约束，2个问题的数学模型如下.

问题1：

(20)$\left. \begin{split} &\min \,\,C_{\text{max}} = \max\,\,C_{M,j,R,Q_j}. \\ &{\mathrm{s.t.}} \quad 式(3)\sim (14)；\\&\qquad \sum\limits_{j = 1}^N {{\mathrm{FDT}}_j} \leqslant \varepsilon_ 1.\end{split} \right\}$

式中：${\varepsilon }_{1}\in [0,+\infty ] $，0表示无拖期时间，无穷大表示不考虑拖期时间. 在实际求解过程中，当$ {\varepsilon }_{1}=0 $时问题1可能无法进行求解，应根据问题的实际情况调整$ {\varepsilon }_{1} $的最小值.

问题2：

(21)$\left.\begin{split} & \min\; {\mathrm{TFDT}} = \sum\limits_{j = 1}^N {{\mathrm{FDT}}_j} .\\& {\mathrm{s.t.}} \quad 式(3)\sim (14)；\\&\qquad C_{M,j,R,Q_j} \leqslant \varepsilon_ 2,j \in J. \end{split}\right\}$

$ {\varepsilon }_{2} $的最小值为问题1在不考虑拖期时间时所求得的$ {C}_{\mathrm{m}\mathrm{a}\mathrm{x}} $，$ {\varepsilon }_{2} $的最大值为问题1在$ {\varepsilon }_{1} $取最小值时所求得的$ {C}_{\mathrm{m}\mathrm{a}\mathrm{x}} $.

利用Gurobi对上述2个单目标问题进行求解，根据$ \varepsilon $的取值范围对$ \varepsilon $进行调节. 每调节一次，可以获得一组对应解$ [{C}_{\mathrm{m}\mathrm{a}\mathrm{x}},{\varepsilon }_{1}] $或$ [{\varepsilon }_{2},\mathrm{T}\mathrm{F}\mathrm{D}\mathrm{T}] $. 通过多次调节$ {\varepsilon }_{1} $与$ {\varepsilon }_{2} $的值，可以获得多目标问题的一组非支配解. 将IMO-MBO、MBO1、MBO2分别运行10次，取最好的结果为对应解码方法下的Pareto前沿. 由于本文的研究问题为NP-hard问题，选择小规模算例N7M4R1，以保证Gurobi的求解效率. 作出不同算法对N7M4R1所求的Pareto前沿，结果如图6所示. 采用$ \varepsilon $-约束法获得的Pareto前沿对采用“子批优先”或“批次优先”的解码策略获得的Pareto前沿具有支配关系，利用2种不同的解码策略获得的Pareto前沿映射着真实Pareto前沿的不同区域，因此可以验证数学模型的有效性. 当完工时间为178时，相较于单独使用“子批优先”策略，采用“子批优先”+“批次优先”的混合策略，使得总拖期减少了8个时间单位，说明组合解码策略对于特殊问题具有较好的求解能力，改进解码策略有助于引导算法所求结果向问题的真实Pareto前沿逼近.

为了验证IMO-MBO的有效性，将其与非支配排序遗传算法（non-dominated sorting genetic algorithm II, NSGA-II）、多目标粒子群算法（multi-objective particle swarm algorithm, MOPSO）^[14]、多目标混合遗传算法（multiple-objective hybrid genetic algorithm, MOHGA）^[15]和混合多目标人工蜂群算法（hybrid multi-objective discrete artificial bee colony, HDABC）^[16]等算法进行对比. 5种算法的编码、解码和种群初始化策略均相同. NSGA-II采用二元锦标赛选择算子、顺序交叉算子、贪婪变异和最优变异算子. MOPSO的邻域搜索算子采用本文的贪婪变异和最优变异算子，交叉算子采用顺序交叉算子. NSGA-II和MOPSO的其余参数如表8所示. MOHGA和HDABC采取与参考文献相同的参数和策略. 算法的终止条件为运行时间达到$ 3 M N R $. 针对每个算例，独立进行20次实验，对所得的IGD指标取均值.

从表9可以看出，针对IGD指标，IMO-MBO在绝大部分算例上都优于其他4种算法. 如表10所示为对各项指标所得数据采取置信水平为95%的Wilcoxon符号秩检验的结果，说明IMO-MBO显著优于对比算法. 上述结果表明，与其他算法相比，IMO-MBO具有较好的收敛性和多样性.

针对每个算例基于5种算法所得的IGD指标，采用最小-最大归一化方法对其进行归一化：

(22)$ X_{\text{norm}}(u) = \frac{{X(u) - \min \;(X)}}{{\max\; (X) - \min\; (X)}}. $

式中：$ u\in \left[\mathrm{1,5}\right] $，$ X $为利用5种算法所得指标的集合，$ X\left(u\right) $和$ {X}_{\mathrm{n}\mathrm{o}\mathrm{r}\mathrm{m}}\left(u\right) $为利用第$ u $种算法所得的指标和归一化后的指标.

将IGD指标归一化后所得的结果如图7所示. 可以看出，针对IGD指标，IMO-MBO算法在大、小规模算例上都显著优于NSGA-II和MOPSO算法. HDABC算法在小规模问题上的表现与IMO-MBO相当，但随着规模的扩大，IMO-MBO的优势更明显. MOHGA算法在大、小规模问题上都能与IMO-MBO保持较小的差距. 如图8所示为小规模算例N6M6R2和大规模算例N17M8R3由5种算法所求Pareto前沿绘制而成的对比图，可见各算法在求解不同规模问题时的差异性.

结合TFT-LCD阵列车间的生产特性，本文构建可重入混合流水车间批量流调度问题模型，设计改进多目标候鸟优化算法进行求解. 考虑到调度问题的独特性，提出“子批优先”+“批次优先”的解码策略，以增强算法在处理特殊问题时的能力. 此外，针对算法的本身特点进行改进，主要包括提升初始种群质量、优化局部搜索方向及增强全局搜索能力. 通过实验验证了改进策略的有效性和算法的优越性. 进一步的研究方向是在模型中纳入动态事件的影响，因为在实际生产中可能会遭遇机器故障或工件抽检不合格的情况. 此时通常需要将正在加工的子批进行拆分，区别不同加工状态的工件. 引入这些动态事件，将使模型更贴近生产实际.