随着市场需求的变化与竞争的日趋激烈，对产品交期的要求越来越短，个性化需求越来越高，制造业越来越体现出多品种小批量的生产特征，特别对加工以及装配型生产企业更为明显. 批量流技术广泛应用于多品种小批量的这一分批生产模式中^[1]. 随着产品种类的增多与产品复杂度的上升，零件、部件和产品的协同生产要求更高，问题更加复杂，实际生产表现就是整个车间的缓冲区（用于零部件周转存放）面积过大，整个产品生产周期中的等待时间占比大，这对当前制造业急需提升亩均产值、解决用地紧张问题特别重要. 对于吸尘器、空调和冰箱等家电产品，产品种类多样往往通过3阶段加工装配，先加工注塑件，再装配部件，零部件成套后才总装产品. 产品存在装配关联约束^[2]，容易导致前后阶段进度不匹配，造成缓冲区堆积在制品，拉长产品生产周期，因此有必要用最佳的调度方法安排零部件和产品的生产. 装配关联约束与不同工序的加工时间差异较大，且工序的设备数通常是多台，这就要对工件生产进行批量划分，确定各子批的加工设备^[3].

研究问题源于吸尘器等家电类多品种小批量产品的生产过程，拟研究考虑序列不相关准备时间与多模具约束下，以最小化的最大完工时间为目标的3阶段批量流混合装配流水车间调度问题. 注塑模具与总装工装夹具的切换准备时间主要集中在调试时间，与生产序列无关，忽略序列对准备时间的影响. 批量流调度^[4]可以减少等待时间，减少缓冲区面积、提高生产效率、缩短交货期和提升亩均产值，具有广泛的应用背景和实际意义. 国内外学者关于批量流调度问题往往没有考虑除设备资源外的生产资源，比如原材料、人力资源和模具等^[5]，但不同的零件往往要采用不同的模具，不同的产品要不同的工装夹具辅助装配. 对于多品种小批量的生产模式与模具广泛应用机械和电子等众多行业的情况，考虑多模具约束的混流分批调度具有高度现实意义. 针对车间调度问题，最大完工时间指标可有效表达其他常规调度指标的函数^[6]，如产品的零部件等待加工时间，所以优化目标选取最小化最大产品完工时间.

已有学者研究批量流混合流水车间调度问题，Zhang等^[7]研究不可混插子批的2阶段混合流水车间分批调度，提出2种启发式算法依次解决调度顺序以及批次分割2个子问题，并且第2阶段只有1台设备. Defersha等^[8]提出并行遗传算法求解可混插子批的多阶段混合流水车间分批调度，但所有加工批次的子批数是一样的. Zhang等^[9]提出改进候鸟优化算法求解等量分批的批量流混合流水车间调度问题. Qin等^[10]提出2阶段蚁群算法解决考虑多约束的等量分批的批量流混合流水车间调度问题. 张彪^[11]针对带批处理的多品种小批量生产模式，在静态、动态2种环境里建立多目标优化模型. 王文艳等^[12]提出离散水波优化算法，研究不可混插子批的带批处理的批量流混合流水车间调度. 上述研究文献大多基于不可混插子批、等量分批和一致分批的假定，在实际生产中，多台设备加工一种工件、子批批量不同、不同阶段批量划分方案不同的情况屡见不鲜，而这些因素都会影响批量划分. 但这些状况对调度方案有更高的要求，工件批次不确定性更高，使得本研究的问题具有更高复杂度. 求解调度问题的常用方法为智能优化算法，关于精确算法，在理论上可求得最优解，但随着问题规模的增大，求解时间会呈指数倍增长，无法满足实际应用. 鉴于以上情况，在考虑序列不相关准备时间与多模具约束的情况下，对3阶段批量流混合装配流水车间调度问题展开研究，以最小化最大完工时间为目标进行问题建模，再结合问题特征提出一种有效候鸟优化算法（effective migrating birds optimization, EMBO）进行求解.

针对家电类产品中多品种小批量的生产特征，根据产品模块化的理念，对工件的多道加工工序的设备可组成自动流水线加工，将一个复杂的产品装配分为不同的阶段. 将复杂产品在任一阶段的多道工序模块化，视为一道工序，得到家电类产品简化工序图，如图1所示.

