混合遗传蝙蝠算法求解单目标柔性作业车间调度问题

2018-07-04徐华,程冰

小型微型计算机系统 2018年5期

徐华,程冰

(江南大学物联网工程学院,江苏无锡 214122)

1 引言

车间调度问题一直以来都是科学研究的一个热点.柔性作业车间问题(FJSP)是在作业车间调度的基础上扩展的更加灵活复杂的调度问题.相比于经典的作业车间调度,FJSP考虑了同一个工艺可以在不同的机器上加工的问题,不同机器上的加工时间也有所不同.FJSP减少了对机器的约束,扩大了可行解的搜索范围,增加了求解难度,使得调度问题更加复杂、更加灵活.柔性作业车间更加贴近实际生产中的制造环境,更符合现代柔性制造的理念.

首次提出FJSP的是Bucker P.和Schlie R.[1],此后便引起了广大学者的关注研究.FJSP已经被证明是一个NP-hard问题[2].目前,求解FJSP的方法大多集中在智能算法以及多种智能算法结合的混合算法上,如遗传算法(Genetic Algorithm,GA)[3-5]、蚁群算法(Ant Colony Optimization,ACO)[6,7]、粒子群算法(Particle Swarm Optimization,PSO)[8,9],还有一些其他的算法[10-13].蝙蝠算法(Bat Algorithm,BA)是一种模拟蝙蝠回声定位机理得出的算法,是Yang在2010年提出的一种新兴启发式智能算法[14].发展至今,蝙蝠算法已经应用到很多领域,如函数优化[15]、无线传感网络[16,17]、电网系统[18,19]等.在生产调度领域,许多专家学者应用蝙蝠算法及其改进算法求解调度优化问题.夏晶晶等人提出一种改进型蝙蝠算法来优化车间内工件的最大完工时间[20].韩忠华等人提出基于汉明距离精英个体集的自适应蝙蝠算法求解柔性流水车间调度问题[21].Luo等人针对置换流水车间问题,将NEH算法与蝙蝠算法相结合,并将调度问题划分为若干个子问题[22].Dao等人受并行处理的启发,提出基于通信策略的并行蝙蝠算法来求解作业车间调度问题[23].

从上述内容中可以看出,蝙蝠算法成功的应用于车间调度领域,但是其相关性的研究尚不成熟,蝙蝠算法自身也有易陷入局部最优的缺点.本文结合遗传算法的变异交叉操作,提出一种混合遗传蝙蝠算法(HGBA)来求解单目标柔性作业车间问题.同时采用三种方式对种群进行初始化,在保证解的多样性的同时也保证了解的质量;引用动态递减的权重来均衡局部搜索与全局搜索;针对蝙蝠算法易陷入局部最优解的问题,提出一种基于变异操作的邻域搜索;结合于本文采用的基于机器编码方式,提出混合列交叉的策略来进行位置更新,避免产生无效解.最后通过实例测试,实验结果证明了HGBA算法的有效性.

2 柔性作业车间调度模型

2.1 问题描述

柔性作业车间与经典作业车间的区别就是工序可在多台机器上加工.根据工序可选加工机器集的大小,可将柔性作业车间调度分为两类:一类是完全柔性作业车间调度(T-FJSP),即每个工序可以在所有的机器上加工;一类是部分柔性作业车间调度(P-FJSP),即至少有一个工序不能在所有的机器上加工.T-FJSP是P-FJSP的一种特殊情况,在实际情况中,P-FJSP中机器的选择一般都存在约束,所以P-FJSP更具有实际意义,而且P-FJSP是比T-FJSP更复杂的调度问题.

FJSP可以简单描述为:n个工件在m台机器上加工,工件集J={J1,J2,…,Jn},机器集M={M1,M2,…,Mm}.每个工件Ji(i∈{1,2,…,n})有λi(λi≥1)道工序,并且每道工序可在一台或者多台机器上加工.每道工序可以任意选择一台机器加工,不同机器加工的时间长短也不同.调度问题的目标就是在满足约束条件的基础上,合理的安排工件的加工次序、加工时间以及加工机器.FJSP问题中的相关符号定义如下:

