无关并行机类型混合流水车间成组调度问题的改进候鸟优化算法

袁帅鹏，李铁克，王柏琳

(1.北京科技大学 经济管理学院，北京 100083；2.钢铁生产制造执行系统技术教育部工程研究中心，北京 100083)

0 引言

成组调度(Group Scheduling, GS)源于单元制造系统，是一种利用工件在设计和加工上的相似性，将工件进行分组加工，以提高生产效率的生产组织方法。由于其结构化、高效率和低成本的生产优势，GS已广泛应用于汽车装配[1]、电路板印刷[2]、钢铁制造[3]等领域。迄今，已有关于GS问题的研究成果主要聚焦于经典的流水车间环境，问题假定同一阶段有且仅有一台机器[4]，而实际的工业环境多以混合流水车间为主，即通常会在瓶颈工序设置多台并行机以平衡各阶段的生产节奏、降低瓶颈工序对系统产出的影响。相比前者，混合流水车间具有更好的灵活性和稳定性，但同时也增加了调度问题求解的难度。因此，对混合流水车间环境下的GS问题展开研究具有重要的理论意义和实用价值。

与经典调度问题不同，GS需要同时考虑工件组间调度和各工件组内工件间调度两个相关子问题，对于混合流水车间成组调度(Hybrid Flowshop Group Scheduling, HFSGS)问题，还需要进一步考虑各工件组在各阶段并行机上的指派过程，是一类复杂的联合决策优化问题。此外，在HFSGS问题中，由于同组内工件间的相似性，组内工件间切换的准备时间通常可以忽略(或视为加工时间的一部分)，但需考虑工件组间切换的准备时间。LOGENDRAN等[5]首次对具有序列不相关准备时间和一致并行机类型的HFSGS问题进行了研究，分析了存在单准备时间和多准备时间两种情况下问题的性质特征，并提出一种三阶段启发式算法(LN-PT-M)；SHAHVARI等[6]指出序列相关准备时间具有更为重要的实际意义，进而对带有序列相关准备时间的HFSGS问题展开研究，以最小化Makespan为目标建立了混合整数线性规划模型，并提出6种改进的禁忌搜索算法；针对同样的问题，KESHAVARZ等[7]开发了一种文化基因算法，并基于所设计算法给出了问题最优解的下界；KARIMI等[8]同时考虑了最小化Makespan和加权拖期两个优化目标，构建了问题的数学模型，并提出一种改进的多阶段非支配排序遗传算法；FENG等[9]进一步研究了一类具有预防性维护的HFSGS问题，从设备和系统两个层面分别构建了问题的数学模型，并提出一种嵌套遗传进化的模拟退化算法；SHAHVARI[10]研究了一类混合流水车间批处理调度问题，与本文问题不同，该问题未考虑成组技术假设，假定同组内的工件可拆分为更小的批次且可以被分配到不同的设备上加工，以最小化总加权完工时间和总加权拖期为目标构建了问题的混合整数线性规划模型，并提出一种改进的禁忌搜索算法。

上述文献为HFSGS问题的研究提供了良好的理论基础，但已有成果均基于一致并行机环境，即假定工件在同一阶段上的加工时间为定值。而在部分工业环境中，由于新老设备的交替使用，无关并行机(工件在同一阶段上的加工时间与选取的并行机有关)的应用场景屡见不鲜，此种情况下工件在各阶段上的指派过程会更加复杂，这对问题性质分析和模型构建都提出了新的挑战。此外，由于HFSGS属于一类多维度、联合决策优化问题，而已有研究多采用分阶段的方式对多个子问题进行单独求解，缺乏对问题特征知识的挖掘以及子问题间关联特征的分析，导致算法的稳健性较差。鉴于以上两点，本文在考虑序列相关准备时间约束的情况下，对无关并行机类型的HFSGS问题展开研究，首先以最小化Makespan为目标建立了问题的数学模型，然后结合问题的联合决策特征提出一种改进的候鸟优化算法，算法基于负载均衡思想和改进先到先得策略对染色体进行解码，进化过程中开发了不同的邻域搜索机制来构造邻域结构，并提出一种协同优化的邻域解生成策略。最后，基于不同问题规模的数据实验对模型和算法的有效性进行验证。

1 问题描述及模型

1.1 问题描述

