基于改进人工蜂群算法的柔性作业车间调度*

王玉芳，马铭阳，葛嘉荣，缪 昇

(南京信息工程大学 a.江苏省大气环境与装备技术协同创新中心；b.自动化学院;c.江苏省大数据分析技术重点实验室，南京 210044)

0 引言

上世纪90年代，Brucker P[1]首次提出柔性作业车间调度问题 (Flexible Job Shop Problem, FJSP) 的概念。柔性作业车间调度问题是传统作业车间调度的扩展，突破了资源唯一性限制，每道工序可在多台不同的机器上加工，从而使作业车间调度问题更加贴合实际生产，所以一直是国内外的研究热点。

黄海松等[2]提出一种改进的模拟退火的方法解决柔性调度问题，采用个体调换和局部颠倒两种不同的搜索方式，避免算法陷入“早熟”。靳彬锋等[3]提出一种模拟退火结合遗传算子的混合算法，采用拉普拉斯交叉算子和逆转变异，结合模拟退火的局部搜索能力，提高问题的求解速度与质量。近年来，因具有搜索速度快，参数少，鲁棒性强等特点[4-6]，人工蜂群(Artificial Bee Colony，ABC)算法也应用到调度问题求解中。陈少等[7]在ABC算法中引入了相似度概念对种群进行分类，采用不同的搜索策略，观察蜂选择操作用锦标赛代替轮盘赌改善算法过早收敛现象。田野等[8]提出一种离散的ABC算法，采用自适应变异策略降低早熟收敛的可能性。Leila Asadzadeh[9]提出的并行ABC采用动态迁移策略与其他种群进行交流，结果与其他算法相比，算法的收敛速度较快。Arit Thammano等[10]提出混合ABC算法，采用迭代搜索和分散搜索进行局部搜索，利用模拟退火算法跳出局部最优解，验证结果表明该算法能够找到最优解或近似最优解。针对ABC算法局部搜索能力弱，容易陷入局部最优的缺陷[11-13]，上述研究进行了改进，并取得了阶段性成果。但是，算法跳出局部最优能力尚存较大改进空间。

本文提出一种改进ABC算法，通过改进初始解的生成方法及三种蜜蜂的操作，提高算法的寻优能力和鲁棒性，改善算法陷入局部最优的问题。

1 问题描述

柔性作业车间调度问题描述如下：有m(M1,M2,...,Mm)台机器处理n(J1,J2,...,Jn)个工件，每个工件有若干道工序，Oij表示工件i的第j道工序，每道工序可以在不同机器上进行加工，且在不同的机器上的加工时间是不相同的。根据资源选择条件限制，柔性作业车间调度问题分为完全柔性作业车间调度问题和部分柔性作业车间调度问题，完全柔性作业车间调度问题中每一个工件的任意一道工序可以选择车间中任意机器加工；而部分柔性作业车间调度问题至少存在一道工序只能选择车间部分机器进行加工。两种类型如表1和表2所示，这是一个包括3个工件、3台机器的加工时间表，表中数据表示工序在机器上的加工时间，“—”表示工序不能在该机器上加工。

表1 完全柔性作业车间调度问题实例

表2 部分柔性作业车间调度问题实例

调度目标是通过为各工序选择合适的机器进行加工以及调整各个机器上工序加工的先后顺序来使最大完成时间最小。本文中的时间均为抽象的单位时间，此外，在加工过程中还需要满足下列的约束条件：

(1) 任意工件都可以从零时刻开始被处理；

(2) 同一时间同一台机器上只可以处理一个工件；

(3) 同一个工件的同一道工序在同一时间只能被一台机器处理，直到该工序处理完成；

(4) 同一个工件的工序之间有先后顺序约束，但是不同工件的工序没有先后顺序约束；

(5) 不同的工件之间没有先后顺序的约束。

定义如下数学符号用于问题的数学描述：

n：工件总数。

m：机器总数。

i：工件序号，i=1,2,3,...,n。

h：机器序号，h=1,2,3,...,m。

ei：第i个工件的工序数。

j：第i个工件的工序号，j=1,2,3,...,ei。

Oij：第i个工件的第j道工序。

Oijh：第i个工件的第j道工序在机器Mh上加工。

tijh： 第i个工件的第j道工序在机器Mh上加工所需时间。

sij：第i个工件的第j道工序加工开始时间。

cij：第i个工件的第j道工序加工完成时间。

