一种用于混合流水车间调度问题的改进候鸟优化方法

摘要

本发明公开了一种用于混合流水车间调度问题的改进候鸟优化方法，该方法包括：在之前进化代数，采用排列解码方式对跟飞鸟个体和领飞鸟个体进行解码，实现对跟飞鸟个体和领飞鸟个体的进化；在超过进化代数临界值后，依概率采用微调排列解码方式对跟飞鸟个体和领飞鸟个体解码，实现对跟飞鸟个体和领飞鸟个体的进化；通过判断进化代数是否满足要求，获得混合流水车间调度最佳方案。在本发明提供的改进候鸟优化方法中，微调排列解码不严格按照排列解码方法中的先到先加工原则，这增加了搜索到更好解的可能性；将排列解码步骤和微调排列解码步骤相结合，加快采用微调排列解码的改进候鸟优化算法的收敛速度。

说明书

技术领域

本发明属于计算机集成制造技术领域，更具体地，涉及一种用于混合流水车间调度问题的改进候鸟优化方法。

背景技术

混合流水车间调度问题(Hybrid flow-shop scheduling problem，HFSP)，又称柔性流水车间调度问题，由Salvador在1973年首先提出，该问题可以看作是经典流水车间调度问题与并行机调度问题的结合。在HFSP问题中，至少有一个阶段中处理机的个数大于1，这大大增加了HFSP的求解难度，已证明处理机数分别为2和1的两阶段的HFSP是NP-hard问题。按并行机种类的不同HFSP分为三类：相同并行机、均匀并行机和不相关并行机。混合流水车间调度问题在机械、物流、钢铁、纺织等领域有广泛的应用，譬如曲轴生产线、PCB板生产线等，因此研究HFSP对实际生产具有重要的意义。

自HFSP提出之后，学者们探索各种求解HFSP的方法，目前求解HFSP方法主要可分为三类：精确算法、启发式规则和元启发式规则。精确算法，如分支定界法(B&B)，在问题规模小、问题性质不复杂的情况下可以求得问题的精确解，但实际调度问题往往求解空间太大，因此很难用精确算法求解；启发式规则，如优先分配规则，优点是能够快速构建问题的解，但启发式规则是局部优化方法，很难得到全局最优结果；Panwalkar等人在1977年对113种不同的规则进行了总结，Montazeri等针对FMS总结了20条常见的规则并分析了这些规则的性能；元启发式算法通过模拟某些自然现象和规律，具有较好的稳定性，近年来广泛应用于求解HFSP，如遗传算法(Genetic algorithm，GA)、人工免疫系统算法(ArtificialImmune System，AIS)、人工蜂群算法(Artificial Bee Colony，ABC)、蚁群算法(AntColony Optimization，ACO)、粒子群算法(Particle Swarm Optimization，PSO)、分布估计算法(Estimation of Distribution Algorithm，EDA)等。一个较好的元启发式算法即使不能求得问题的最优解，但能够求得与最优解尽可能接近的较好解，近年来的研究趋势是将启发式规则与元启发式算法相结合，这大大提高元启发式算法的性能，如Pan首次提出24种启发式规则，并运用到离散人工蜂群算法中来求解混合流水车间总完工时间最小化问题。

候鸟优化算法(Migratory Bird Optimization，MBO)是一种新兴的元启发式算法，它通过模拟候鸟迁徙过程中V字队形减少能量损耗来对问题进行优化。MBO最早年由Duman在2012年提出并将其运用二次分配问题的求解上，获得解的质量优于遗传算法、模拟退火算法、禁忌搜索算法、粒子群算法等。此后，MBO被应用于解决各种问题，如信用卡欺诈检测问题、排课问题、连续函数问题等。同时，越来越多的学者尝试将MBO运用到生产线调度上：Pan将MBO用于混合流水车间调度问题；谢展鹏用MBO求解了阻塞流水车间的调度问题，通过求解经典算例验证了MBO的有效性和鲁棒性；Benkalai用MBO求解了准备时间与序列相关的置换流水车间调度问题；Tongur用MBO求解了流水车间调度问题。

发明内容

针对现有技术的以上缺陷或改进需求，本发明提供了一种用于混合流水车间调度问题的改进候鸟优化方法，其目的在于解决现有用于混合流水车间调度问题的优化方法容易陷入局部最优而无法获得更优混合流水车间调度方案的技术问题。

为实现上述目的，本发明提供一种用于混合流水车间调度问题的改进候鸟优化方法，包括如下步骤：