考虑序列相关准备时间和无关并行机类型的HFSGS问题可描述如下：①工件被划分为若干工件组并在多阶段流水车间环境下加工，至少有一个阶段存在多于1台的并行机；②并行机类型为无关并行机，即同一阶段上的并行机具有不同处理速度，工件在某一阶段的加工时间与选取的并行机有关；③对于同工件组内的工件，在每一阶段上能且仅能选取一台并行机进行加工，且加工过程必须连续，不能被其他工件组内的工件打断；③各阶段上的并行机在切换不同工件组时存在一定的准备时间，该准备时间序列相关，即准备时间不仅与将要加工的工件组有关，还与紧前加工的工件组有关；⑤目标为最小化最大完工时间，即Makespan。

该问题需要确定工件组间的加工顺序、各工件组内工件间的加工顺序以及各工件组在各阶段上并行机的指派3个子问题，使得所有工件的最大完工时间尽可能小。若使用FFm表示无关并行机类型的混合流水车间环境，fmls表示成组调度，sijk表示序列相关准备时间，Cmax表示最大完工时间，根据三元组表示法，本文问题可描述为FFm|fmls,sijk|Cmax。为使问题更加明确，本文基于以下假设：

(1)阶段间缓冲区的容量无限；

(2)所有工件、并行机在调度零时刻均为可用状态，不考虑工件在阶段间的运输时间；

(3)生产环境具有稳定性，不考虑设备故障、工件的恶化和学习效应。

1.2 数学模型

为对问题FFm|fmls,sijk|Cmax进行准确描述，本节采用0-1整型决策变量的方式建立了其混合整数线性规划模型，其中涉及的符号及含义如表1所示。

表1 符号变量含义

其混合整数线性规划模型描述如下：

minCmax。

(1)

(2)

(3)

xi′ik+xii′k≤1,i=1,…,g,i′=1,…,g,

k=1,…,K;

(4)

(5)

(6)

i′=1,…,g,i=1,…,g，k=1,…,K；

(7)

Sik+M(2-xi′ik-zikh)≥Ci′k+si′ikh，

i=1,…,g，i′=0,…,g，k=1,…,K，

h=1,…,Mk；

(8)

cilk-pilkh+M(1-zikh)≥Sik,i=1,…,g，

l=1,…,ni，k=1,…,K，h=1,…,Mk；

(9)

cilk-pilkh+M(2-zikh-yil′l)≥cil′k,

i=1,…,g,1≤l′

k=1,…,K,h=1,…,Mk;

(10)

cil′k-pil′kh+M(1-zikh+yil′l)≥cilk,

i=1,…,g,1≤l′

k=1,…,K,h=1,…,Mk;

(11)

cilk-pilkh+M(1-zikh)≥0,i=1,2,…,g,

l=1,…,ni,k=1,h=1,…,Mk;

(12)

cilk-pilkh+M(1-zikh)≥cil(k-1),i=1,2,…,g,

l=1,…,ni,k=2,…,K,h=1,…,Mk;

(13)

Cik≥cilk,i=1,…,g,l=1,…,ni,k=1,…,K;

(14)

Cmax≥Cik,i=1,…,g,k=1,…,K;

(15)

Sik,Cik,cilk≥0,i=1,…,g,

l=1,…,ni,k=1,…,K;

(16)

xi′ik,yil′l,zikh∈{0,1},i,i′=1,…,g,

1≤l′

(17)

目标函数(1)表示最小化最大完工时间，即Makespan；约束(2)～约束(4)表示在任一阶段上，各工件组均有且仅有一个紧前工件组(包含虚拟工件组G0)、至多一个紧后工件组，且两者不能为同一个；约束(5)表示在任一阶段的任一并行机上，有且仅有一个虚拟工件组G0，且G0必须安排在首个位置进行加工；约束(6)表示对于任一工件组，在每一阶段仅能选取一台并行机进行加工；约束(7)表示决策变量xi′ik和zikh之间的限制关系：在任一阶段，只有两个工件组在同一台并行机加工时，才有可能存在紧邻关系；约束(8)表示如果两个工件组在某阶段上存在紧邻关系，则后续工件组内任一工件的开工时间不小于紧前工件组的完工时间；约束(9)表示各工件在各阶段上的开工时间要至少大于所在工件组在该阶段上的开工时间；约束(10)和约束(11)为同工件组内工件间的序列约束，即对于具有先后顺序(不一定紧邻)的两个工件，后续工件的开工时间至少大于先前工件的完工时间；约束(12)表示任一工件在第一阶段上的完工时间要大于其加工时间；约束(13)表示对于任一工件，只有在当前工序完工后才可开始下一道工序的加工；约束(14)表示各工件组在各阶段上的完工时间；约束(15)定义了所有工件组的最大完工时间；约束(16)～约束(17)为决策变量的取值范围。该模型已通过CPLEX数学规划软件验证了其正确性(详见3.3节最优性检验)。