K：一个特别大的正数。

Ci：工件Ji的完工时间。

Cmax：最大完成时间。

目标函数及约束条件如下：

f=min{maxCi}

(1)

s.t.

ci0=0

(2)

sij+xijh×tijh≤cij

(3)

ci(j-1)≤sij

(4)

cij≤Cmax

(5)

sij+tijh≤skl+K(1-yijhkl)

(6)

ci(j-1)≤sij+K(1-yijhkj)

(7)

(8)

sij≥0,cij≥0

(9)

其中，式(1)表示本文所求的目标函数：最小化最短完成时间；式(2)表示虚拟的第零道工序完工时间为零；式(3)和式(4)表示同一个工件包含的工序必须按照先后顺序处理；式(5)表示任意工序的完成时间不超过总的完成时间；式(6)和式(7)表示在某一时刻的一台机器上只允许处理一道工序；式(8)表示在某一时刻同一道工序只能在一台机器上处理；式(9)表示任意工序的开始时间和完成时间都是非负的，且任意工件都可以从0时刻开始加工。

2 改进的ABC算法

2005年，Karaboga D[14]在总结了前人的研究成果之后，提出了ABC算法。该算法模型主要包含蜜源和蜜蜂两大要素。蜜源相当于需解决优化问题的可行解；蜜蜂分为雇佣蜂、观察蜂和侦查蜂三种类别。雇佣蜂与蜜源的位置相对应，所有雇佣蜂的数量与蜜源相等，且具有记忆功能，能够把搜索到的蜜源信息存储起来，根据蜜源的好坏，按一定的概率分享给观察蜂。观察蜂得到雇佣蜂分享的信息之后，选择满意的蜜源信息进行跟随，观察蜂的数量等同于雇佣蜂。侦查蜂则按一定规则搜索新的蜜源位置。三种蜜蜂之间可以互相转换，这是蜂群算法特有的机制，其转换关系如图1所示。

图1 雇佣蜂、观察蜂和侦查蜂转换关系图

2.1 编码与解码

标准ABC算法是处理连续解空间的启发式算法，无法直接应用于柔性作业车间调度这种离散问题，因此针对该问题需进行合适的编码。考虑此问题存在两个相应的子问题，即作业在机器上的加工顺序和加工工序选择机器问题，所以采用双层编码的形式。第一层是工序层，用来确定工序的加工顺序；第二层是机器层，用来表示各工序选择的机器。每一层的长度和工序的总数相同。

工序串编码如图2所示，假设工序串为[3 1 2 1 2 2]，则第一个3表示工件3的第一道工序，同理，第一个1表示工件1的第一道工序，而在第四个位置上的1则表示工件1的第二道工序；每个数字出现的次数等于对应的该道工件的工序数。所以图2中工序串的加工顺序O31→O11→O21→O12→O22→O23。

图2 工序串编码示意图

机器串编码如图3所示，机器串编码是从左到右按工件序号以及各工件中工序的顺序来排序。第一个位置上的数字2表示该工序选择其可选机器集中的第二个机器M2进行加工，同理第五个位置上的数字1表示该位置的工序选择其可选机器加工集的第一个机器M3进行加工；与图2的工序串对应起来即工序O11在机器M2上加工，工序O23在机器M3上加工。

图3 机器串编码示意图

2.2 种群初始化

种群初始化方法对算法的求解质量和求解速度有很大的影响，若完全使用随机方法生成初始种群，则初始解优劣不一，随机性过强，初始解的质量很难得到保障，这势必会影响搜索最优解的速度，导致需要以增加迭代次数和种群大小为代价来获得最优解，进而增加优化时间。为了避免上述问题，本文采用随机选择和按规则选择相结合的方法实现种群初始化。

在机器串编码中，采用三种初始解生成规则，全局选择(global selection, GS)、局部选择(local selection, LS)和随机选择(random selection, RS)[15]。GS和LS能够尽可能地平衡每台机器上的负荷，提高机器的利用率，在一定程度上减小初始解的最大完工时间；而具有强随机性的随机选择可以取到解空间中的任意解，保证初始解的多样性。

在工序串编码中，本文采用剩余负荷最大规则(maximum residual load, MRL)、加工时间最短优先(shortest process time, SPT)规则和随机选择(random selection, RS)三种规则。MRL把各个工件的剩余加工时间统计排序，优先加工剩余加工时间最长的工件；SPT优先处理剩余加工时间短的工件；RS把各个工序进行随机排序选择。

