改进多邻域候鸟优化算法的柔性作业车间调度研究

杜凌浩，向凤红

(昆明理工大学 信息工程与自动化学院，昆明 650500)

1 引言

近年来，我国高端制造业逐步兴起，柔性作业车间调度问题(Flexible job shop scheduling problem，FJSP)考虑了机器柔性，更加适用于当前实际生产情况而越来越受到关注[1]。

因为采用精确算法在解决FJSP大规模算例时较为困难，近年来大多数学者将解决方案放在了智能优化算法上。文献[2]提出了基于协同优化算法的多群体协同遗传算法对FJSP的最大完工时间最小问题进行了研究。文献[3]将灰狼算法与遗传算法相结合研究了FJSP问题。文献[4-6]分别将蚱蜢优化算法、蜻蜓算法、花朵授粉算法进行改进，并将其应用在了FJSP问题上。虽然目前学者已经使用了很多经典的智能优化算法来解决FJSP问题，但还需要一些更具竞争力的算法来获得更好的优化结果。

候鸟优化算法(migrating birds optimization，MBO)是2012年由Duman等[7]受到候鸟迁徙过程中领飞鸟和跟飞鸟的行为而提出的一种新型智能算法。由于其求解问题的优越性，许多学者将其应用在了调度问题。文献[8]将候鸟优化算法与分布估计算法结合研究了阻塞批量流水车间调度问题。文献[9]对候鸟优化算法的邻域结构进行改进，并提出一种随机迭代排列解码方法应用在了混合流水车间调度问题。文献[10]将基于迭代贪婪算法、贪婪随机自适应搜索、路径重新链接技术和局部搜索与候鸟优化算法相结合研究了阻塞混合流水车间调度问题。文献[11]采用候鸟优化算法对置换流水车间调度问题进行了研究。但目前主要集中在流水车间调度问题，少有文献使用MBO算法研究了柔性作业车间调度问题。文献[12]和文献[13]采用变邻域搜索策略与候鸟优化算法相结合，研究了FJSP问题。但对算法的改进，只增加了算法的局部搜索能力，解空间的探索范围和全局性还有待提升。因此，本文提出一种改进的多邻域候鸟优化算法来解决FJSP问题。具体地，采用随机和最优加工时间策略初始化种群，并采用两段式编码，以插入和变异的方式构造了6种不同的邻域结构，采用联合邻域搜索策略扩大解空间的搜索范围。设计二次种内竞争策略来保证优秀个体在种群能够发挥更好的引导作用；最后设计了种间协同策略来解决MBO算法特殊的共享机制而容易导致算法容易陷入局部最优的问题。通过实例和基准算例进行测试，与其他算法进行对比验证了算法的有效性。

2 柔性作业车间问题

2.1 问题描述

柔性作业车间调度问题描述如下：有n个工件(J1,J2, …,Jn)需要在m台机器(M1,M2, …,Mm)上加工。其中每个工件含有一道或者多道工序，每个工件的工序数可以不同，且每道工序的加工顺序是固定的；每道工序可以选择在不同的机器上加工，加工时间取决于所选择的机器。一个工件同一时刻只能被一台机器加工；一台机器同一时刻只能加工同一工件的同一工序；工件一旦开始加工就不能中断；各工件之间具有相同的优先级；同一工件存在加工顺序，不同工件工序相互独立；开始前，所有工件机器应该准备就绪。本文出现的符号定义如表1所示。

表1 数学符号及符号定义

2.2 模型建立

本文以最大完工时间为优化目标，其中f为完工时间，表达式如下所示：

f=min(max(Cj)), 1≤j≤n

(1)

Sjh+xxjh×pijh≤Cjh,i=1,2,3,…,m;

j=1,2,3,…,n;h=1,2,3,…,hj

(2)

Cjh≤Sj(h+1),j=1,2,3,…,n;

h=1,2,3,…,hj-1

(3)

Cjhj≤Cmax,j=1,2,3,…,n

(4)

Sjh+pijh≤Skl+L(1-yijhkl),j=0,1,2,3,…,n;

k=1,2,3,…,n;h=1,2,3,…,hj;

l=1,2,3,…,hk;i=1,2,3,…,m

(5)