Oij表示工件Ji的第j(j∈{1,2,…,λi})道工序;

Wijk表示工序Oij在机器k上加工状态,并且有:

(1)

Tijk表示工序Oij在机器k上的加工时间;

Bijk表示工序Oij在机器k上的开始加工时间;

Eijk表示工序Oij在机器k上的完工时间;

Ci表示工件Ji的完工时间.

本文的目标是使得最大完工时间Cmax最小,最大完工时间是指最后一个工件被加工完成的时间,代表着整个调度的生产周期.目标函数如下所示:

func=min(max(Ci)),1≤i≤n

(2)

2.2 约束条件

1)每个工序在加工过程中不允许被中断,假设机器无故障:

Eijk=Bijk+Tijk

(3)

2)每个工件必须按照工序的顺序加工,不可乱序,即Oij完成之后才可加工Oi(j+1):

(4)

也可表示为:

(5)

3)不同工件的工序之间不存在先后约束.

4)同一个机器在某时刻只允许加工一道工序;即当工序Oij在时刻t(t>0),若有Wijk=1,则当i≠p且j≠q时,必不存在Opq使得Wpqk=1.

5)每台机器相互独立,任何一台机器是否工作、是否故障都不影响其他设备,并且所有机器在开始时刻(t=0)均可以开始工作.

表1给出3个工件、5个机器(3×5)的P-FJSP调度例子,表中的数据表示工序在对应的机器上的加工时间,其中“—”表示工件不能在该机器上加工.

表1 3×5调度实例Table 1 3×5 Scheduling example

3 蝙蝠算法

蝙蝠算法是根据蝙蝠回声定位的原理得出的启发式算法.蝙蝠以速度vi在位置xi处随机飞行,以频率fi和响度A搜寻猎物.根据自身与猎物之间的距离来调节发射的脉冲频率,调整发射的脉冲速率r0∈[0,1].在d维空间里,x=(x1,x2,…,xd)T,初始种群规模为pop_size,单个蝙蝠表示为xi(i=1,2,…,pop_size).蝙蝠算法相应变量更新如下:

1)速度与位置更新:

fi=fmin+(fmax-fmin)β

(6)

vi(t+1)=vi(t)+(xi(t)-x*)fi

(7)

xi(t+1)=xi(t)+vi(t+1)

(8)

其中,fi是发射频率,取值范围为[fmin,fmax];β为随机变量,β∈[0,1];vi(t)、xi(t)为第t代蝙蝠的速度与位置,vi(t+1)、xi(t+1)为第t+1代蝙蝠的速度与位置,均为d维向量;x*表示当前的最优解;

2)局部搜索,对当前最优解按照如下规则进行搜索:

xnew=xold+εAt

(9)

xold表示选择的一个解,xnew表示进行扰动后的新解;ε∈[-1,1],At表示第t代蝙蝠的平均响度.

3)响度与脉冲发射速度更新:

(10)

(11)

4 求解FJSP的遗传蝙蝠算法

4.1 编码方式

表2 可选机器集Table 2 Optional machine set

下面按照表一中给出的实例数据进行说明.从表中数据可知,工序O11可在M1、M2、M4这3个机器上加工,则有S1={1,2,4},可选机器个数SN1=3,对应的基因g1取值在[1,SN1]之间,假设此时取g1=3.同理,O12可以在M1、M3、M4、M5这4个机器上加工,则有S2={1,3,4,5},可选机器个数SN2=4,对应的基因g2取值在[1,SN2]之间,假设此时取g2=1.依照此方式可对基因序列进行完整的编码.表2列出了工序的可选机器集.随机给出一个完整的编码序列为[3 1 3 3 4 2 1 2],通过编码方式可以反向进行解码,得出对应的工序的加工机器序列,因此上述编码对应的工序加工机器为[4 1 4 5 5 3 2 3].图1为解码示意图.

图1 解码示意图Fig.1 Decoding diagram

4.2 种群初始化