步骤1：初始化领飞鸟个体、跟飞鸟个体、巡回次数及进化代数；

步骤2：判断进化代数是否大于进化代数临界值，若是进入步骤4，否则，进入步骤3；

步骤3：采用排列解码方式对领飞鸟个体和跟飞鸟个体进行进化获得进化后个体，并更新进化代数后进入步骤2；

步骤4：根据领飞鸟个体产生领飞鸟个体邻域解，并依概率以微调排列解码方式获得领飞鸟个体邻域解的目标值，并以最优目标值对应的领飞鸟邻域解作为进化后领飞鸟；

步骤5：根据跟飞鸟个体和领飞鸟个体邻域解产生跟飞鸟个体邻域解，并依概率以微调排列解码方式获得跟飞鸟个体邻域解的目标值，并以最优目标值对应的跟飞鸟邻域解作为进化后跟飞鸟；

步骤6：判断巡回次数是否达到巡回次数临界值，若是，用进化后跟飞鸟作为本代领飞鸟，获得进化后个体，并初始化巡回次数进入步骤7，否则，更新巡回次数并进入步骤4；

步骤7：判断进化代数是否达到进化总代数，若是，则将进化后种群中领飞鸟个体作为混合流水车间调度方案，否则，更新进化代数并进入步骤4。

优选地，依概率微调排列解码方式包括如下子步骤：

步骤21：将各个工件在第s-1个阶段中的完工时间进行升序排列获得第s个工件序列和第s个完工时间序列；

步骤22：根据第r次更新第s个完工时间序列中第j对相邻完工时间的差值获得第r次更新第j个微调概率；

步骤23：判断第r次更新第j个微调概率是否大于随机值，若是，则调换第r次更新第s个工件序列中第j对相邻工件的前后顺序和第r次更新第s个完工时间序列中第j对相邻完工时间的前后顺序，获得第r+1次更新第s个工件序列和第r+1次更新第s个完工时间序列；否则，第r+1次更新第s个工件序列为第r次更新第s个工件序列，第r+1次更新第s个完工时间序列为第r次更新第s个完工时间序列；

步骤24：判断对次序j是否等于对总数n-1，若是，将第r+1次更新第s个工件序列作为第s个最终工件序列，并进入步骤25；否则，令r＝r+1，j＝j+1，进入步骤22；

步骤25：判断加工阶段次序s是否等于加工阶段总数k，若是，将完成k个加工阶段的最大完工时间作为领飞鸟或者跟飞鸟的目标值；否则，令s＝s+1，r＝1，j＝1，并进入步骤21；

其中，第1阶段中的工件序列根据领飞鸟或者跟飞鸟确定，第1次更新第s个完工时间序列为步骤21中的第s个工件序列，第1次更新第s个工件序列为步骤21中的第s个工件序列。

优选地，步骤22中根据公式获得第j个微调概率；

其中，为工件序列中第j个工件对应的工件完工时间。

优选地，对跟飞鸟进行多次微调排列解码获得跟飞鸟的多个备选目标值，并将最优备选目标值作为跟飞鸟的目标值。

优选地，对领飞鸟进行多次微调排列解码获得领飞鸟的多个备选目标值，并将最优备选目标值作为领飞鸟的目标值。

优选地，通过对领飞鸟依概率进行最优插入和最优交换操作产生领飞鸟邻域解。

优选地，根据如下步骤获得跟飞鸟领域解：

对跟飞鸟进行最优插入和最优交换操作获得预备跟飞鸟领域解；

将预备跟飞鸟领域解和领飞鸟领域解中未替换领飞鸟的领飞鸟领域解作为跟飞鸟领域解。

优选地，步骤5和步骤6之间还包括如下步骤：

采用随机交换、前插操作、后插操作或序对交换四种操作对进化后跟飞鸟进行局部搜索获得局部跟飞鸟个体；

判断局部跟飞鸟个体的目标值是否优于进化后跟飞鸟个体的目标值，若是，则用最优目标值对应的局部跟飞鸟个体更新进化后跟飞鸟；否则，不更新进化后跟飞鸟。

优选地，步骤3包括如下子步骤：

步骤31：根据领飞鸟个体产生领飞鸟个体邻域解，并以排列解码方式获得领飞鸟个体邻域解的目标值，并以最优目标值对应的领飞鸟邻域解作为进化后领飞鸟；