机器串生成规则GS/LS/RS的选择概率分别为30%、30%和40%，工序串的生成规则MRL/SPT/RS的选择概率分别为30%、30%和40%。

2.3 雇佣蜂操作

针对柔性作业车间调度问题，对传统的雇佣蜂操作进行改进，采用两种交叉方法，第一种是在工序串上进行IPOX交叉[16]，第二种在机器串上进行多点交叉的操作。这两种方法不会产生非法解，同时还能把父代个体中的优良基因传递到下一代。

(1)IPOX交叉

首先通过初始解求得目标函数值，然后计算适应度值，选取适应度值最大的工序串为全局最优解。具体操作过程如下：

步骤1：从种群中选择一条工序串作为父代X1，生成一个0～1之间的随机数，若随机数小于0.5，选择全局最优解为X2；若随机数在0.5～1之间，则种群中选出另一条工序串作为X2(即X2不能与X1相同)；

步骤2：把n个工件J1,J2,...,Jn分为两个互补的工件集R1和R2；

步骤3：把父代X1中包含在R1工件集中的工序号按照在X1中的位置复制到子代C1中，把X2中包含在R2工件集中的工序按照原顺序插入到子代C1的空缺处；

步骤4：把父代X2中包含在R2工件集中的工序号按照在X2中的位置复制到子代C2中，把X1中包含在R1工件集中的工序按照原顺序插入到子代C2的空缺处；

步骤5：计算子代C1和C2的适应度值，选择适应度值较大的子代作为交叉后的子代；

步骤6：计算子代染色体适应度值，若其大于父代X1的适应度值则替换，否则不改变。

(2)多点交叉操作

多点交叉作用于机器串的交叉操作，因为交叉的是同一工序的可用机器，所以不会产生非法解，具体步骤如下：

步骤1：选则与父代X1工序串对应的机器串作为机器串父代P1，选则与父代X2工序串对应的机器串作为机器串父代P2；

步骤2：随机生成一个由0和1组成的长度与机器串相等的二进制串；

步骤3：把父代P1中与二进制串中与1位置相同的机器号复制到子代S1的相同位置；把父代P2中与二进制串中与0位置相同的机器号复制到子代S1的相同位置；

步骤4：把父代P2中与二进制串中与1位置相同的机器号复制到子代S2的相同位置；把父代P1中与二进制串中与0位置相同的机器号复制到子代S2的相同位置；

步骤5：计算子代S1和S2的适应度值，选择适应度值大的作为机器串多点交叉后的子代；

步骤6：计算子代染色体适应度值，若其大于父代P1的染色体的适应度值则替换，否则不改变。

2.4 观察蜂操作

观察蜂采用轮盘赌[17]的选择方式，根据蜜源的适应度值选择蜜源的位置，蜜源的适应度值越高，选择该蜜源位置的概率越大。依据式(10)计算选择概率，fitw是第w个解对应的适应度值，D为蜜源的数量，等于种群NP的一半，如式(11)：

(10)

(11)

蜜源的适应度值按式(12)计算，objw是蜜源w的目标值：

fitw=1/(1+objw)

(12)

工序串采用变换步长策略对选择的蜜源位置附近进行搜索，大步长交换可行解中多对工序的顺序，易产生显著变化，增强全局搜索能力，避免陷入局部最优；而小步长交换可行解中一对工序的顺序，这种变化很小，适合在当前解空间进行更深一步地搜索，加快算法向最优解靠近。对于变步长策略来说，需要设定一个阈值，使大步长与小步长有机结合，当搜索次数小于阈值时进行小步长搜索，反之进行大步长搜索，同时把搜索次数变量清零；计算适应度值，用贪婪策略选择适应度高的个体，以保证种群能够保留精英个体。

对工序串进行插入变异，从工序串中选择任意一道工序插入到工序串中任意位置，其他工序按原有顺序排序，计算适应度值，用贪婪策略保留最优解；对机器串进行变异操作，任意选取一道工序，在其可选机器集中随机选择一台机器进行变异，同时计算适应度值，用贪婪策略选择适应度高的染色体保留到下一代种群中。

2.5 侦查蜂操作