研究对象为3阶段混合装配流水车间，如图2所示，由4个部分组成：第1部分为零件加工，多种零件在此以批为单位加工，零件的不同子批可在多台无关并行机（零件加工时间与选取设备有关）上加工，受准备时间和模具数量约束的影响；第2部分为部件加工，部件的关联零件齐套后在此以批为单位加工，不受准备时间和模具数量约束的影响；第3部分是产品总装，产品的所有零部件齐套后在此以批为单位装配，不同产品的子批可在多台无关并行机上加工，受准备时间和模具数量约束的影响；第4部分是缓冲区，存放未齐套的零部件，部件与产品齐套后才能加工装配，即缓冲区中存在大于等于部件或产品所有关联零部件的子批数量. 3阶段批量流混合装配流水车间问题可以描述为：该车间一共有P种产品，各个产品的需求数量为Q_c，产品各工序对应的模具数量为O_i，在3阶段共M台设备上进行加工，优化问题是在满足模具数量约束的情况下对所有产品3阶段中的各工序分批，确定各工序子批的加工设备与加工顺序，使得生产最大完工时间最小.

为了便于研究问题，给出以下假定：

1）不同工序加工存在序列不相关准备时间；

2）缓冲区无容量限制；

3）生产环境稳定，不考虑设备故障、生产不合格等；

4）所有子批在任一设备上只能连续地加工.

为了便于描述问题，定义如下符号：

索引和输入数据：

P：产品种类总数，序号c，d；

Q_c：一定时间内的产品c的需求数量；

G：生产阶段总数，G=3，序号g，h；

S_g：工序总数，序号i，j；

d_c,i：产品c阶段g工序i上的工件数；

Pa_i：阶段g工序i的生产最小批量；

M：设备总数，序号m，n；

M_i：阶段g工序i的可用设备总数，序号m，n；

T_m,i：阶段g工序i在设备m上的加工时间；

DT_m,i：设备m上加工对象换成阶段g工序i的准备时间；

R：一个非常大的正数；

O_i：阶段g工序i的模具总数，序号p，q，当工序不用模具时，O_i= R.

变量：

K_i：阶段g工序i的最大批次总数，序号k，l；

sq_g：阶段g各工序子批按一定加工次序形成的序列，序号u，v ，即u对应k，v对应l；

N_i,u,v：经过阶段g中u个序列与阶段h中v个序列加工后阶段g工序i的可用零部件总数；

λ_k：阶段g工序i的第k个子批的大小；

m_k：阶段g工序i的第k个子批的设备号；

st_m,k：设备m上阶段g工序i的第k个子批的开始加工时间；

ct_m,k：设备m上阶段g工序i的第k个子批的完成加工时间.

二进制变量：

α_k,u：若阶段g工序i的第k个子批是阶段g第u个加工序列为1，否则为0；

β_i,u,v：若阶段g中u个序列与阶段h中v个序列加工后阶段g工序i的可用零部件总数小于0为1，否则为0；

γ_m,k：若阶段g工序i的第k个子批分配到设备m_k上加工为1，否则为0；

e_i,j：阶段g工序i要在阶段h工序j前加工装配为1，否则为0.

f_m,k,l：若设备m上阶段g工序i的第k个子批在阶段h工序j的第l个子批前加工为1，否则为0.

根据最小化最大产品完工时间，建立目标函数为

(1) $ F = \min\; (\mathop {\max }\limits_{g = 3} {\rm{c}}{{\rm{t}}_{m,k}}). $

当任一工序的子批小于等于对应模具总数与设备数时，表达式为

(2) $ {K_i} = \min\; ({O_i},{M_i}). $

任一工序的可用零部件总数等于经过存在装配约束的2个阶段序列生产加工与使用装配后的剩余零部件总数：

(3) $ {{N} _{i,u,v}} = \sum\limits_{u = 1}^u {\sum\limits_{k = 1}^{{K_i}} {{\lambda _k} \times {\alpha _{k,u}}} } - \sum\limits_{v = 1}^v {\sum\limits_{l = 1}^{{K_j}} {{\lambda _{j,l}} \times {\alpha _{j,v}}} } \times {e_{i,j}},g < h. $