步骤32：根据跟飞鸟个体和领飞鸟个体邻域解产生跟飞鸟个体邻域解，并以排列解码方式获得跟飞鸟个体邻域解的目标值，并以最优目标值对应的跟飞鸟邻域解作为进化后跟飞鸟；

步骤33：判断巡回次数是否达到巡回次数临界值，若是，用进化后跟飞鸟作为本代领飞鸟，获得进化后个体，并初始化巡回次数进入步骤2，否则，更新巡回次数并进入步骤31。

总体而言，通过本发明所构思的以上技术方案与现有技术相比，能够取得下列有益效果：

本发明根据混合流水车间调度问题的特点，基于原始排列解码方法，将一种概率模型与原始排列解码方法相结合，提出了一种微调排列解码方法，微调排列解码方法不严格按照原始排列解码方法中的先到先加工原则，这增加了搜索到更好解的可能性；为了加快采用微调排列解码方法的改进候鸟方法的收敛速度，将原始排列解码方法和微调排列解码方法相结合，进而提出一种两阶段解码的改进候鸟方法。

附图说明

图1为本发明提供的改进候鸟优化方法中混合流水车间调度问题的示意图；

图2为本发明提供的改进候鸟优化方法中候鸟飞行示意图；

图3为本发明提供的改进候鸟优化方法的流程示意图；

图4(a)为本发明中采用现有解码方法获得的四工件两阶段HFSP的甘特图；图4(b)为采用微调排列解码方法获得的四工件两阶段HFSP的甘特图；

图5为对算例j30c5e2采用不同解码方法的收敛曲线；

图6为本发明提供的改进候鸟优化方法中随机交换、前插操作、后插操作和序对交换四种操作示意图；

图7为采用本发明提供的改进候鸟优化方法对j30c5e6算例进行求解的甘特图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。

针对混合流水车间问题的特点，本发明提出改进候鸟优化优法解决以最小化完工时间为目标的混合流水车间调度问题，在改进候鸟优化优法中，采用微调排列解码方法，并与现有解码方法对比，验证提出解码方法的有效性，进而设计一种两阶段解码方法；提出了基于两阶段解码的改进候鸟优化方法，在该方法中设计了四种邻域结构仅对跟飞鸟进行局部搜索。应用改进候鸟优化方法求解相同并行机HFSP的Carlier和Neron经典算例，在24个较难算例和10个大规模算例，几乎都获得当前最好解，并发现一个新的当前最好解，证明了提出改进候鸟优化方法的有效性。

1混合流水车间调度问题

1.1问题描述

HFSP描述如下：现有n个工件J＝{1,2,..n.,，}k个加工阶段S＝{1,2,...,k}，每个加工阶段有m_s个并行机。要求满足以下约束条件：①所有工件以相同的顺序流经各个阶段；②至少有一个阶段的并行机数量大于1；③每个工件在每个阶段只能选择该阶段的一台并行机进行加工；④每台机器在任意时刻只能加工一个工件。本发明研究的HFSP需要以下假设：①所有工件在各个阶段的加工时间已知；②所有工件和机器在0时刻可获得；③两阶段之间的缓冲区无限大；④不考虑机器工件转换时间和工件在两阶段之间的运输时间；⑤所有工件以非抢占方式加工。本发明求解以最小完工时间为目标的HFSP问题，即在每个阶段为每个工件分配机器并确定每台机器上加工工件的顺序以使最大完工时间最小，HFSP的示意图如图1所示。

1.2数学模型

记n为工件总数，k为阶段总数，i为机器序号，j、j₁、j₂均为工件序号，s为阶段序号，P_js为工件j在阶段s加工所需的加工时间，S_js为工件j在阶段s的开始加工时间，F_js为工件j在阶段s的完工时间，m_s为阶段s的并行机数量，L为一个很大的常数，C_max为最大完工时间，且定义以下两个0-1变量，X_jis为判断工件j在阶段s是否在机器i上加工，为判断在阶段s，工件j₁是否先于工件j₂加工，即：

建立HFSP的数学模型如下：

Minimize C_max

且j₁≠j₂；s＝1,...,k>

且j₁≠j₂；s＝1,...k；i＝1,...m_s>

上述数学模型的优化目标是最小化HFSP的总完工时间。其中，式(1)是对最大完工时间的约束，即总完工时间大于所有工件在最后一个阶段的完工时间；式(2)用来计算每个工件在任何一个阶段的完工时间；式(3)保证了每个工件在每个阶段只能由该阶段的一台机器加工；式(4)保证了每个工件必须在上阶段加工完成后才能开始现阶段的加工；式(5)和式(6)是对机器加工容量的约束，既对于两个在同一台机器上加工的工件，只有当一个工件完成加工后，另一个工件才能开始加工；式(7)是0-1变量约束。

