改进人工蜂群算法求解柔性作业车间调度问题

陈 少，吉卫喜,b，仇永涛，张国祥

(江南大学 a.机械工程学院；b.江苏省食品先进制造装备技术重点实验室，江苏 无锡 214122)

0 引言

柔性作业车间调度问题(Flexible Job Shop Problem, FJSP)[1]历年来一直是国内外研究的热点问题之一，研究已证明该类问题是典型的NP-hard问题。尽管近年来学者们已将诸如遗传算法[2]、蚁群算法[3-4]、粒子群算法[5]等人工智能算法应用到该问题上的求解上，并取得了一定的效果，但至今仍没有得出一套完全良好的解决方案，因此该问题仍具有很大的研究空间。

本文所研究的人工蜂群算法(Artificial Bee Colony, ABC)是由土耳其学者Karaboga[6]于2005年提出。该算法具有搜索速度快、精度高、参数少、鲁棒性强等优点，文献[7]也指出它与GA、PSO等算法相比，所求得的解的质量相对较好。而在车间调度问题上，近年来的ABC算法研究大多集中在流水车间的问题上[8-9]，在柔性作业车间调度问题上，田野等[10]虽有一定研究，但仍存在易陷入“早熟”收敛特性、局部搜索能力较弱、收敛速度较慢等缺陷，故该算法仍具有很大的改进空间。本文在介绍其标准算法的基础上，针对算法中三类蜜蜂的特点分别进行改进，使算法能适用于FJSP问题求解的同时，具有较快搜索速度和良好的跳出局部解的能力，最后选用标准算例求解并与其他算法结果对比证明该改进算法的有效性。

1 问题描述

FJSP问题可进行如下描述: 有n个工件，用Ji(i=1,2,…,n)表示第i个工件，每个工件之间相互独立，每个工件都有Oi道工序组成，Oij表示工件Ji的第j道加工工序。n个工件需要在m台机床上进行加工，Mk(k=1,2,…,m)表示第k台设备，每个工件的加工工序是确定的。对于每道工序Oij有一台或多台设备可进行加工，用mij表示其可选设备集，mij⊆(1,2,…,m)调度的目的就是为每道工序选择最佳的加工设备并确定每台设备上所有工序的加工顺序，使加工完所有工序的总时间最小。此外，还需满足以下约束条件：

(1)同一时间同一台设备上只能加工一个工件的某一道工序；

(2)同一时间一个工序只能在某一台设备上加工，且加工过程不可以中断直至该工序加工完成；

(3)同一工件的各工序存在先后顺序约束，但对于不同工件的各工序而言，它们相互独立；

(4)所有工件可选择的加工设备及设备相应的加工时间是确定的。

上述问题的数学描述如下：

(1)

s.t.

(2)

cij≤si(j+1),i=1,2,…,n，k=1,2,…,m

(3)

sij+cij≤saq+Y(1-yijaqk),
i,a=1,2,…,n，k=1,2,…,m,j,q=1,2,…,oi

(4)

cij≤si(j+1)+Y(1-yaqi(j+1)k),
i=1,2,…,n;k=1,2,…,m;j,q=1,2,…,oi

(5)

sij≥0且cij≥0

(6)

(7)

cij≤Cmax,i=1,2,…,n,j=1,2,…,oi

(8)

式中，Cmax为最大完工时间；Ci为工件Ji的完工时间；sij为工序Oij开始加工时间、cij为该工序完成加工时间、tijk为该工序在设备Mk上的加工时间；Y表示一个足够大的正数；Xijk和yijaqk是标志数，它们代表的含义如下：

(9)

(10)

上述公式中，式(1)表示所求问题的目标函数，即最后完工时间最小化；式(2)和式(3)表示对于同一工件的各工序之间必须按确定的工艺路线进行加工；式(4)和式(5)代表一台设备在同一时间只能加工某个工件的某一道工序；式(6)表示所有工序开始加工和结束加工时间必须大于0；式(7)表示某个工件的某道工序在同一时刻只能在一台设备上加工; 式(8)表示任何一个工序的完工时间小于或等于总工序的完工时间。