任一工序的子批之和等于该工序对应各产品的需求数总和：

(4) $ \sum\limits_{k = 1}^{{K_i}} {{\lambda _k}} = \sum\limits_{c = 1}^P {{Q_c} \times {d_{c,i}}} . $

任一工序任一子批只能在一台设备上加工：

(5) $ \sum\limits_{m = 1}^M {{\gamma _{m,k}}} = {\text{1}}{\text{.}} $

任一工序任一子批的加工设备属于对应工序的可用设备集：

(6) $ {m_k} \in {M_i}. $

任一工序任一子批的与完成加工时间的关系：

(7) $ {\rm{c}}{{\rm{t}}_{m,k}} = {\rm{s}}{{\rm{t}}_{m,k}}+\sum\limits_{m = 1}^{{M}} {{\gamma _{m,k}}} \times {\lambda _k} \times {T_{m,i}}. $

同一设备上先后进行加工的2个子批间的等待时间约束：

(8) $ {\rm{s}}{{\rm{t}}_{m,l}} \geqslant {\rm{c}}{{\rm{t}}_{m,k}}+{\text{D}}{{\text{T}}_{m,j}} - (1 - {f_{m,k,l}}){{R}}{\text{.}} $

产品与部件的任一序列子批必须在下属任一阶段工序按序列生产的可用零部件数大于等于0后才能开始加工. 该模型已通过CPLEX验证有效性和正确性：

(9) $ \begin{gathered} {\rm{s}}{{\rm{t}}_{n,l}}+(2 - {\beta _{i,u,v}} - {e_{i,j}}){{R}} \geqslant \\ \mathop {\max }\limits_{u' \in [1,u+1]} {\rm{c}}{{\rm{t}}_{m,k}} \times {\alpha _{k,u'}},g < h. \\ \end{gathered} $

由于批量流混合流水车间调度问题的强NP难特性，精准算法难以在有效时间内求解，而结合问题特征的智能优化算法为快速求解提供一种有效方法. 候鸟优化算法（migrating birds optimization, MBO）是一种新型元启发式算法，有独特的分享和受益机制^[13]，可以更细致搜索优良解的邻域，促使算法更快向优良解进化，具有高效的局部搜索效率及突出的收敛性能的优点. 目前，MBO算法在求解上二次分配问题上解的质量更优^[14]，并且在求解调度类优化问题已有较好效果^[15-17]. 批量流调度问题中考虑批量划分与子批排列顺序调度，对批量的搜索依靠基于变异的邻域搜索^[18]，而MBO算法的邻域搜索能力为分批向量的寻优提供强力支持，可在不破坏约束的前提下进行有效搜索，因此采用MBO算法进行求解. 据此，提出一种EMBO算法来求解3阶段批量流混合装配流水车间调度问题. 首先，根据模具数量和3阶段协同生产等问题特征确定批量划分策略；其次，基于问题特征和批量划分策略，设计编码与解码机制；接着，根据问题特征设计针对批量划分与子批排列2个子问题的邻域结构；然后，为了改进算法性能，提出领域结构自适应调节与竞争机制改进策略；最后，给出 EMBO 算法的详细流程.

常见的不同批量划分策略^[19]主要有等量分批（工件任务分成均等的生产子批）和不等量分批（工件任务的各子批批量可不同），还可以进一步分为一致子批（工件任务所有工序的批量划分方案相同）和可变子批（工件任务各道工序的划分方案不必相同）. 针对3阶段协同生产特征，不同阶段加工能力不同，考虑不同阶段不同批次划分方案，有助于减少最大完工时间. 因此采用不等量可变策略划分：各阶段工序的最大批次数为min (K_i，M_i) .

一个完整的批量流方案包括子批的批次数、每个子批的数量、子批的加工顺序和子批的加工设备. 考虑批量划分与子批调度2个子问题，设计一种2段编码机制：批量划分编码与排列编码^[20]. 为了便于说明编码机制，以简单产品1与2为例进行说明，同一阶段不同工序用数字表示，具体工序如图3所示，各阶段工序最大批次数都设为2.