2候鸟优化算法

MBO灵感来源于候鸟迁徙过程中V字形队列在候鸟长途飞行中能够减少能量损耗这一生物现象。众所周知，单独候鸟在飞行过程中，翅膀扇动会让周围的空气流动进而形成旋涡，这股气流由中央向下流动，形成的压强对于后面飞行的候鸟有上升的作用，后方的候鸟利用这种压强可以节省自身消耗的能量，所以相比独自飞行，以V字形队伍飞行能够节省能量，进而提高候鸟群的飞行距离。Duman在2012年阐述这种现象，表明翅尖距离(Wing TipSpacing，WTS)和同一队列前后相邻的两只候鸟之间的距离(depth)是影响节约能量的多少的两个重要因素，并首先提出基于候鸟迁徙现象的MBO启发试算法，并将MBO运用到二次分配问题上，取得了很好的效果。图2为候鸟飞行示意图。

图3所示为改进候鸟优化方法的流程图，改进候鸟优化方法分为四个阶段，分别为：鸟群初始化、领飞鸟进化、跟飞鸟进化和领飞鸟替换。算法步骤介绍如下：

(1)鸟群初始化：用于产生整个候鸟群，包括左队列候鸟和右队列候鸟；

(2)领飞鸟进化：领飞鸟是指队列的第一只候鸟，领飞鸟进化指对领飞鸟进行邻域搜索，并用产生的邻域解中的最好解替代领飞鸟；

(3)跟飞鸟进化：在该跟飞鸟邻域搜索后获得的邻域解和该跟飞鸟前面的候鸟的邻域解中未使用的较好解中寻找最好解替换该跟飞鸟；

(4)领飞鸟替换：经过一定次数(巡回次数)的领飞鸟进化和跟飞鸟进化后，领飞鸟移动到左或右队列的尾部，领飞鸟后面的候鸟(左或右队列)成为新的领飞鸟。

上述过程一直进行到满足一定准则，然后输出最好的候鸟作为问题的解。

3候鸟优化算法解决混合流水车间调度问题

3.1编码方式

本发明中采用排列编码方式，即取所有工件序号的排列作为一个个体，然后在第一阶段按照各个工件在该排列中的位置，依次对工件进行机器选择。例如4个工件的情况，工件序列{1,2,4,3}，表示在第一阶段，先为工件1安排机器，然后依次为工件2、4、3安排机器。

3.2解码方式

在排列解码中，如果严格地按照先到先加工规则进行加工，则可能会错失更好解。如图4(a)和图4(b)所示，为4个工件2个阶段，每个阶段均有2台并行机,工件序列为{1,2,4,3}的加工甘特图，矩形块上的数字表示工件号。图4(a)中在第一阶段工件4的完工时间是10，工件3的完工时间是11，如果按照原始排列解码，在第二阶段应该先安排工件4再安排工件3，此时最大完工时间从图4(a)可以看出是27。但是，如图4(b)所示，如果在第二阶段，先安排工件3，即将工件3安排在机器3上，此时工件3的完工时间是25，再将工件4安排到机器4上，此时工件4的完工时间是25，此时，在阶段二先安排工件3再安排工件4的最大完工时间是25，小于先安排工件4再安排工件3的最大完工时间27。

从上述可以看出，以先到先加工规则进行加工虽然在很大程度上可以获得问题的较优解，但该规则也可能错失更好解。

本发明提出以概率对工件序列进行微调的解码方式，如式(8)所示，式中P表示微调概率，e为自然常数，Δ为各工件完工时间排升序后，相邻两个完工时间的差值。

本发明提出以概率对工件序列进行微调的解码方式如下：

首先，在第一阶段(s＝1)，按照给定的编码序列确定各个工件的加工顺序。

接着，在阶段s(s＝2,...,k)确定工件的加工顺序时，先将阶段s-1各个工件的完工时间排升序得到一个工件序列Π＝{a₁,a₂,...,a_n}和对应完工时间序列

其次，计算j＝1,2,...,n-1，n为工件总数量，将其带入式(8)求得P_j，再随机生成一个0～1之间的随机数r；判断随机数r和微调概率P_j，若r＜P_j，则交换工件a_j+1和工件a_j的位置，同时交换完工时间和的位置，直到j＝n-1并得到新的工件序列Π'，将新的工件序列Π'作为s阶段的工件序列。