2 改进的候鸟优化算法

由于问题FFm|fmls,sijk|Cmax的强NP难特性[5]，精确算法虽在理论上可以得到最优解，但求解时间会随着问题规模的增加呈指数倍增长，无法满足实际应用的需要，而基于智能优化的元启发式算法为快速求解该类问题提供了一种有效途径。

候鸟优化(Migrating Birds Optimization, MBO)算法是一种新兴的、基于种群进化和邻域搜索的元启发式算法，它通过模拟候鸟迁徙过程中V形队列能够提高鸟群飞行速度这一生物现象对问题进行优化[11]。MBO将每一个解视为鸟群中的一只鸟，优化过程包括鸟群初始化、领飞鸟进化、跟飞鸟进化和领飞鸟替换4个阶段，其中跟飞鸟被分为左种群子集和右种群子集两部分。在整个进化过程中，MBO采用左右群体集的并行搜索机制来指导种群进化，使得算法具有较强全局搜索能力。同时，MBO通过邻域共享机制来模拟个体间交互的过程，对于每一个体，会将自身较好的邻域解共享至下一个个体，这种独特的个体进化机制能够快速锁定种群中的优势邻域结构，促使算法以较快的速度向优势解的方向进化。当前，MBO算法在求解调度类组合优化问题方面已取得较好的效果[12-13]。据此，本文结合MBO的优化机制和FFm|fmls,sijk|Cmax问题的特征，提出一种改进的候鸟优化(Enhanced MBO, EMBO)算法。EMBO采用置换序列的方式对染色体进行编码，基于负载均衡思想和改进的先到先得策略将染色体解码为问题的可行解；提出了一种基于准备时间的最优插入策略来构造可行解的邻域结构，并提出一种协同优化的邻域解生成策略；为避免算法陷入局部最优，设计了一种基于年龄阈值的重置机制。算法实施过程如下。

2.1 编码解码策略

2.1.1 编码策略

2.1.2 解码策略

考虑到各并行机具有不同的加工能力，解码时首先基于负载均衡思想确定第一阶段各并行机加工工件组的数量(记为σh)，然后结合子集X确定各工件组在第一阶段上并行机的选择及同一并行机上工件组间的加工顺序，再由子集Yi确定各工件组内工件间的加工顺序；对于后续阶段，根据上一阶段的完工顺序，采用改进的先到先得策略确定各工件组在各阶段上的并行机的选择。具体实施步骤如下：

步骤1使用式(18)计算σh的值：

σh=

(18)

步骤3由式(19)确定各工件组在第一阶段所选取并行机的编号，记为I1(i)：

I1(i)=GV(X(i)),i=1,2,…,g。

(19)

步骤4对于在同一并行机上加工的工件组集，按照子集X中出现的顺序依次加工。

步骤5对于后续阶段k(k=2,…,K)，使用式(20)确定工件组Gi(假定紧前工件组为Gi′)所选取的并行机编号Ik(i)，并按照上一阶段完工的顺序依次加工：

i=1,…,g，k=2,…,K。

(20)

由上述实施步骤可以看出，解码过程充分考虑了并行机的负载均衡，并在先到先得策略基础之上进一步考虑了工件组在各并行机上准备时间的差异性，使得算法具有较大的概率得到更好解。

2.2 邻域解的生成

MBO是一种基于邻域搜索的元启发算法，邻域结构的设计对算法性能至关重要。由2.1节的编码策略可以看出，子集X和Yi分别表示不同的子问题，为提高算法搜索效率，本节针对子集X和Yi设计了不同的邻域构造方案，并提出一种协同优化策略将两个子集整合为完成的邻域解，具体如下。

2.2.1 子集X邻域结构设计

子集X主要用来确定各工件组在第一阶段上并行机的选择以及同一并行机上工件组间的加工顺序，为搜索优质解，在构造邻域时要充分考虑各工件组在各阶段并行机上加工时间和准备时间的大小及差异性。本文以常用于组合优化问题的插入算子为基础，提出一种基于准备时间的最优插入操作来构造子集X的邻域结构，实施步骤如下：

步骤1从子集X中随机抽取一个工件组。