在标准ABC算法中，若雇佣蜂在同一个蜜源的适应度值超过limit次(最大搜索次数)没有改进，雇佣蜂转换为侦查蜂，随机产生一个新的解，但是每次只有一只雇佣蜂转换为侦查蜂，随机生成的一个新解对于种群的影响较小，不利于算法跳出局部最优解。因此，本文对侦查蜂进行改进，若Y个蜜源经过limit次而没有改进，则采用本文2.2节的种群初始化方法生成Y个新蜜源，通过增加侦查蜂的数量来保持种群的多样性，利于提高算法的全局搜索能力。

2.6 算法流程

根据上述改进策略，结合柔性作业车间调度问题，提出改进的ABC算法，如图4所示。

主要包括以下步骤：

步骤1：建立柔性作业车间调度模型；

步骤2：确定调度的约束条件；

步骤3：初始化种群以及设置参数；

步骤4：计算适应度值，雇佣蜂进行IPOX交叉和多点交叉操作；

步骤5：计算各蜜源适应度值，并且计算观察蜂选择跟随各雇佣蜂的概率；

步骤6：观察蜂采用变步长搜索策略，并且进行变异操作；

步骤7：判断蜜源是否达到最大搜索次数，若满足条件则雇佣蜂转换为侦查蜂，搜索新的蜜源，否则到步骤8；

步骤8：判断算法是否达到最大迭代次数，如果是则算法结束；如果未达到最大迭代次数，则跳转到步骤4。

图4 改进的ABC算法流程图

3 实验分析

为了验证所提算法在求解柔性作业车间调度问题的有效性，本文与文献[18-19]和文献[7]提出的算法性能进行比较，均采用Kacem标准测试集[18]中的8×8和10×10两个算例来测试算法的性能。8×8是8个工件在8台机器上加工的部分柔性作业车间调度问题算例，10×10是10个工件在10台机器上加工的完全柔性作业车间调度问题算例。

本文改进的ABC算法采用Matlab编程实现，程序在Windows 10系统，主频为3.4 GHz，内存为8 G的个人电脑上运行。对于上述两个算例，算法参数设置如下：种群NP=200；最大迭代次数maxCycle=100；最大搜索次数limit=20； 搜索阈值threshold=5；将算法运行10次，并与文献[18]中Kacem所得到的结果、文献[19]所提的IGA算法和文献[7]中的改进ABC算法的运行结果相比较，比较结果如表3所示(Cmax表示10次运行中所得的最优值，Aver表示10 次运行的平均值)。

表3 四种算法结果比较

从表1中可以看出本文算法在8×8和10×10算例中均能找到最优解，说明改进ABC算法具有较好的寻优能力。值得说明的是，算法10次运行找到最优解的平均值更小，可以看出算法中的改进策略是有效的，变步长策略既保证了局部搜索的能力，又增强了算法全局搜索能力，有效避免启发式算法易陷入局部最优的局限性，算法收敛性和鲁棒性好。

8×8问题和10×10问题的最优解甘特图如图5、图6所示，横坐标为完工时间，是抽象时间单位，纵坐标为机器号；图7为改进ABC算法的进化曲线，横坐标为迭代次数，纵坐标为完成时间。

图5 8×8最优解甘特图

图6 10×10最优解甘特图

图7 两个算例的进化曲线

从算例的进化曲线中可以看出种群均值时而会产生退化，这是由于侦查蜂数量增多，产生新的初始解导致种群均值增大，但是在种群均值退化的同时，全局最优解曲线也会向下降，找到更好的全局最优解，而且从算法收敛曲线可以看到退化只是暂时的，总体趋势还是向最优解靠近，说明增加侦查蜂数量可以有效地使算法跳出局部最优。

4 结论

针对柔性作业车间调度问题，以最大完工时间最小为目标，提出了改进的ABC算法，种群的初始化采用随机选择与按规则选择相结合的方法，减少了生成过差初始解的可能，同时避免了因依赖按规则选择产生初始解导致的算法早熟。算法在雇佣蜂操作中通过IPOX交叉策略来对蜜源进行搜索，并提出全局最优解或者任意解与当前蜜源进行交叉操作，提高了算法的收敛速度；在观察蜂阶段采用变步长策略提高算法的全局搜索能力，提升算法跳出局部最优的可能性；为了保持种群的多样性，增加了侦查蜂的数量。通过实验算例验证了改进算法突出的寻优能力和收敛性。后续将研究绿色柔性作业车间调度问题，响应国家提出的绿色制造号召。