2 标准人工蜂群算法简介

人工蜂群算法源是一种基于群智能的随机搜索算法。蜂群内蜜蜂个体根据职能不同分为三类：

(1)引领蜂(employed bees)：负责发现蜜源并将信息传递给跟随蜂,所采用的搜索方式如下：

vij=xij+φij(xij-xkj)

i,k∈{1,2,3…,SN}，j∈{1,2,3,…,D}

(11)

上式中，SN表示蜜源个数，vij表示经变换后所得到的新的蜜源，xij为原蜜源，xkj是一个随机选取的一个不同于xij的蜜源。φij表示在区间[0,1]上产生的一个随机数。

(2)跟随蜂(onlooker bees)：根据引领蜂所传递蜜源丰富程度信息，依据一定的概率对蜜源进行选择，并对选择后的蜜源采用公式(11)的方式进行开发，依据的概率公式为：

(12)

其中，fiti代表对应蜜源xij的适应度值，pi则代表该蜜源被选中的概率。

(3)侦察蜂(scout bees):当一个蜜源的适应度值在给定的步骤内(定义为控制参数“limit”) 没有被提高, 则丢弃该蜜源并通过公式(13)搜索新的蜜源:

(13)

在算法中，蜜源的一个位置即表示问题的一个潜在解，而蜜源的丰富程度则对应于解的优劣(即适应度值的大小)，所以蜂群寻找高收益度蜜源的过程既是对应问题寻求最优解的过程。

3 改进ABC算法求解FJSP问题

3.1 编码与解码

这种编码方式一个编码方案就代表问题的一个可行解，且方便算法的搜索过程，既能保证编码的唯一性，解码过程也相对简单。

3.2 种群初始化

大多算法的初始种群是采用随机方法产生的。单一的随机方法具有很大的不确定性，所产生的种群有可能是较为分散的优良种群，也可能是个体间较为相似的劣质种群，难以保证初始群的质量。因此，本文采用基于混沌序列思想[11]、基于加工时间越短越优先(SPT)启发式规则和随机方法三种不同的方式共同产生工序码初始种群，保证初始解的质量。三种方式所占的比例如下所示：

初始机器码的产生则采用随机方式，即在对应工序的可用机器集中随机选择一台机器号填入机器码对应的位置上。

混沌序列思想是指通过特定的映射方式产生一组具有随机性、遍历性及规律性的序列。本文采用常用的Logistic映射，其系统方程如下：

X(k+1)=u*X(k)*[1-X(k)]
(k=0,1,2,…,n)

(14)

式中，u表示控制参数，当u=4时表示系统处于完全混沌的状态。

用混沌序列方式产生初始解步骤如下：

(1)随机产生一个在(0,1)之间的初始值X(0)；

(3)将序列中的每一个元素与工序码中元素一一对应，然后将该序列从小到大排序，并将对应位置的工序也随之排序，即得到一个工序调度方案。

例如要产生某个3个工件，每个工件有2道加工工序的工序码，用混沌序列产生初始工序码的过程如表1所示。

表1 混沌序列产生工序码过程

3.3 搜索过程的改进

标准的ABC算法的搜索方式是针对连续优化问题的，而FJSP属于离散优化问题，且考虑到ABC算法目前仍存在易陷入“早熟”的收敛特性、局部搜索能力较弱、收敛速度较慢等缺陷，因此本文提出以下改进方式。

3.3.1 引领蜂搜索过程的改进

对于一般算法的搜索过程而言，种群适应度较差时需要较大范围的邻域搜索方式以加快算法的收敛速度，而适应度值较好时则需要较小范围的邻域搜索方式来加强局部搜索能力。为实现针对不同适应度值的个体有不同的搜索范围，本文根据引入相似度φ概念，定义如下：