Cjh≤Sj(h+1)+L(1-yiklj(h+1)),j=1,2,3…,n;

k=0,1,2,3,…,n;h=1,2,3,…,hj-1;

l=1,2,3,…,hk;i=1,2,3,…,m

(6)

(7)

Sjh≥0,Cjh≥0,

j=0,1,2,…,n;h=1,2,3,…,hj

(8)

式(2)和式(3)表示每个工件工序的先后顺序约束；式(4)表示单个工件的完工时间小于总完工时间；式(5)和式(6)表示同一台机器的在某一时刻不能加工多道工序；式(7)表示机器约束，即不能有多台机器在某一时刻加工同一个工序；式(8)表示各个参数变量是正数。

3 改进候鸟优化算法解决FJSP问题

3.1 基本候鸟优化算法

基本候鸟算法详细步骤如下：

步骤1算法初始化。算法初始化分为两部分，第一部分是设置MBO的参数，包括产生初始解的个数，邻域解的数量，共享解的数量以及巡回次数。第二个部分是生成初始种群，算法的性能受初始种群的影响。在基本MBO中，采用随机生成可行解的方式生成初始解。在所有可行解s当中，选择一个解作为领飞鸟，其余可行解作为跟飞鸟，跟飞鸟被平均分为2组，分别放到左队列和右队列中。其中各有(s-1)/2个解。

步骤2领飞鸟进化。通过邻域结构生成k个邻域解，将邻域解中的最优解与领飞鸟进行对比，若最优解优于当前领飞鸟的解，则替换领飞鸟；之后将未使用的nx个邻域解给跟飞鸟使用。

步骤3跟飞鸟进化。根据邻域结构，会产生k-nx个邻域，在新产生的k-nx个邻域和由前面候鸟产生的未使用的nx个邻域解中找到最好的解，若最优解优于当前解，则替换跟飞鸟，同时将本次未使用到的nx个最好解给下一只鸟使用。

步骤4领飞鸟替换。判断有没有达到巡回次数，若未达到巡回次数，则转到步骤二，若达到巡回次数，领飞鸟移动到队伍的末端，在领飞鸟后面的鸟(左边或右边)成为新的领飞鸟。

3.2 编码和解码

本文采用两段式编码：机器编码，表示将工序分配给对应的机器；工序编码，表示工序被机器加工的顺序。

如图1所表示的是某一染色体的编码。机器编码层依次按照工件顺序进行加工。机器编码的数字表示当前工序在对应机器集中选择的机器，如图1的第一个数字2表示该工序选择在可加工机器集中第二台机器加工，即O12选择在机器集中的第二台机器M3上加工。第二个数字1表示选择O32在机器集中的第一台机器M2上加工。工序编码层的数字表示工件号，数字第几次出现就表示该工件的第几道工序，如上图对应所示。解码时首先通过工序编码获得当前工序的相关信息，然后在机器编码中找到对应的加工机器，从而确定当前工序的加工时间，然后依次对工序编码进行安排得到完整的调度解，绘制甘特图。

图1 染色体编码示意图Fig.1 Chromosome coding diagram

3.3 种群初始化

为了获得较好的初始解，本文采用随机生成初始种群，同时针对FJSP在不同机器有不同加工时间的特点，提出最优加工时间策略来对种群进行初始化。最优加工时间策略即为每道工序分配机器时，选择机器加工时间最小的机器，进一步减少机器的加工时间，2种方式生成种群的比例为1∶1。

3.4 邻域结构

MBO算法通过对自身邻域解的搜索来引导种群进化，为扩大解空间的搜索范围，结合本文的编码方式，设计了6种不同的邻域结构产生邻域解。

邻域结构1：基于机器编码的单点变异，在机器编码中随机选择一个基因，同时在该工序的可选机器集里选择一个与它不同的机器替换原基因。

邻域结构2：基于工序编码的互换变异，随机选择2个工件的工序，交换2个不同基因在染色体中的位置。

邻域结构3：将基于机器编码的单点变异与基于工序编码的互换变异相结合的方式(图2)。

图2 邻域结构3示意图 Fig.2 Schematic diagram of neighborhood structure 3

邻域结构4：基于机器编码的前插操作，随机生成r1，r2，且r1

邻域结构5：基于工序编码的前插操作，随机生成r1，r2，且r1