最后，在阶段s按照工件序列Π'安排工件进行加工。

根据上述过程，本发明提出依概率对工件序列进行微调的解码方式具体为：

步骤1：根据给定的工件序列确定第一阶段中各个工件的机器选择和各个机器上工件的加工顺序；即根据领飞鸟或者跟飞鸟确定第一阶段中各个工件的机器选择和各个机器上工件的加工顺序；

步骤2：第s阶段中各个工件的机器选择和各个机器上工件的加工顺序的确定遵循骤3～步骤5；s的初始值为2；

步骤3：根据各个工件在阶段s-1中的完工时间计算如前述的工件序列Π和对应完工时间序列FT；

步骤4：按照步骤4.1～步骤4.5调整工件序列Π和时间序列FT；

步骤4.1记j＝1；

步骤4.2计算其中

步骤4.3随机生成一个0～1之间的随即数r，若r＜P_j，则交换工件序列中Π的工件a_j和工件a_j+1的位置并交换时间序列FT中和的位置；否则，不更新两个相邻位置工件顺序和对应完工时间序列；

步骤4.4j＝j+1；

步骤4.5循环执行步骤4.2～步骤4.4直到j＝n-1，并记此时的工件序列为Π'；

步骤5：根据新工件序列Π'确定阶段s中各个工件的机器选择和各个机器上工件的加工顺序；

步骤6：s＝s+1；

步骤7：循环执行步骤2～步骤6直到s＝k。

即可以获得跟飞鸟个体或者领飞鸟个体的目标函数值。

从上述过程可以看出，对于同一个工件序列，由于允许了工件序列以概率形式微调，该工件序列对应的目标函数值可能不唯一，为了获得该工件序列对应的更好解，设定循环次数CIRCLE，将上述解码过程循环CIRCLE次，并记录循环过程中的最优目标函数值作为该工件序列的目标函数值。

如图5是分别采用置换解码，原始排列解码，微调排列解码方法的MBO算法对Carlier和Neron提出的大规模算例j30c5e2进行求解的收敛曲线。从收敛曲线可以看出，采用置换解码的MBO算法虽然比采用原始排列解码的MBO算法获得的解稍好，但其收敛速度最慢，其次，采用微调排列解码方法的MBO算法的收敛速度慢于采用原始排列解码的MBO算法，这是因为解码中加入了循环次数CIRCLE，但采用微调排列解码方法的MBO算法取的结果比采用原始排列解码的MBO算法求得的结果稍好，这是因为微调排列解码增加了搜索到更好解得可能性，同时，由于微调排列解码中加入了概率，算法也不易陷入局部最优。

从以上讨论可以看出，提出的微调排列解码方法是为了搜索使用原始排列解码不能得到的更好解，但是随机排列解码中加入了概率和循环次数CIRCLE，这使得采用微调排列解码方法的MBO算法求解速度变慢。

为了加快采用随机排列解码的MBO算法的收敛速度，本发明提出一种将原始排列解码和微调排列解码方法相结合的两阶段解码方法：

首先设定一个进化代数临界值GEN，在MBO算法开始运行时采用原始排列解码方法，当种群进化超过GEN代时，MBO算法开始使用微调排列解码方法，这样提高了算法的速度，又增加了MBO算法搜索到最好解的可能性。

3.3种群初始化

种群初始化需要考虑种群的多样性和种群中部分个体的质量。采用四种规则，即SPTB、NEH_LPT(λ)、bLPTB和NEH_bSPT(λ)产生种群中的四个个体，个体的编码方式为排列编码，并以原始排列解码方式对个体进行解码，获得该个体的最大完工时间，以该四个个体中最优个体(最大完工时间最小)作为领飞鸟，这保证了种群中部分个体的质量。种群中的剩余个体采用随机策略产生，且要求新产生的个体不同于当前种群中的任何个体，这保证了种群的多样性。

3.4邻域结构

设计邻域结构是为了让种群朝着所期望的方向进化。在MBO算法中，除领飞鸟外，其它所有个体的邻域解集由两部分组成，即自己产生的邻域解和前面个体未使用的邻域解。本发明采用的邻域结构基于最优插入操作和最优交换操作。