(15)

其中，fiti表示个体i的适应度值，fitbest表示种群中最优个体的适应度值。

根据个体相似度φ的大小，根据定义的分群比例C把种群分为当前群体中较优的先进群Q和较差的后进群P，对两个子群分别采用不同范围的搜索方式，如下所示。

同时，公式(11)的邻域搜索方式是针对连续问题优化的搜索，根据两个子群的特点，本文参考遗传算法相关搜索策略，对公式(11)进行变换，分别定义了针对两个子群工序码的两种不同搜索方式：

vij=xij⊕insert(swap(xij))

(16)

vij=xij⊕reverse(xij·cross·xkj)

(17)

其中，"swap"表示交换操作，即在工序码任意选取两个位置，然后交换这两个位置上的对应的工序；"insert"表示插入操作，即在工序码中随机选取一个位置的工序，将该工序插到另一任意位置上；"cross"表示交叉操作，在选取的两个工序码之间执行交叉操作；"reverse"表示反序操作，表示随机选取两个位置，将两个位置之间的所有元素进行倒序排列。根据文献[12]的研究表明，基于工序编码交叉(Precedence Preserving Orderbased Crossover, POX)的交叉方式能较好的继承父代的特性，因此本文"cross"步骤中采用该交叉方式。

同时文献[12]也指出，在邻域搜索的范围上，交叉≻反转≻交换≻插入，根据之前所说的分群目标，本文中先进群Q采用公式(16)的搜索方式，后进群P采用公式(17)的搜索方式。根据机器码的编码特点，这里两个种群机器码均使用均匀交叉方式进行邻域搜索。

3.3.2 跟随蜂搜索过程的改进

在跟随蜂阶段，引领蜂依据轮盘赌概率选择方式选择蜜源并搜索，这种选择方式容易使算法陷入局部最优解中，故本文采用锦标赛选择策略[13]。因其只把适应度值的相对大小作为选择的标准，在一定程度上能减小超级个体的影响，对于防止算法的过早收敛有一定的作用。同时为加强两个子群间的信息交流，重新将两个子群合并为一个种群，根据锦标赛策略选出个体xij后，在种群中任选一个个体与其进行交叉并进行贪心选择。这样加强了种群间的信息交流，在一定程度上降低了单一种群易陷入局部最优解的风险，且贪心选择使算法不会丢弃目前的最优值，保证了较快的收敛速度。这里机器码采用多点变异方式，在机器码某些位置上随机选择可用机器替换当前机器，并同样采用贪心选择策略进行选择。

3.3.3 侦察蜂搜索过程的改进

ABC算法中若一个蜜源在搜索次数达到“limit”次后没有改变，则放弃该蜜源并通过侦察蜂随机搜索方式产生一个新蜜源。该操作虽然在一定程度上可以使算法跳出局部最优解，但若放弃的解恰好是全局最优解，则会导致算法重新搜索最优解，降低搜索效率。此外，考虑到算法陷入局部解的特点是种群中多个个体趋于相同，即拥有相同的适应度值，本文采取以下替换方式：

(1)设定全局最优解未改变次“limit”；

(2)每次迭代时记录当前种群的全局最优解gbesti；

(3)若gbesti在循环达到“limit”次为发生改变，则判断当前种群中最优适应度值的个数g；

(4)若g≻1，则按照定义的比例r，随机生成r×g新的个体取代该种群中部分适应值相同的最优个体。

3.4 改进ABC算法流程

基于以上所述，针对柔性作业车间调度问题改进后的ABC算法流程如图1所示。

图1 改进ABC算法流程图

4 实例验证