批量划分编码解决子批的批次数与每个子批的数量问题. 采用不等量可变策略划分批量，需要确定所有产品的各阶段各工序的工件划分方案，且工件子批不等量，极大增加问题的复杂度. 对此，对不同产品的相同加工工序进行工件分批，便于进行批量划分，减少计算量. 对此，用K_i个精度为0.1的[0, 1.0]间随机数X_{i, k}，来确定3阶段各工序中工件子批的批次数与每个子批的数量，如图4所示.排列编码解决子批的加工顺序问题. 对图4批量划分编码中不同阶段的子批序列随机排列，生成排列编码来解决子批调度子问题，如图5所示.

子批存在下限约束的要求，对此子批数量要么大于对应工序的生产最小批量，要么为0. 通过式（10）和（11）可得到每个子批的数量，并满足上述要求.

(10) $ {\lambda _k} = \left[\frac{{{{{X}}_{i,k}} \times \displaystyle \sum\limits_{c = 1}^P {{Q_c} \times {d_{c,i}}} }}{{{\text{P}}{{\text{a}}_i}}}\right]\times {\text{P}}{{\text{a}}_i};\;k < K'. $

式中：K' 为阶段g工序i的实际批次总数，即阶段g工序i中非0随机数X_{i, k}的个数；X_{i, k}为阶段g工序i的第k个子批的[0, 1.0]随机数大小.