步骤2结合2.1节解码策略中构造的辅助向量GV，按照最小准备时间原则在每个并行机基因区域内选取1个插入点，进而得到m1个插入位置。

步骤3根据插入位置得到m1个新工件组序列。

步骤4计算所得到新工件组序列的目标值，选取最优者作为子集X的邻域结构。

传统的插入操作通常会随机选取若干插入点，或插入所有可能的位置，这两种方案均有一定的局限性。在所设计的算子中，被选取的工件组会按照最小准备时间原则选取各并行机区域内的最优插入位置，具有较强的针对性。以图1中的染色体为例，假定第一阶段并行机的数量M1=2，通过解码策略得到的辅助向量GV=[1,1,1,2,2]，图2给出了子集X邻域结构设计的详细过程。

2.2.2 子集Yi邻域结构设计

对于子集Yi，由于同工件组内的工件在任一阶段上均只能选取一台并行机进行加工，且无需考虑工件间切换的准备时间，因此不同工件序列对目标值的影响仅取决于工件的加工时间。鉴于此，算法采用常用于求解调度问题的前插、后插、随机交换和区块反转4种操作来构造其邻域结构，4种邻域操作的执行过程如图3所示。

2.2.3 邻域解的生成

虽然子集X和Yi的邻域结构被独立设计，但两者具有很强的关联性，如何将它们有效组合进而产生完整的邻域解对算法性能至关重要。考虑到问题FFm|fmls,sijk|Cmax的联合决策特征，本文设计了协同优化的邻域解生成策略，具体思路如下：首先从当前解的子集X中随机选取一个工件组(记为Gi)，然后以Gi为基准，对当前解中Gi对应的工件序列Yi执行邻域构造操作，并从中选取最优者插入Yi对应的位置；随后，以更新后的工件序列为基准，将Gi按照最小准备时间插入策略选取最优插入位置，得到一个邻域解；重复上述过程直至得到给定数量的邻域解。在构造邻域解的过程中，为避免对同一工件组及其内的工件序列执行重复操作，我们引入禁忌搜索的思想，即对于任一个体，把每次随机选取的工件组放入禁忌表中，在构造下一个邻域解时，检测所选取的工件组是否已被存入禁忌表，如果存在则重新选取。

仍以图1中的染色体为例，邻域解的生成过程可用图4表示。根据其执行过程可以看出，在每次迭代过程中，该策略能够针对特定的工件组及其工件序列进行协同优化。

2.3 重置机制

为有效平衡算法的全局搜索和局部搜索能力，本文提出一种基于年龄阈值的重置机制：首先为所有个体赋予初始值为1的年龄参数，在每一次迭代过程中，若当前解不能由其最好的邻域解替换，则将其年龄值增加1；否则，将当前解的年龄值初始化为1。显然，年龄越小表示后续迭代中找到更优解的可能性越高，而年龄越大表示找到更好解的可能性较低，并且可能会陷入局部最优状态。因此，若个体的年龄值超过预先设定的阈值(记为limits)，则采用随机生成的方式重置当前个体。

2.4 算法流程

基于以上算法设计，EMBO算法求解问题FFm|fmls,sijk|Cmax的具体步骤如下：

步骤1初始化算法参数，包括种群规模p_size，每个个体产生自身邻域解的数量α，传递给下一个个体邻域解的数量β，巡回次数T，年龄阈值limits。

步骤2结合2.1节的编码策略随机生成初始种群，并将初始种群划分为领飞鸟、左种群子集和右种群子集3部分。

步骤3领飞鸟进化。采用2.2节的邻域解生成策略构造当前领飞鸟的α个邻域解，若邻域解集中的最优者优于当前领飞鸟，则使其替换之；然后从未使用的邻域解中选取较优的β个邻域解加入左、右共享邻域集(分别记为PNL和PNR)。

步骤4左种群子集进化。对于左种群子集中的每一个解(跟飞鸟)，同样采用2.2节的邻域解生成策略构造α-β个邻域解，然后将α-β个邻域解和共享邻域集中的β个邻域解合并形成邻域解集，若邻域解集中的最优者优于当前跟飞鸟，则替换之；随后从未使用的邻域解中选取较优的β个邻域解更新PNL。

步骤5执行与步骤4相似的操作更新右种群子集中的每一个解。

步骤6启用2.3节的重置机制对当前种群进行更新。

步骤7检查是否达到巡回次数T，若未达到，转步骤2；否则，将领飞鸟随机移动到左(或右)队列的尾部，左(或右)队列中的第一只飞鸟成为新的领飞鸟。