最优插入操作，即随机选择一个工件j，将j从原工件序列π中删除，得到有n-1个工件的新工件序列π'，工件j在工件序列π'中有n个可插入位置，分别计算工件j插入这些位置后的目标函数值，取目标函数值最小的情况，进而得到经过最优插入操作后的最优工件序列。

最优交换操作，即随机选择一个工件j，分别将工件j和工件序列的其他所有位置的工件交换位置，共有n-1次交换操作，计算所有交换操作执行后的目标函数值，取目标函数值最小的情况，进而得到经过最优交换操作后的最优工件序列。

在本发明中，对于每个个体，分别有0.5的概率执行最优插入操作和最优交换操作，即随机产生一个0～1的随即数r，若r<0.5，则对该个体执行最优插入操作，否则，对该个体执行最优交换操作。

3.5局部搜索

领飞鸟是种群中的最优个体，一般很难通过局部搜索操作进一步挖掘更好解，因此本发明仅对跟飞鸟进行局部搜索。

采用随机交换、前插操作、后插操作和序对交换这四种操作组合起来对跟飞鸟进行局部搜索，上述四种操作如图6所示。

(1)随机交换：随机选取序列中的两个不同的工件交换位置。

(2)前插操作：随机选取两个不同的工件，然后根据两个工件在原序列的位置，将位置靠后的工件插入到位置靠前的工件的前面。

(3)后插操作：随机选取两个不同的工件，然后根据两个工件在原序列的位置，将位置靠前的工件插入到位置靠后的工件的后面。

(4)序对交换：随机产生两个不同的工件，以这两个工件的中间位置为对称轴，依次交换这两个工件及这两个工件之间所有关于该对称轴对称的工件对。

3.6候鸟优化算法框架流程

为方便阐述，定义以下变量：PSize为种群大小，k为领飞鸟产生邻域解的数量，x为每个个体传给下一个个体的邻域解数量，G为巡回次数，PN_L为每个个体传给下一个个体的左邻域解集，PN_R为每个个体传给下一个个体的右邻域解集，flag用来标记用哪列队伍的跟飞鸟替换领飞鸟，当其等于1时，表示用左队列的第一只跟飞鸟替换领飞鸟，当其等于0时，表示用右队列的第一只跟飞鸟替换领飞鸟。

本发明解决最小化最大完工时间混合流水车间的改进候鸟优化方法流程如下：

步骤1：初始化实验参数，初始化种群；

步骤2：判断进化代数是否大于进化代数临界值，该进化代数临界值根据需求确定，若是进入步骤4，否则，进入步骤3；

步骤3：采用排列解码方式对领飞鸟个体和跟飞鸟个体进行进化获得进化后个体，并更新进化代数后进入步骤2；具体包括如下步骤：

步骤31：根据领飞鸟个体产生领飞鸟个体邻域解，并以排列解码方式获得领飞鸟个体邻域解的目标值，并以最优目标值对应的领飞鸟邻域解作为进化后领飞鸟；

步骤32：根据跟飞鸟个体和领飞鸟个体邻域解产生跟飞鸟个体邻域解，并以排列解码方式获得跟飞鸟个体邻域解的目标值，并以最优目标值对应的跟飞鸟邻域解作为进化后跟飞鸟；

步骤33：判断巡回次数是否达到巡回次数临界值，若是，用进化后跟飞鸟作为本代领飞鸟，获得进化后个体，并初始化巡回次数进入步骤2，否则，更新巡回次数并进入步骤31。

步骤4：对领飞鸟进行最优插入和最优交换操作，产生k个邻域解，用最优邻域解替换领飞鸟，剩余未使用的x个邻域解分别存入PN_L和PN_R；

步骤5至步骤7为跟飞鸟的进化步骤：

步骤5：对左队列跟飞鸟进行最优插入和最优交换操作，产生k-x个邻域解，用该k-x个邻域解和PN_L中的最优解替换该跟飞鸟，清空PN_L，剩余未使用的x个邻域解存入PN_L；

步骤6：对右队列跟飞鸟进行与步骤5的相似操作；

步骤7：分别对左右队列的跟飞鸟进行前文所述的四种局部搜索操作，若产生比该跟飞鸟更好的个体，则替换该跟飞鸟；

步骤8：若巡回次数达到巡回次数临界值，该巡回次数临界值根据实际需求确定，根据flag的值挑选左队列或者右队列中的队首跟飞鸟替换领飞鸟，并将领飞鸟移动至该队列末端，并初始化巡回次数并进入步骤9，否则，更新巡回次数，执行步骤4。