邻域结构6：将基于机器编码的前插操作与基于工序编码的前插操作行相结合的方式(图3)。

图3 邻域结构6示意图 Fig.3 Schematic diagram of neighborhood structure 6

3.5 联合邻域搜索策略

在该策略中，多种不同邻域共同引导种群进化。左队列的个体采用前3种基于变异的邻域结构；右队列的个体采用后3种基于插入的邻域结构。对于领飞鸟，在进化巡回过程中可以任意选择6种不同的邻域结构来构造邻域解。种群的进化过程中，左右跟飞鸟可以得到多种不同的邻域组合方式，使多种不同的邻域结构得到充分利用。

3.6 跟飞鸟二次种内竞争策略

跟飞鸟的进化依赖于前一只鸟共享的邻域解，前鸟的优劣影响着算法的进化，在传统的MBO中，领飞鸟的替换是轮换式的，这就导致优秀的个体可能需要很长一段时间才能拥有成为领飞鸟的机会，从而导致鸟群在进化过程中很难把优秀的邻域解传递给下一只鸟，如果较差的解排在队列前面，则后续跟飞鸟获得的共享解在进化过程中的作用将会不明显。为了让较好的个体能够更好的发挥对下一只鸟的引导作用，本文借鉴了文献[14]提出的一种竞争策略来保证适应度较好的鸟处于队伍前列。但文献[14]提出的竞争策略只针对于前后跟飞鸟的小范围竞争，无法对全局的跟飞鸟做出相应的调整，因此本文提出一种新的竞争策略，即在跟飞鸟每次巡回结束之后分别对左右种群以适应度从小到大的方式进行重排列。同时为增强该策略对种群进化的影响，采用跟飞鸟二次种内竞争策略，即在达到巡回次数以后再次采用竞争策略来保证较优个体处于队列前面，增加优良跟飞鸟成为领飞鸟的机会。

3.7 种间协同策略

MBO算法中基于邻域的搜索方式使算法具备极强的局部搜索能力，但由于其特殊的共享机制，容易导致种群陷入局部最优。结合文献[15]的研究发现，种群内多次执行交换操作能够增加种群的多样性，有效避免算法陷入局部最优。考虑到候鸟优化算法特殊的V字型结构，本文提出种间协同策略避免算法陷入局部最优，引导算法探索更优秀的解空间。采用遗传算法中的交叉操作来实现该理论，即采用基于机器编码的单点交叉和基于工序编码的POX交叉。不同于传统遗传算法，在本文算法中，父代母代分别来自左右跟飞鸟种群。

基于机器编码的单点交叉如图4所示，随机选择机器编码的任意位置，然后交换该位置右侧部分的基因。若某基因出现不可行解，则保持当前基因的原有机器编码不变。P1代表来自左队列的候鸟，P2代表来自右队列的候鸟，C1和C2表示采用基于机器编码的单点变异之后，而产生的新工序编码。

图4 基于机器编码的单点交叉示意图 Fig.4 Single point crossing based on machine coding

POX交叉与其他交叉操作相比是效果最好的操作之一，它能够有效的保证任意工序之间的约束关系，其主要思想为把总工件集分为2个不同的子工件集J1和J2，分别在左右队列中找到J1或J2中所有工件的位置，本文选择J2工件集对应的基因。将左右队列包含J2工件位置的基因互换得到新的个体，如图5所示，表示的是5个工件共15道工序的工件的调度解。P1代表左队列的候鸟，P2代表右队列的解，J2表示当前的工件集，C1和C2表示通过POX交叉以后新的工序编码(图5)。

图5 基于工序编码的pox交叉示意图 Fig.5 POX cross based on process coding

3.8 IMBO算法流程

IMBO算法流程如图6所示。

图6 IMMBO流程框图 Fig.6 IMMBO flow diagram

4 仿真测试与分析

本文采用Matlab 2019a编程，并在Windows 10系统、内存为8GB、处理器为[Intel]i5-4200H、64位操作系统的计算机上运行。为验证算法的有效性，选择Kacem算例和Brandimate算例[16-17]进行仿真，同时为保证算法的有效性，采用3个文章实例进行验证。文献[10]和文献[11]的参数设置，经过大量测试，本文设置参数如下，种群规模size=51，领飞鸟和跟飞鸟产生邻域解的数量nk=5，共享邻域解nx的个数为2，巡回次数G=5，迭代次数为200。