(11) $ {\lambda _{{{K'}}}} = \sum\limits_{c = 1}^P {{Q_c} \times {d_{c,i}}} - \sum\limits_{k' = 1}^{{{K'}} - 1} {{\lambda _{k'}}} . $

式中：λ_K′为阶段g工序i的第K′个子批的数量.

解码机制解决子批的加工设备问题. 考虑各设备的不同加工能力，根据“先到先加工”规则确定子批加工顺序；先根据“最先空闲”规则，再根据“能力优先”（加工时间小）规则，在可用设备集中选取加工设备. 按上述规则与装配齐套约束来确定各阶段子批的开始与结束加工时间，最后得出最小最大完工时间.

MBO算法通过搜索邻域解集迭代进化，邻域结构直接影响算法的求解质量和收敛速度，因此需要设计高效的邻域结构. 2段编码为不同的子问题，针对不同子问题编码设计不同领域结构，并且提出一种领域结构同时解决2个子问题.

1） 批量划分编码的邻域结构 工序批量块变异为随机选择任一阶段一种工序的一个子批，在约束范围内使其随机变化，其它子批随之变化. 子批随机数可突变为0，批次数量减少；工序批量块交换为随机选择2种最大批次数的工序随机数进行交换. 2）排列编码的邻域结构 调度算法中对加工排列顺序，常用随机交换、前插、后插、序对交换、最优插入和最优交换6种操作构造领域结构^[21]. 3）2段编码的邻域结构 在MBO算法中，早期跟飞鸟进化时容易被共享领域解替代，使得跟飞鸟中较优编码片段被丢弃^[22]. 因此提出当前跟飞鸟与领域解交叉产生新邻域解. 考虑装配约束，提出一种基于节点工序的下属工序统一交叉的邻域结构. 设计如下：随机选取一个节点工序，与其下属工序构成集合，将该集合中所有工序子批的随机数交换，再将该集合中不同阶段中所有工序子批的排列编码按排列顺序交换. 以阶段2工序1为例，由f1与f2编码生成z1与z2新编码，具体过程如图6所示.

算法共采用9种邻域结构，不同结构在算法不同阶段对解的搜索效果不同，如在算法后期阶段，排列编码中最优插入、最优交换结构优于其他4种结构，应提高这2种结构的应用频率. 因此引入自适应调节策略^[23]，可以在算法每次迭代时根据领域结构在之前迭代中的表现更新对应权重，然后通过轮盘赌方法得到结构的使用概率，从而控制算法不同迭代时每种结构的使用频率，优化算法效率.

考虑2段编码对应邻域结构数量不同，给排列编码每种结构赋值权重1，其它结构赋值权重2. 用轮盘赌方法根据权重w_i随机选择邻域结构产生邻域解，每次迭代后更新权重. 通过下式调节邻域结构权重为

(12) ${w_{i,{\rm{seg}} + 1}} = \left( {1 - {\eta _i}} \right){w_{i,{\rm{seg}}}} + {\eta _i}{{\cal X}_{i,{\rm{seg}}}}/{\delta _{i,{\rm{seg}}}}.$

式中：seg为算法迭代次数；δ_i为结构i使用次数； χ_i为结构i累计得分，若结构i产生解优于原解，则χ_i得分加1；η_i∈[0, 1.0]为权重w_i对结构i效果反应的快慢.

在MBO算法中，跟飞鸟经过一定次数巡回后会代替领飞鸟，若优良解在队列比较后面，经过多轮巡回后才能起主导作用，迟滞优化效率. 左右2个队列间没有交互，会降低种群多样性. 针对上述问题，在鸟群巡回结束后，引入种群内竞争^[22]，可保持种群多样性，提升算法优化效率，具体操作步骤如下：1）跟飞鸟中随机选择一对个体，比较其适应度；2）若排列在前跟飞鸟的适应度较小，则交换两者位置，否则不变.

便于描述EMBO算法，定义以下参数：Nf为鸟群个体数量，a为每个个体产生的邻域解数，b为每个个体传给下一个体的邻域解数，ng为巡回次数，Temp为哪边队列的首位跟飞鸟替换领飞鸟，C₀为竞争次数. EMBO详细算法流程如图7所示.

测试环境为WIN10系统，CPU为i7-7700k、内存为16GB，采用MATLAB2016a编程. 文献[9]表明目前批量流车间调度没有基准算例，以某装配企业吸尘器生产过程与Shao等^[24]的实验数据为参考. 确定以下实验数据：产品种类P∈{3，5，7，9}，产品数量Q∈U[100，400]，其中，U为离散分布. 阶段2部件工序4种，阶段3直属零件工序4种，按每种产品阶段2工序数S∈{1，2}，阶段3直属工序数S∈{1，2，3}组成多种产品，生产各工序与产品示例如图8所示. 产品总装部分设备相同，设备数M₁∈U[3，7]，加工时间T₁∈U[10，20]；部件加工部分设备相同，设备数M₂∈U[1，5]，加工时间T₂∈U[3，6]；零件加工部分有3种设备，每种设备数M₃∈U[1，3]，工序加工时间与设备种类有关，一些设备无法加工部分零件，加工时间T₃∈U[3，8]. 存在模具数量约束的生产准备时间为DT∈U[200，600]，对应模具数量O∈U[2，6]. 各工序最小生产批量Pa∈U[20，60]. 数据格式U[x，y]为x和y的离散均匀分布.

EMBO算法相关参数有Nf，a，b，ng，C₀. 其中a，b相互约束，不适用正交，且已有文献多如此设置：a=3，b=1，通过试实验发现这种参数设置适用且有较好效果，因此a和b采取这种设置. Nf，ng，C₀与问题规模有关，使用田口实验设计方法研究^[25]，参考已有文献的因子水平并结合大量测试确定参数水平，如表1所示. 算法在每种参数组合下独立运行10次，最大运行时间^[11]为 ${{G}} \times \displaystyle \sum\limits_g^{{G}} {\displaystyle \sum\limits_i^{{S_g}} {{{{K}}_i}} } \times 10\;{{S}}$，其中，S指阶段的工序数，如S₁指阶段1的工序数. 以P=5，K=67算例为例，将求得F均值作为评价指标（ARV）. 表2为正交实验的结果，图9为参数变化对算法性能影响趋势图. 图中，lev为表1中的水平值. 从中可知，当Nf=51、ng=5、C₀=20时，算法性能最好，后续实验中将采用这一参数组合. 上述没有最优参数组合的实验，按上述实验方式进行运算，可得到ARV为10 602，比上述参数组合的ARV都小，再次验证这一参数组合的有效性.

为了验证建立模型的正确性，使用EMBO算法和CPLEX分别独立运行10次求解. 由于研究问题是一个强NP-难问题，当问题规模逐渐变大时，计算量显著增加. CPLEX对于上述算例，求解时间过长，因此以图3的产品1与产品1、2为2种算例求解，设各阶段工序最大批次数都为2，得到实验结果并进行相对偏差率（PRD）比较，统计结果如表3所示. 从表3中可以看出，第1组算例EMBO算法得到与 CPLEX 一样的响应值，第2组算例中两者的响应值虽然不一样，但是PRD仅为7.3‰，表明两者之间的间隙极小，证明EMBO算法的有效性.

采用不等量可变策略进行批量划分，为了验证此策略效果，将其与等量可变策略进行对比，考虑生产规模，产品种类数与最大子批数总数不同，选取P=5，K=67与P=9，K=78这2种算例，使用EMBO算法分别独立运行10次，得到实验结果如图10所示. 图中，N_o为实验次数，F为最小化最大产品完工时间. 从图10中可知，对于不等量可变与等量可变2种批量划分策略，在批次数量相同时，不等量策略通过在各阶段的批量划分，子批数量更灵活，充分利用设备，减少设备空闲时间，从而减少最大完工时间. 当生产产品越多，批次数量越多时，不等量策略效果越好. 算例结果表明不等量策略优于等量策略5%~6%.

为了验证EMBO算法性能，选取改进遗传算法（improved genetic algorithm, IGA）^[19]、改进粒子群算法（improved particle swarm optimization, IPSO）^[26]和改进候鸟算法（improved migrating birds optimization, IMBO）^[21]这3种解决柔性流水车间调度问题的有效算法，采用原文推荐参数设置，进行对比实验. 此外，因本研究问题与文献问题存在差别，对算法进行调整. 因问题的NP 难特性，以多次重复实验得到的最优解平均值Avg来衡量算法求解精度，采用最优解标准偏差Std来评价算法稳定性. 按4种不同产品规模每种随机生成3个算例，每种算例算法独立运行10次，统计得到每组实验的Avg与Std，以及相对标准偏差（RSD），结果如表4所示.

从表4中可知，EMBO与IMBO算法的最优解均值均明显优于IGA与IPSO算法的最优解均值，且EMBO算法的最优解均值一般优于IMBO算法的最优解均值，但2种候鸟算法的最优解相差不大，且标准偏差也相差不大，需对EMBO算法与IMBO算法进行t检验进一步比较，结果如表5所示. 在大多算例中EMBO算法的最优解均值都优于IMBO算法的最优解均值，个别算例中EMBO算法的最优解均值也较优，由此得到在不等量可变分批策略下的3阶段批量流混合装配流水车间调度问题中，EMBO算法的优化结果存在显著的优越性. 此外，在不同子批总数的多数情况下，EMBO算法与其它3种算法相比，得到的RSD 更小，并且最大的RSD仅为1.94%，表明EMBO算法的优化结果更稳定，具有较强的鲁棒性. 取P=5，K=67算例进行4种算法的收敛与运行时间比较，如图11所示，其中t为CPU运行时间，F为最小化最大产品完工时间. 从图11中可知，虽然IGA和IPSO算法的收敛速度较快，但在一定运行时间内EMBO和IMBO算法的收敛精度比IGA和IPSO算法都好. EMBO与IMBO相比较，EMBO算法的收敛速度更快，且更易于跳出局部最优，验证EMBO算法的有效性.

针对3阶段批量流混合装配流水车间调度问题提出了有效候鸟优化算法（EMBO）. 针对不等量可变分批策略，与等量可变分批策略进行比较，证明在批量流混合装配流水车间调度问题中， 不等量可变分批策略更有效. 最后，通过对不同规模算例的随机重复实验，与其他求解分批问题的智能算法进行对比，验证EMBO算法求解混合装配流水不等量可变分批调度问题的有效性与鲁棒性. 研究3阶段批量流混合装配流水车间调度问题，并建立数学模型；研究在批量流混合装配流水车间中的批量划分策略，并对不同策略进行比较；设计一种EMBO算法，提出基于批量划分与排列顺序2个子问题的两段编码，设计一种同时优化2个子问题的领域结构和针对多种领域结构的自适应调节策略. 本研究优化目标为最大完工时间，未来将引入交货期、生产成本和总流经时间等多目标更符合实际生产，以此进一步研究批量流调度.