为验证该算法的有效性，本文选取了柔性作业车间Kacem基准函数[14]中的8×8和10×10两个案例进行求解。本文改进的人工蜂群算法参数设置为：种群规模：200；控制次数limit=10；最大迭代次数200；相似度比例C=0.93；侦察蜂重新生成比例r=0.8。将该算法运行10次，并与文献[14]中Kacem所得到的结果、文献[15]中所提的PSO算法和模拟退火算法(Simulate Anneal,SA)结合的方法和文献[16]所提的改进的GA算法的运行结果相比较，比较结果如表2所示(Cmax表示10次运行中所得的最优值，Aver.表示10次运行的平均值)。

表2 四种算法结果对比

从表2可以看出，本文所提的改进的人工蜂群算法针对两种算例获得的最优值均小于或等于其他三种算法，其中8×8问题和10×10问题的两个最优调度甘特图分别如图2、图3所示。

图2 8×8最优解甘特图(最优值Cmax=14) 图3 10×10最优解甘特图 (最优值Cmax=7)

5 结束语

针对柔性车间调度问题求解难的特点，本文改进人工蜂群算法的相关步骤，并用标准实例的求解结果和其他算法对比验证了该改进算法的具有良好的寻优性能和稳定性。下面研究的重点是如何将算法有效的改进并应用到多目标多资源约束的车间调度问题求解上，使研究更加符合实际的生产情况。

[参考文献]

[1] 李传鹏,王桂从,崔焕勇. 柔性作业车问调度问题研究现状及发展趋势[J]. 组合机床与自动化加工技术，2013 (11):109-112．

[2] 张国辉,党世杰. 遗传算法求解低碳柔性车间生产调度问题[J].组合机床与自动化加工技术,2016(11):141-144.

[3] 武福,张治娟.一种求解柔性作业车间调度问题的混合 智能算法[J].组合机床与自动化加工技术,2013(5): 130-133.

[4] Rossi A,Dini G.Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimization method[J].Robotics and Computer-Integrated Manufacturing,2007,23:503-516.

[5] 刘韵,胡毅,罗企,等.一种解决柔性车间作业调度问题的 粒子群优化算法[J].组合机床与自动化加工技术,2015 (12):144-147.

[6] Karaboga D.An idea based on honey bee swarm for numerical optimization[D]: Turkey:Computer Engineering Department,Erciyes University,2005.

[7] Karaboga D,Basturk B.On the performance of artificial bee colony (ABC) algorithm[J].Applied Soft Computing,2008,8(1): 687-697.

[8] 张素君,宁欣,顾幸生. 基于混合离散人工蜂群算法的置换流水车间调度[J].河南大学学报(自然科学版),2017,47(2): 194-201.

[9] 李俊青,潘全科,王法涛.求解混合流水线调度问题的离散人工蜂群算法[J].运筹与管理,2015,24(1):157-163.

[10]田野,徐洪华.求解多目标柔性作业车间调度问题的离散人工蜂群算法[J].长春理工大学学报(自然科学版),2015,38(4): 116-121.

[11] Liao G C,Tsao T P.Application Embedded Chaos Search Immune Genetic Algorithm for Short-term Unit Commitment[J].Electric Power Systems Research, 2004, 71(2):135-144.

[12]肖小城.粒子群求解作业车间调度问题的研究[D].郑州: 郑州大学,2010.

[13] BAO L,ZENG J C. Comparison and analysis of the selection mechanism in the artifical bee colony algorithm[C]. 2009 9thInternational Conference on Hybrid Intelligent Systems.Los Alamitos,CA:IEEE Computer Society, 2009: 411-416.

[14] Kacem I,Hammadi S,Bome P.Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems[J]. IEEE Transactions on Systems, Man and Cybernetics,Part C, 2002, 32(1):408-419.

[15] Xia W J,Wu Z M.An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problem[J]. Computer & Industrial Engineering,2005, 48 (2):409-425.

[16] 刘琼,张超勇,饶运清,等.改进遗传算法解决柔性作业 车间调度问题[J].工业工程与管理,2009,14(2):59-66.