4.1 基准算例仿真实验

从表2可以看出，本文算法能够获得最多的最优解，并且RPD的平均值也是最低的，因此本文提出的IMMBO算法具有一定的优越性。

表2 Brandimate和Kacem算例对比

4.2 联合邻域搜索验证实验

然后对联合邻域搜索的有效性进行验证，这里采用单一邻域结构与采用多种邻域结构联合搜索的方式进行验证。本文选择邻域结构1和4来进行验证。为保证验证实验的合理性，领飞鸟采用单一邻域结构，选择邻域结构1，跟飞鸟采用多种不同邻域结构。其中MBO1代表左右跟飞鸟都采用邻域结构1，MBO4代表左右跟飞鸟都采用邻域结构4，MBO14代表左右跟飞鸟分别采用邻域结构1和4。每个算法分别针对Brandimate的10个算例独立运行10次，取平均值进行验证。从表3的数据中可以看出采用联合邻域搜索MBO14的算法明显优于只采用单一邻域结构的MBO1的MBO2算法。

表3 联合邻域搜索验证

4.3 不同候鸟优化算法对比实验

最后为进一步验证本文改进候鸟优化算法与使用其他不同方法改进候鸟优化算法的优越性，选择文献[12]的HMBO1算法和文献[13]的MBOA和VNS_MBOA算法，采用Brandimarte算例在相同条件下运行10次取平均值进行比较。结果如表4所示，可以看出除少部分算例本文算法未获得较优的值外，其余算例都获得优于其他方法的解，可以看出IMMBO优于其余算法。

4.4 实例仿真

实例1：实例1包括3个工件，6台机器，共15道工序，实验数据来自文献[22]，文献[22]采用PST层次结构的遗传算法和文献[23]采用鲸鱼群优化算法得到的最优解为134。文献[24]采用改进的离散粒子群算法得到的最优解是129。利用IMMBO算法对实例进行优化求解，得到的最优解是116，相比于文献[22]和文献[23]，最优加工时间缩短了18，相比于文献[24],最优加工时间缩短了13，对应的甘特图如图7所示。

表4 4种候鸟优化算法对比结果

图7 实例1甘特图 Fig.7 Example 1 Gantt diagram

实例2：实例2包括10个工件，8台机器，共35道工序，实验数据来自文献[25]，文献[26]和文献[27]对蝙蝠算法进行改进分别获得了82和79的最小完工时间，采用IMMBO算法得到的最优解为69，相比于文献[26]和文献[27]，最优加工时间分别缩短了13和10，其甘特图如图8。

图8 实例2甘特图 Fig.8 Example 2 Gantt diagram

实例3：实例3包括6个工件，8台机器，共26道工序，实验数据来自于文献[28]，其中文献[29]采用的量子粒子群算法得到的最优解为67，文献[28]采用双层粒子群优化算法得到的最优解为60，文献[27]采用改进的蝙蝠算法得到最优解为为56，文献[30]的混合遗传蝙蝠算法得到的最优解为55，采用IMMBO算法得到的最优解为53，相比于文献[27]和文献[28]，最优加工时间分别缩短了3和7，与文献[30]和文献[24]相比，最优加工时间分别缩短了14和2，其甘特图如图9。

图9 实例3甘特图 Fig.9 Example 3 Gantt diagram

从上面3个实例可以看出IMBO都获得了比其他算法更加优良的解，说明所提算法优于其他算法，表明了算法的有效性。

5 结论

针对FJSP问题，提出了一种基于改进的多邻域候鸟优化算法。首先采用两段式编码解决FJSP的工序排序和机器选择问题；为增大解空间的搜索范围设计了6种不同的邻域结构；为扩大候鸟进化过程中前鸟对后鸟的影响作用，设计了二次种内斗争策略增强较好的个体在算法迭代过程中的效果。最后，为解决候鸟优化算法基于邻域搜索方式，容易陷入局部最优的问题，提出了种间协同策略。通过实例和标准算例测试，IMBO算法在求解FJSP问题时的有效性，下一步将对算法继续改进应用到求解多目标FJSP问题。