步骤8判断终止条件，若不满足，转步骤2；否则，输出最优解及目标值。

3 仿真实验

3.1 实验设计

实验首先基于小问题规模测试算例将EMBO的运行结果与混合整数线性规划模型取得的最优解进行对比，以检验EMBO的最优性；然后从文献中选取了3种求解HFSGS问题的元启发式算法，并基于大问题规模的测试算例将EMBO的运行结果与3种算法进行对比，以检验EMBO的有效性。实验中所有算法均使用MATLAB R2015a编程实现，模型采用ILOG CPLEX 12.7.0数学规划软件进行求解，算法测试环境为Intel i5-6200U/CPU 2.40 GHz/8.0 GB。

由于未发现可直接应用于本文问题的基准数据，本文选取文献[7](研究一致并行机环境下具有序列相关准备时间HFSGS问题)中的实验数据作为参考，并对其进行修正和扩充，得到以下实验数据：阶段数量K∈{2,3,5,7}，工件组数量g∈{3,4,5,10,15,30}，各工件组内工件的数量ni∈{3,4,5,10}。根据阶段数量、工件组和各工件组内工件数量将以上数据分为6组小问题规模的实验(K=2、g∈{3,4,5}和ni∈{3,4}的正交组合)和18组大问题规模的实验(K∈{3,5,7}、g∈{10,15,30}和ni∈{5,10})。实验中其他问题参数设置如下：每一阶段并行机的数量为Mk∈DU[1,3]，工件加工时间pilkh∈DU[5,75]，序列相关准备时间si′ikh∈DU[5,50]，数据格式DU[a,b]表示介于a和b之间的离散均匀分布。

每组实验随机生成10组测试算例，采用相对偏差率(PRD)[14]来衡量算法性能，PRD计算公式为：

(21)

式中：Cmax(A)表示当前测试算例算法A得到的Cmax值，ref为当前测试算例的参考值：对于小问题规模的算例，选取混合整数线性规划模型取得的最优值作为参考；对于大问题规模的测试算例，选取所有算法得到的最好解作为参考。

3.2 算法参数设置

算法参数设置对算法性能起着重要的作用。EMBO中的算法参数包括：种群规模p_size，邻域解的生成数量α，邻域解的传递数量β，巡回次数T，年龄阈值limits。其中，α要至少大于β+1，以确保当前解的邻域集中有足够的邻域解共享至后者。已有文献均将α设置为3，将β设置为1，通过预备实验发现这种参数设置同样适用于本文问题且具有较好的效果，因此EMBO采用同样的参数设置。对于其他3个参数，使用田口实验设计方法[15]探讨参数对算法性能的影响，针对每个参数设置4个水平值，具体如表2所示。并选用中等问题规模的样本数据(K=5,n=15,ni=10)为例，使用EMBO对每组参数组合方案独立运行10次，将10次求得Cmax的均值作为评价指标(ARV)，结果如表3所示。

表2 参数组合方案

表3 参数组合正交表及其评价指标值

续表3

根据表3进一步统计了各个参数的响应值和对算法性能的影响趋势图，结果分别如表4和图5所示。由表4的统计结果可知，种群规模p_size对算法性能的影响最大，其次是巡回次数T，最大维持代数limit对算法性能的影响程度最小。结合图5可以看出，当p_size=11，T=20，limits=10时算法具有最好的性能，因此以下实验均采用此参数设置。

表4 不同参数的响应值

3.3 最优性检验

由表5可以看出，第一组实验10组测试算例EMBO均得到了与CPLEX一样的目标值，这证实了本文所设计模型的正确性，同时也说明EMBO针对小问题规模搜索最优解的有效性。随着问题规模的增加，EMBO取得的PRD均值呈现增加趋势，但6组实验EMBO的总体PRD均值仅为0.94%，这表明对于小问题规模的测试算例EMBO得到的Cmax值与最优解的间隙非常的小。由SR值可以看出，56组测试算例(忽略4组CPLEX未得到最优解的算例)中共35组得到了最优解，这表明对于多半测试算例(约62.5%)EMBO均能在有限的时间内得到最优解。以上结果说明，对于小问题规模的测试算例，本文提出的EMBO具有很好的优化性能。

表5 最优性测试结果

3.4 与元启发式算法对比