步骤9：判断进化代数是否达到进化总代数，若是，则将进化后种群中领飞鸟个体作为混合流水车间调度方案，否则，更新进化代数并进入步骤4。

4实验结果与分析

以Visual Studio2010为开发环境，以C++为编程语言，算法在Intel Core i53210M、内存为4GB的笔记本电脑上运行。候鸟优化算法相关参数有种群大小PSize，巡回次数G，领飞鸟产生邻域解数量k，每个个体传给下一个个体的邻域解数量x。种群大小PSize等于左右队列跟飞鸟数量加上领飞鸟，若种群数量太小，则初始化个体在解空间上的分布密度会太小而不利于对整个解空间的搜索，而且种群数量太小会影响种群的多样性；若种群数量太大，会造成部分个体的邻域重叠，而且种群数量过大会导致算法运行时间大大增加。巡回次数G主要影响算法的收敛速度，G较大时算法收敛速度较快，G较小时算法收敛速度较慢。k和x一般取较小的值，因为过大的k值或x值会造成算法的早熟。参考文献，并经过大量的测试，本发明IMBO算法相关参数如下：PSize＝51，G＝10，k＝3，x＝1。

解码方法中的循环次数CIRCLE、代数临界值GEN和具体的问题规模有关，经过测试，本发明这两个参数取值如下：CIRCLE＝10、GEN＝5。

4.1～4.3节对每组实例的测试均进行3次，表1～表3中的数据取3次结果中的最好值。

4.1所提解码方法的有效性

为验证所提解码方法和MBO算法的有效性，分别用采用本发明提出的两阶段解码方法的MBO算法(记为IMBO)和采用原始排列解码的MBO算法对Carlier和Neron经典算例中的24个较难的算例进行求解。算例的名称由3个字母和三个数字组成，第一个字母“j”表示工件，第二个字母“c”表示阶段，第三个字母不唯一，用来表示并行机的布局方式。第一个数字表示工件的个数，第二个数字表示阶段数，第三个数字表示该类型的第几个问题。如算例j10c5c1是10个工件，5个加工阶段，中间阶段有两台并行机，其他阶段各有三台并行机类型问题的第1个问题。表1是对比结果，其中，LB为对应算例的理论下界，即无论采用精确算法还是元启发式算法，求出的解在理论上均不会小于对应的下界。

表1两阶段排列解码和原始排列解码对比

正如上文所讨论的，提出微调排列解码方法的目的就是为了增加搜索到问题更好解的可能性。从表1可以看出，采用本发明提出的两阶段排列解码方法的MBO算法在算例j10c5c3、j10c5c6和j15c5c2上取得了比采用原始排列解码方法的MBO算法更好的结果，这验证了提出的两阶段解码方法的有效性。

为验证本发明所提方法对中大规模算例的求解效果，4.2节和4.3节分别对中大规模算例进行求解，并与相关文献中的算法进行比较，比较算法包括改进的离散人工蜂群算法(IDABC)、混合变邻域搜索(HVNS)、离散人工蜂群算法(DABC)、粒子群优化算法(PSO)和人体免疫系统算法(AIS)。这里对比算法包括两个人工蜂群算法(IDABC和DABC)，是因为文献中的IDABC算法求得的解是所有文献中的最新解；而对比文献中的DABC算法是因为本发明参考了的该篇文献的数学模型。

上述对比算法是近年来求解以最小化完工时间为目标的HFSP的典型代表。

文献中的IDABC算法分别针对雇佣蜂、跟随蜂和侦察蜂实行了不同的进化策略：雇佣蜂阶段，依次通过变异、交叉、选择操作产生更好个体。跟随蜂阶段，一种基于插入和交换操作的变邻域搜索策略被用来产生更好个体，而侦察蜂阶段，通过迭代贪婪算法(IG)来产生更好个体。

文献中的HVNS算法将化学反应(CRO)算法和分布估计(EDA)算法相结合来求解HFSP，文中提出了8种邻域结构，采用基于动能的邻域改变算法来避免陷入局部最优，采用基于EDA的全局搜索算法来引导算法搜索更具潜力的解空间。

文献中的DABC算法采用了一种混合解码方式；提出24种产生个体的启发式算法，并通过实验选择了其中四种来产生4个高质量个体作为初始种群的一部分；采用一个参数来控制雇佣蜂和跟随蜂的搜索过程使全局搜索和局部搜索达到一个平衡；提出了一种局部细化搜索算法来进一步搜索解空间。