许多智能算法如粒子群算法、遗传算法等在某种程度上其性能易受初始种群的影响.在初始化种群的过程中既需要保证种群的多样性,也需要保证种群的质量.因此,初始种群需要达到两个基本要求:一是多样性,多样性好的初始解覆盖的解空间大,搜索范围广,寻找到全局最优解的机率也更大;二是初始解的质量,解的质量影响着收敛速度.为了满足这两点,本文按照以下方案进行初始化.

1)随机生成法:根据每个工序可选择的加工机器,随机选择一台机器.

2)最小时间选择法:根据工序在可选机器上的加工时间选择用时短的机器.当不同机器上的加工时间相同时,则比较机器上的现有的工作量(即机器上的处理时间),选取工作量小的机器.

3)第二小时间选择法:选择工序在可选机器上加工时间第二小的机器.

在初始化种群时,采用轮盘赌的形式.对于某一个解,其基因位上的值由如下方式决定:当rand<0.4的时候采用方案(1);当rand≥0.4,采用方案(2)选择机器的,同时当工序可选的最小时间机器只有一个,为避免解的多样性变差,则随机选择采用方案(2)与方案(3)来生成.

4.3 惯性权重重定义

为了平衡局部搜索与全局搜索,针对公式(7)引入权重变量变为:

vi(t+1)=w*vi(t)+(xi(t)-x*)fi

(12)

并且采用惯性权重动态递减的方式变换权重值,改进的权重w重定义为:

(13)

其中,wmax与wmin分别表示为w可取的最大值与最小值.t为当前迭代次数,tmax为总迭代次数.其动态变化如图2所示.

图2 w变化曲线Fig.2 Change curve of weight

4.4 混合列交叉更新策略

标准蝙蝠算法的位置更新公式为xi(t+1)=xi(t)+vi(t+1),由于本文采用的是基于机器的编码,直接利用上式更新蝙蝠位置会导致无效解的产生,一是由于出现小数产生无效解;二是由于超出编码范围产生无效解.通过4.1节的编码方式可知,z位上的编码基因最大值为SNz,一般的更新方式易产生无效解.因此本文提出混合列交叉更新策略,由于此策略是同一工序的加工机器交换,所以产生的必为可行解.将上式(8)更新为

xi(t+1)=xi(t)⊗vi(t+1)

(14)

在该式中将vi(t+1)看作索引,指向与xi(t+1)交叉的序列,交换其对应位置的元素.给出一组数据进行说明.

当x1⊗v1时,v1中的第一个元素为3,即指向x3的第一个元素,互换x1与x3的第一个元素;v1中的第二个元素为2,即指向x2的第二个元素,互换x1与x2的第二个元素,依此类推,对x1元素进行更新.当所有的都更新完之后,得到的新位置如下:

在算法初期,经过列交叉之后,种群多样性会增加.到算法后期,所有蝙蝠都飞向最优蝙蝠,位置之间的相似度增强,更新过后算法逐渐收敛.

4.5 基于变异操作的邻域搜索策略

算法中个体可以通过对自身以及对邻域解进行搜查以获取更优有解.邻域结构的合理性体现着求解策略对问题本身特征信息的利用,影响着最终求解的效率和质量[24].因此,需要合理的设置邻域结构.本文采取两种基于变异操作的邻域搜索策略.

1)基于最优排列的变异:在调度解的编码中随机选择两个位置,根据上文叙述可知每个位置上的基因有几种,生成其所有排列,产生相应的邻域解,选择其中适应度值最好的个体.

2)基于机器工作量的变异:在调度解的编码中随机选择两个位置,分别对所选位置可加工的机器进行工作量的分析,选择工作量小的机器取代原位置.

邻域搜索的伪代码如下:

while(ct

b←rand()

if(b≥0.5)

根据方案(1)进行变异生成新的个体

else

根据方案(2)进行变异生成新的个体

endif

if新解的适应度值比旧解的适应度值好

接受新解

end if

ct←ct+1

end while

4.6 HGBA算法流程

HGBA算法具体步骤如下:

步骤1.设置参数,并且根据本文采用的编码方式,按照4.2的初始化方法产生初始种群

步骤2.通过设定的目标函数求解每个个体的适应度值,得出当前最优解

步骤3.根据式(6)、(12)、(14)更新个体的速度与位置

步骤4.对于每个个体,当rand1>ri,则通过4.5的邻域搜索算法对当前最优解进行扰动,产生一个新解

步骤5.若新解优于当前最优解且rand2

步骤6.更新当前最优解,并对其进行邻域搜索

步骤7.满足设定的最优解条件或者达到最大迭代次数,则终止程序;否则就转到步骤3

步骤8.输出最优解和最优值

5 实验仿真与结果

本文实验采用MATLAB编程,程序在Windows 10系统下内存6G的计算机上运行.算法中的参数设置如下:

表中pop_size表示初始种群规模,tmax表示总迭代次数,ctmax表示邻域搜索的总迭代次数,fmin与fmax分别表示频率的最小值与最大值,wmin与wmax表示权重的最小值与最大值.

为了验证本文算法的性能,分别采用三种实例进行测试,经典10×10实例以及文献[25]、文献[26]中的实例.同时采用BA算法与改进算法HGBA进行比较,为了让BA算法与HGBA相比具有可信度,BA中的相应参数设置均与HGBA相同.

表3 参数值列表Table 3 List of parameter values

实例1是经典10×10实例,它是10个工件在10台机器上加工的完全柔性作业车间调度问题,利用本文算法求解该问题可以得到当前所知的最优解7,图3为对应甘特图.

图3 10×10最优解甘特图Fig.3 Gantt chart of optimal solutionfor 10×10

实例2是6×6实例,实验数据来源于文献[25],利用本文的算法求解该问题可得到全局最优解为10,该全局最优解对应的调度甘特图如图4.

图4 6×6最优解甘特图Fig.4 Gantt chart of optimal solutionfor 6×6

实例3是6×8实例,实验数据来自文献[26],6个工件共26道工序在8台机器上加工.利用本文提出的HGBA对实例进行优化,得出全局最优值为55,图5为最优解调度甘特图.

表4中的数据均为独立运行10次产生的.“best”列表示算法得到的最小完工时间的全局最优解,“avg”列表示10次运行得到的最优解的平均值.首先,从表中可以看出,对于经典10×10实例,HGBA算法可以得出当前最好的结果7,相对于标准BA算法,改进的HGBA算法的精度提高了61.11%.

图5 6×8最优解甘特图Fig.5 Gantt chart of optimal solutionfor 6×8

对于6×6实例,HGBA算法得出的全局最优值为10,与文献[25]中的结果相比,最优解精度提高了9.09%;与BA相比,最优解精度提高了16.67%.对于6×8实例,HGBA算法得出的全局最优值为55,与文献[26]中的结果相比,最优解精度提高了8.33%;与BA相比精度提高了6.80%.实验数据证明了HGBA算法求解FJSP问题的有效性.

表4 测试结果Table 4 Test results

图6 10×10收敛曲线图Fig.6 Convergence curve for 10×10

图6、图7给出了用BA与HGBA分别求解10×10实例与6×8实例的全局最优解收敛图,从图中可以看出,由于对初始化进行改进的缘故,HGBA在刚开始迭代时就可以获得较好的解,BA的初始解明显较差.对于10×10实例,在迭代中能够BA算法在得到全局最优解20处陷入局部最优,而HGBA能够跳出局部最优继续进化得到全局最优解7;同样的,对于6×8实例,BA在59处陷入局部最优,HGBA能够跳出局部最优继续进化而得到更优质的解55.这证明了本文算法在初始化与采用的邻域搜索的有效性.因此,本文提出的HGBA算法在求解柔性作业车间调度是有效的,可以得到良好的效果.

图7 6×8收敛曲线图Fig.7 Convergence curve for 6×8

6 结论

柔性作业车间由于工序可选择的加工机器的多样性而变得更加的复杂,解空间更大.本文以最大完工时间最小化为目标进行柔性作业车间的优化调度,提出混合遗传蝙蝠算法.首先,针对初始解的多样性与质量,采用多种方式相结合来初始化种群;其次通过重定义w权重来平衡全局与局部搜索,提出基于变异的邻域搜索策略避免陷入局部最优;同时根据本文采用的基于机器的编码方式与调度问题的离散性问题,提出了混合列交叉策略来进行位置的更新;最后并将标准BA算法与改进算法HGBA用于求解3个实例,实验结果对比证明了算法的有效性.然而,在实际的生产过程中,调度的好坏还受很多其他因素的影响,比如加工质量、提前/拖期等,笔者下一步将在本文的基础上,研究多目标柔性作业车间问题.

：

[1] Brucker P,Schlie R.Job-shop scheduling with multi-purpose machines[J].Computing,1990,45(4):369-375.

[2] Garey M R,Johnson D S,Sethi R.The complexity of flow- shop and jobshop scheduling[J].Mathematics of Operations Research,1976,1(2):117-129.

[3] Liu Xiao-bing,Jiao Xuan,Ning Tao,et al.Improved methodof flexible job shop scheduling based on double chains quantum genetic algorithm[J].Computer Integrated Manufacturing System,2015,21(2):495-502.

[4] Taisch M.Multi-objective genetic algorithm for energy-efficient job shop scheduling[J].International Journal of Production Research,2015,53(23):7071-7089.

[5] Zhang Teng-fei,Ma Yue,Li Li,et al.Improved genetic algorithm for flexible job shop scheduling problem[J].Journal of Chinese Computer Systems,2017,38(1):129-132.

[6] MinseokSeo,Daecheol Kim.Ant colony optimisation with parameterised search space for the job shop scheduling problem[J].International Journal of Production Research,2010,48(4):1143-1154.

[7] Tian Song-ling,Chen Dong-xiang,Wang Tai-yong,et al.An asynchronous parallel ant colony optimization for flexible job-shop scheduling problem[J].Journal of Tianjin University(Science and Technology),2016,49(9):920-928.

[8] Zhang Qi-liang,Chen Yong-sheng.Hybrid PSO-NEH algorithm for solving no-waitflexible flow shop scheduling problem[J].Systems Engineering-theory & Practice,2014,34(3):802-809.

[9] Zhong Yu-jiang,Yang Hai-cheng,Mo Rong,et al.Optimization method of flexible job-shop scheduling problem based on niching and particle swarm algorithms [J].Computer Integrated Manufacturing System,2015,21 (12):3231-3238.

[10] Li Xiu-lin,Lu Jian-sha,Chai Guo-zhong,et al.Hybrid bee colony algorithm for flexible Job Shop scheduling problem[J].Computer Integrated Manufacturing System,2011,17 (7):1495-1500.

[11] Zhao Shi-kui.Bilevel neighborhood search hybrid algorithm for the flexible job shop scheduling problem[J].Journalof Mechanical Engineering,2015,51(14):175-184.

[12] Wu Xiu-li,Zhang Zhi-qiang,Du Yan-hua,et al.Improved bacteria foraging optimization algorithm for flexible job shop scheduling problem[J].Computer Integrated Manufacturing System,2015,21(5):1262-1270.

[13] Gao K Z,Suganthan P N,Pan Q K,et al.Discrete harmony search algorithm for flexible job shop scheduling problem with multiple objectives[J].Journal of Intelligent Manufacturing,2016,27(2):363-374.

[14] Yang X S.A new metaheuristic bat-inspired algorithm [M].Nature Inspired Cooperative Strategies Foroptimization,Berlin:Springer,2010:65-74.

[15] Li Zhi-yong,Ma Ling,Zhang Hui-zhen.Quantum bat algorithm for function optimization[J].Journal of Systems & Management,2014,23(5):717-722.

[16] Chen Y T,Tsai M T,Liao B Y,et al.An echo-aided bat algorithm to construct topology of spanning tree in wireless sensor networks[M].Intelligent Data Analysis and Its Applications,Springer International Publishing,2014:451-462.

[17] Goyal S,Patterh M S.Modified bat algorithm for localization of wireless sensor network[J].Wireless Personal Communications,2016,86(2):1-14.

[18] Lin Jun-hao,Zhang Yan,Chen Si,et al.Optimal DG allocation considering effect of controllable load for active distribution system[J].Electric Power Automation Equip-ment,2016,36(9):46-53+73.

[19] Yang Jia-ran,Wang Xin-cheng,Jiang Cheng,et al.Multi-objective dynamic optimal scheduling of power system considering wind power risk[J].Power System Protection Control,2016,44(7):25-31.

[20] Xia Jing-jing,Wang Meng.Improved bat algorithm for job shop scheduling problem[J].Journal of HuaZhong Normal University(Natural Sciences),2016,50(4):536-543.

[21] Han Zhong-hua,Zhu Bo-qiu,Shi Hai-bo,et al.Study for flexible flow shop scheduling problem with based on advanced bat algorithm[J].Application Research of Computers,2017,33(7):1-6.

[22] Luo Q,Zhou Y,Xie J,et al.Discrete bat algorithm for optimal problem of permutation flow shop scheduling [J].Scientific World Journal,2014,2014:1-15.

[23] Dao T K,Pan T S,Nguyen T T,et al.Parallel bat algorithm for optimizing makespan in job shop scheduling problems[J].Journal of Intelligent Manufacturing,2015:1-12.

[24] Zhao Shi-kui,Fang Shui-liang.Operation-based encoding and neighborhood search genetic algorithm for job shop scheduling optimization[J].Journal of Mechanical Engineering,2013,49(16):160-169.

[25] Peng Jian-gang,Liu Ming-zhou,Zhang Ming-xin,et al.Cloud model evolutionary multi-objective flexible job-shop scheduling based on improved non-dominated sorting[J].Journalof Mechanical Engineering,2014,50(12):198-205.

[26] Kong Fei,Wu Ding-hui,Ji Zhi-cheng.Flexible job-shop scheduling optimization based on two-layer particle swarm optimization algorithm[J].Journal of Computer Applications,2015,35(2):476-480.

附中文参考文献：

[3] 刘晓冰,焦璇,宁涛,等.基于双链量子遗传算法的柔性作业车间调度[J].计算机集成制造系统,2015,21(2):495-502

[5] 张腾飞,马跃,李力,等.柔性作业车间调度问题的改进遗传算法[J].小型微型计算机系统,2017,38(1):129-132.

[7] 田松龄,陈东祥,王太勇,等.一种异步蚁群算法求解柔性作业车间调度问题[J].天津大学学报(自然科学与工程技术版),2016,49(9):920-928.

[8] 张其亮,陈永生.基于混合粒子群-NEH算法求解无等待柔性流水车间调度问题[J].系统工程理论与实践,2014,34(3):802-809.

[9] 仲于江,杨海成,莫蓉,等.基于小生境粒子群算法的柔性作业车间调度优化方法[J].计算机集成制造系统,2015,21(12):3231-3238.

[10] 李修琳,鲁建厦,柴国钟,等.混合蜂群算法求解柔性作业车间调度问题[J].计算机集成制造系统,2011,17(7):1495-1500.

[11] 赵诗奎.求解柔性作业车间调度问题的两级邻域搜索混合算法[J].机械工程学报,2015,51(14):175-184.

[12] 吴秀丽,张志强,杜彦华,等.改进细菌觅食算法求解柔性作业车间调度问题[J].计算机集成制造系统,2015,21(5):1262-1270.

[15] 李枝勇,马良,张惠珍.函数优化的量子蝙蝠算法[J].系统管理学报,2014,23(5):717-722.

[18] 林君豪,张焰,陈思,等.考虑可控负荷影响的主动配电系统分布式电源优化配置[J].电力自动化设备,2016,36(9):46-53+73.

[19] 杨家然,王兴成,蒋程,等.计及风力发电风险的电力系统多目标动态优化调度[J].电力系统保护与控制,2016,44(7):25-31.