为进一步测试EMBO的性能，本文选取了3种针对HFSGS问题提出的元启发式算法，分别为文献[6]的禁忌搜索算法(Tabu Search, TS)、文献[7]的文化基因算法(Memetic Algorithm, MA)和文献[8]的遗传算法(Genetic Algorithm, GA)。将这3种算法应用至本文问题，并将其求解性能与所提出的EMBO算法和CPLEX求得的可行解(非最优解)进行对比，3种算法均采用原文推荐的参数设置。此外，由于本文问题与文献中所研究问题存在一定的差别，实验过程中对3种算法的评价函数做了适应性调整。

表6 四种算法和CPLEX的PRD均值(Mean)、标准差(Std.)统计结果

表7 不同阶段和工件规模下四种算法及 CPLEX总体PRD均值对比

由表6的统计结果可以看出，18组测试实验中EMBO的PRD均值全部低于其他3种算法和CPLEX，且所有测试实验EMBO的总体PRD均值仅为1.32%，明显低于GA(4.17%)、TS(3.30%)、MA(5.41%)和CPLEX(3.84%)，这表明EMBO的求解质量优于其他3种算法和CPLEX。对于PRD值的标准差，仅有1组实验(K=7,g×ni=20×10)EMBO略高于TS，其他实验EMBO均为4种算法中的最低者，且其总体PRD值的标准差为0.55%，同样低于GA(1.43%)、TS(0.76%)和MA(0.75%)和CPLEX(0.91%)，说明EMBO在获取较优解的同时，求解性能也相对稳定。

由表7可知，当阶段数量相同时，随着问题规模的增加，4种算法的总体PRD均值都在逐渐降低(如：当K=2时，EMBO在3种问题规模下所有测试算例的总体PRD均值分别为2.25%，1.87%，1.45%)，说明针对本文问题，4种算法的求解质量均具有较好的稳健性，其中EMBO始终低于其他3种算法，这表明EMBO在不同工件规模下均能得到相对较好的解；当问题规模相同时，随着阶段数量的增加，所有测试算例EMBO、TS、MA三种算法求得的总体PRD均值同样逐渐减小，且EMBO始终处于较低的水平，而GA出现震荡的情况，这进一步说明了EMBO在求解质量和稳定性方面的优越性，同时说明EMBO、TS、MA三种算法优于GA。整体上，不同问题规模和阶段数量下CPLEX求得的总体PRD均值不存在严格的变化规律，但始终高于EMBO算法，这说明即使给予较长的求解时间，CPLEX的求解性能也弱于EMBO算法。另外，根据表8的检验结果可知，18组测试实验EMBO与其他3种算法以及CPLEX通过配对t检验得到的p值均小于0.05，这进一步说明与其他3种算法和CPLEX取得的可行解相比，EMBO的求解质量存在显著的优越性。

表8 四种算法和CPLEX的PRD均值配对t检验结果

基于以上分析，可得出结论：针对问题FFm|fmls,sijk|Cmax，本文提出的EMBO算法在求解质量和稳定性方面优于TS、MA、GA和CPLEX。

4 结束语

本文研究了一类带有序列相关准备时间和无关并行机类型的混合流水车间成组调度问题，该问题具有较为广泛的工业应用背景，但相关研究成果很少。为高效求解此调度问题，首先以最小化最大完工时间为目标构建了混合整数线性规划模型，然后结合问题特征提出一种改进的候鸟优化算法。在该算法中，通过一种新的编码和解码策略来表征问题的解，设计了不同的邻域搜索机制来构造邻域结构，并提出一种协同优化的邻域解生成策略，为避免算法陷入局部最优，开发了一种基于年龄阈值的重置机制。实验阶段，首先采用田口实验方法确定了算法的最佳参数组合，然后基于小问题规模的测试算例验证了模型的正确性和所提算法的最优性能，最后基于大问题规模的测试算例将所提算法与其他主流元启发式算法进行了对比，证实了所提算法的高效性和稳健性。本文创新点如下：①研究了无关并行机类型的混合流水车间成组调度问题，给出了问题的混合整数线性规划模型；②设计了一种改进的候鸟优化算法，算法提出了基于负载均衡和改进先到先得的解码策略、基于准备时间的最优插入策略和协同优化的邻域解生成策略，显著提升了算法的求解性能；③所设计的协同优化策略也可以为其他具有联合决策特征调度问题的求解提供有效途径。

本文的优化目标为最小化最大完工时间，但实际工业应用中往往需要考虑多个优化目标，因此基于多目标优化的混合流水车间成组调度问题是未来进一步研究的方向。