PSO算法和AIS算法不再赘述，读者可以参考相关文献来了解算法的机制。

可以发现，上述元启发算法通过各种操作使种群朝着理想的方向进化。而本发明在种群进化中采用了最优交换和最优插入操作，采用随机交换、前插、后插和序对交换四种操作对跟飞鸟进行局部搜索。除此之外，本发明的两阶段解码方法也是与上述算法的主要不同之处。

4.2中规模算例求解

本节我们对比采用两阶段解码方法的MBO和其他文献中提出的算法对24个较难算例的求解效果，结果如表2所示。

表2 24个标准算例对比

表2是求解上述24个较难算例的结果，表中第三列为本发明采用两阶段解码方法的候鸟优化算法(IMBO)求解各算例的结果，最后七列是所有上述六种算法对各个算例的求解结果相对于对应算例下界的百分比偏差，其计算方法为其中r₁为某种算法对某算例的求解结果，r₂为对应算例的下界值。

从表2可以看出，在解的质量上，IMBO对24个较难算例的求解结果均达到了目前最优解，并且从整体上来看，IMBO求解的目前最优解的个数多于IDABC、HVNS和AIS，因此，本发明提出的基于两阶段解码的改进候鸟优化方法(IMBO)在求解中等规模HFSP问题上有良好的性能。

4.3大规模算例求解

为了进一步验证IMBO求解大规模HFSP问题的有效性，用IMBO对10个大规模标准算例进行求解，结果如表3所示。从表3可以看出，与目前最好解相比，虽然IMBO对算例j30c5e3的求解结果差于IDABC算法的求解结果，但IMBO算法刷新了算例j30c5e6的解，并且从整体上来看，IMBO求出了10个算例中的9个目前最好解，IDABC求出了9个，HVNS求出了3个，DABC求出了3个，PSO求出了1个，AIS求出了0个，因此，可以说IMBO求出的目前最优解的个数多于HVNS、DABC、PSO和AIS算法，证明了本申请提出的基于两阶段解码的改进候鸟优化方法(IMBO)在求解大规模HFSP问题上具有良好的性能。图7为算例j30c5e6的甘特图。

表3 10个大规模算例对比

综上，本发明提出的算法对中大规模算例的求解具有良好的效果，一方面是因为，MBO算法作为一种新兴的元启发算法，基于候鸟飞行过程中V型队列能够减少能量损耗这一自然现象，其本身具有可行性；另一方面，是因为算法的具体实现：首先，最优插入操作和最优交换操作是搜索比较彻底的邻域结构，在一个工件序列中，我们随机选择一个工件，经过最优插入或最优交换操作，这个工件被安排在了该工件序列中的最佳位置，可以说，新形成的工件序列是原始工件序列的邻域集中较好的个体；其次，交换、前插、后插和序对交换这四种操作，进一步对跟飞鸟进行局部搜索，增加了获得更好个体的可能性；最后，本发明提出的两阶段解码方法对本发明算法的有效性也有着巨大的贡献。对于一个给定的工件序列，不同的解码方法求得的目标值自然不同，因此解码方法的重要性可想而知。基于先到先加工的原始排列解码方法，符合人类的认知思维，具有很好的解码效果。但正如3.2节所举例子一样，对于在阶段s完工时间有先后顺序的两个工件，由于其在阶段s+1的加工时间不同，按照先到先加工规则在阶段s+1先安排完工时间早的工件不一定能够获得问题的最好解。除此之外，已经安排的工件影响着后面未安排的工件，即使是细小的差别，也会对整个序列所代表的目标值产生影响，而本发明两阶段的解码方法允许这种细小差别的存在，因此增加了获得更好解的可能性。

本发明将候鸟优化算法用于求解以最小化完工时间为目标的混合流水车间调度问题。根据混合流水车间调度问题的特点，基于原始排列解码方法，将一种概率模型与原始排列解码方法相结合，提出了一种微调排列解码方法，微调排列解码方法不严格按照原始排列解码方法中的先到先加工原则，这增加了搜索到更好解的可能性；为了加快采用微调排列解码方法的MBO算法的收敛速度，将原始排列解码方法和微调排列解码方法相结合，进而提出一种两阶段解码方法。然后给出了采用两阶段解码方法的MBO算法，通过对24个较难算例和10个大规模算例进行求解，并与其他求解相同问题的元启发式算法对比，验证了本发明所提出的采用两阶段解码方法的候鸟优化算法的有效性。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。