基于多种群蚁群算法的柔性作业车间调度研究

薛宏全，魏生民，张鹏，杨琳

1.西北工业大学现代设计与集成制造技术教育部重点实验室，西安 710072

2.西安理工大学经济与管理学院，西安 710048

3.西安工业大学，西安 710032

基于多种群蚁群算法的柔性作业车间调度研究

薛宏全1，2，魏生民1，张鹏2，杨琳3

1.西北工业大学现代设计与集成制造技术教育部重点实验室，西安 710072

2.西安理工大学经济与管理学院，西安 710048

3.西安工业大学，西安 710032

1 引言

柔性作业车间调度是Bruker和Schlie在1990年首次提出的，突破了传统作业车间调度中对加工机器的限制，相对于传统作业车间调度，柔性作业车间调度扩大了解的范围，增加了优化难度，是一个更为复杂的NP-hard，但其增加了车间作业调度的灵活性，更加符合企业实际生产现状，因此求解更为科学合理的柔性作业车间调度方案是近年来国内外制造系统调度研究中的一个热点问题。

目前求解柔性作业车间调度的研究主要集中在运用遗传算法[1-3]、粒子群算法[4-5]和蚁群算法[6-11]等算法通过迭代方法实现柔性作业车间调度方案优化。其中，Dorigo博士等人在1991年提出的蚁群算法，因其良好的正反馈、鲁棒性和群体性等特点，被越来越多地用于柔性作业车间调度求解中。张维存等人[6]以工件延迟时间和设备可用能力为启发信息，设计蚂蚁工件间和设备间的转移概率，通过蚂蚁游历获得最优适应值从而实现柔性作业车间调度方案求解。Andrea和王万良等人[7-8]通过对遍历蚂蚁判断是否陷入局部收敛分别对各路径上的信息素进行适当调整加速收敛速度实现柔性作业车间调度方案求解，李燕等人[9]以生产周期和关键工件交货期为优化目标，在传统蚁群算法基础上自适应调整挥发系数ρ，采用机床利用率ηij(t)作为新的启发式信息实现柔性作业车间调度方案求解。刘志勇和Rong-Hwa Huang等人[10-11]通过修改蚂蚁信息素更新规则，规定遍历蚂蚁产生至今最优解后才释放更新全局信息素，减少求解时间，提高了柔性作业车间调度的求解效率。综合现有相关研究分析，发现目前利用蚁群算法求解柔性作业车间调度的研究都是在传统蚁群算法基础上采用不同方法修改单一种群中单种信息素更改规则，虽然通过信息素更新规则的修改加快了收敛速度，提高了求解效率，但强化最优信息的反馈容易导致蚁群早熟和停滞现象；同时利用单一种群求解仅根据概率保持解之间的差异性，不能实现解的多样性。实际上蚁群在工作过程中是有组织、有分工的，不同种类的蚂蚁有不同的信息素调控机制[12-13]，体现出不同的搜索特点，这种分工组织方式应用到蚁群求解柔性车间调度中，对保持求解过程中解的多样性和避免蚁群早熟和停滞现象具有重要意义。

为此，本文结合蚁群分工组织方式，给出一种基于竞争规则的多种群蚁群算法求解柔性作业车间调度方法。求解中首先运用析取图表示柔性作业车间调度，再将蚂蚁分为不同种类的蚁群，把子种群的蚂蚁放到图中各个不同的节点上，通过蚂蚁的移动构造出完整的作业路径，构造路径过程中核心种群引导子种群在竞争中不断进化，经过反复迭代不断优化性能指标，最终根据核心种群对搜索子种群搜索结果的比较获得柔性作业车间最优调度方案。整个求解过程中算法在保证蚂蚁总数不变的前提下，通过不同种群间的行为差异实现种群的多样性来保障求解过程解的多样性；同时搜索子种群中应用竞争规则通过种群间竞争，充分发挥各种群自身的优势，动态调整搜索蚂蚁的分配，将有限的蚂蚁资源分配给搜索率高的种群，有效地缓解柔性作业车间调度求解过程中蚁群早熟和停滞现象发生。

2 柔性作业车间调度模型

2.1 问题描述

柔性作业车间调度在文献[14]中被描述为：作业车间中有n个工件在m台机器上加工，其中工件集合J为{J1,J2,…,Jn}，机器集合M为{M1,M2,…,Mm}；每个工件Ji由工序{Oi1k,Oi2k,…,Oink}按预先确定的加工顺序加工而成，每道工序Oijk（工件Ji的第j道工序在机器k上加工）可以在一组不同加工机器集合Mij(Mij⊆M)中任一台上加工，工序的加工时间随加工机器的不同而不同；调度目标是在为每个工件的每道工序选择最佳加工机器的同时确定每台加工机器上不同工序的最佳加工顺序及开工时间，使整个作业车间生产达到指定性能指标的最优。一个4×5的柔性作业车间调度实例[15]如表1所示。

每件工件在不同机器上加工过程中还满足：

（1）每台机器在同一时刻只能加工一个工件。

表14 ×5的柔性作业车间调度实例

（2）每一个工件在某时刻，只能在一台机器上加工，工序一旦开始被加工便不能中断（即不考虑机器故障），直到该工序被加工完成。

（3）不同工件间具有相同的加工优先级。

（4）不同工件的工序之间没有先后约束。

（6）在零时刻，所有工件都可以被加工。

2.2 析取图模型

析取图是Roy和Sussman在1964年提出的，由于其简单直观和便于分析的突出优点，被成功应用于旅行商问题的表示中。旅行商问题是推销员去N个城市推销货物，从城市vi(i＜N)出发，经其余所有城市一次，然后回到城市vi，要求所走路线最短。其析取图描述为：给定图G=(V,A)，其中V为各城市集合，A为城市间相互连接线组成的边集，已知各城市间的距离，确定一条长度最短的Hamilton回路，即遍历所有城市当且仅当一次的最短回路。

柔性作业车间调度是将n种不同工件的所有工序安排到m台机器上加工，要求最大完工时间makespan最小。通过比较分析发现，柔性作业车间调度和旅行商问题都是NP-hard问题，两者间具有很强相似性，都可采用析取图对问题进行表示。因此，在本文中借鉴析取图表示旅行商问题的方法建立柔性作业车间调度模型[15]。柔性作业车间调度的析取图模型描述为：给定图G=(V,C∪D)，其中V为所有加工工序节点v和两个虚拟工序节点S和E的集合，两个虚拟工序节点分别表示调度的开始和结束，加工工序节点v由不同该工序可加工机器组成；C为连通弧集合，C={＜v,w＞|v∈V,w∈V,v和w表示的两个工序为同一个作业}，对于∀＜v,w＞∈C，stw-stv≥pv表示节点v到节点w有一条连通弧（为单向弧），保证同一工件上的各工序加工顺序的先后约束，stv和stw为节点v和w所表示工序的开始加工时间，pv为节点v表示工序的加工时间；D为析取弧集合，D=Dr,r=1，2，…，m，Dr={(v,w)|v∈V,w∈V}，每一条析取弧（为双向弧）表示连接的节点v和节点w的工序将在同一台机器上加工。表1所示实例的析取图模型如图1所示。

图1 表1所示实例的析取图模型

在以最大完工时间makespan最小化为优化目标时，对于图1中第任意一台机器k(k∈M)的所加工工序而言，每一个加工方案都等价于D中的一个选择，即在D中的每个双向弧中选择一个确定的方向，若为有向非循环，则对应着第k台机器上所有工序的一个最优调度；同理，对所有加工机器进行选择，确定一个完整的有向非循环图G′=(V,C∪D′)即为Hamilton回路，使得最大完工时间makespan最小。

3 多种群蚁群算法求解原理

根据蚁群分工组织的工作方式，本文将蚁群分为2大类不同种群的蚁群，如图2所示。一类是核心蚁群，该种群根据各搜索蚁群的寻优结果，设定搜索种群间的信息交流方案，引导搜索蚁群向高效的方向搜索，最终获得最优调度方案。另一类是搜索种群，该类种群被分布在不同工序节点上，进行不同资源组合的调度方案寻优，为了保证搜索种群搜索效率，又进一步在搜索种群中引入精英蚂蚁和蚁群系统，将搜索种群分解为2子类种群，通过2子类蚁群间的竞争，充分发挥各子种群自身的优势，动态调整搜索蚂蚁的分配，将有限的蚂蚁资源分配给搜索率高的种群，有效地缓解柔性作业车间调度求解过程中蚁群早熟和停滞的现象发生。

图2 多种群蚁群结构

3.1 搜索种群间信息交流方案

搜索种群colonyi迭代满规定代数后，根据交换概率Intervalcolony(i,j)判断是否与外部种群j进行信息交换，交换时机选择：

为了避免信息交换对象的随机选择，信息交换对象根据种群间相似度Scolony(i,j)选择，有：

3.2 搜索种群间竞争规则

搜索种群搜索过程中，蚁群间的竞争通过淘汰差种群和裂变新种群实现动态调整搜索蚂蚁的分配，将有限的蚂蚁资源分配给搜索率高的种群。

种群间进行淘汰的主要依据是以各种群搜索效率为依据建立的种群淘汰裂变数，淘汰裂变数定义为：

其中，lit为设定阈值，iternum(i)表示种群i自最近一次获得历史最优解到现在的迭代次数，H为搜索种群的子种群数。若淘汰裂变数未达到阈值则认为colonyi种群还有发现最优解的机会，不会被淘汰。

当搜索种群的淘汰裂变数达到阈值时colonyi种群将被淘汰，淘汰种群中的蚂蚁数被平均分配到其他未淘汰种群中，加大这些种群搜索效率。经过若干次淘汰种群后，剩下种群数目小于维持多种群蚁群最低搜索所需数量时，通过核心种群选取搜索种群中最差值的种群进行裂变，裂变后的种群将生成两个蚂蚁数与裂变前种群蚂蚁数相同的种群，新生的两个蚁群中一个继承原种群的路径信息继续搜索，一个对种群路径信息进行归一化处理，加大其他方向的搜索力度，减少现有作业路径搜索停滞的可能性。

3.3 信息素更新规则

核心蚁群通过3.1节中的种群信息交流方法设定搜索种群间的信息交流方案，引导搜索种群向高效方向搜索，同时根据既定优化目标对各搜索种群的搜索结果进行评价，由当前获得的最优解作为依据，使用公式（5）定义的函数确定迭代过程中信息素的更新变化量。

其中，τmax和τmin分别表示信息素的最优和最差值，Δy表示信息素迭代过程中的取值。

搜索种群被放在不同工序节点上，从不同节点出发开始对所有节点进行遍历搜索构建出完整的加工序列，为了保证搜索种群搜索效率，在搜索种群中引入精英蚂蚁和蚁群系统实现对所有节点的搜索。精英蚂蚁在搜索过程中对找到的最优路径Tbs进行额外强化，强化量为e/Lbs，e为常数，Lbs为Tbs的长度，精英蚂蚁信息素更新策略为：

其中，ρ∈[0,1)表示路径信息素挥发程度，τvw(t)表示一次循环中走过vw路径的蚂蚁在该路径上释放的信息素总量，Δ(t)表示蚂蚁k在这次循环中在vw路径上释放的信息素浓度，Δ(t)表示蚂蚁k在到目前循环中在vw路径上释放的最优信息素浓度，Δ(t)和Δ(t)更新如下：

其中，Q为预设参数，Lk为所发现的最佳路径长度，Lbs为历史最优路径。

蚁群系统蚂蚁的信息素更新策略为：

其中，τvw(t)表示一次循环中走过vw路径的蚂蚁在该路径上释放的信息素总量，Δτ•表示精英种群信息素的更新量。

4 柔性作业车间调度求解过程描述

柔性作业车间调度求解中首先根据调度问题的工件、机器和加工时间等信息，借鉴旅行商问题的析取图表示方法建立如图1所示的柔性作业车间调度析取图模型G= (V,C∪D)，同时初始化工件数组J[][]，机器数组M[][]，工序数组O[][]和工件加工时间数组T[][]等信息；然后采用如图2的方式，将搜索蚁群向核心蚁群注册，并初始化所有蚁群；最后核心蚁群向所有搜索蚁群发布指令，分布在不同节点上的蚂蚁开始搜索，在整个运算过程中搜索蚁群将相关信息反馈给核心蚁群，核心蚁群根据反馈信息调整搜索种群的相关信息，控制所有蚂蚁完成路径遍历，并根据核心种群对搜索子种群搜索结果比较获得柔性作业车间最优调度方案，整个调度方案求解流程如图3所示。求解表1所示实例的最优调度方案如图4所示。

图3 调度方案求解流程图

图4 表1所示实例的最优甘特图

多种群蚁群算法求解柔性作业车间调度的具体步骤如下：

步骤1根据调度问题的工件、机器和工件加工时间等信息建立柔性作业车间调度的析取图模型，初始化相关信息。

步骤2将蚁群分类，一类为核心蚁群，一类为搜索蚁群；初始化核心蚁群相关信息，将搜索蚁群向核心蚁群注册，将注册后的搜索蚁群分为精英蚂蚁子群和蚁群系统子群，核心蚁群指令搜索蚁群初始化；搜索蚁群初始化时均被置于初始节点处，同时将每只蚂蚁初始节点被放入禁忌表Tabu[][]中，并设置未被访问的节点为G[][]以及下一步允许访问节点S[][]。

步骤3核心蚁群通知搜索蚁群开始搜索工作，对于每一只搜索蚂蚁在一步允许访问的节点S[][]中，根据公式（8）并结合轮盘赌的策略选择下一步将访问的节点，搜索蚂蚁在每经过的一条边vw后，立即更新该边上的信息素τvw= (1-ρ)τvw+ρ/Lvw。

其中ηvw(t)=1/Stw×Tw，Stw表示工序节点w的最早加工时间，Tw表示工序节点w选择相应机器的加工所需的时间。

步骤4将被选中的节点插入Tabu[][]中，同时从G[][]中删除该节点并更新S[][]。

步骤5判断Tabu[][]是否已满?若Tabu[][]已满，则根据Tabu[][]计算每只蚂蚁的目标函数值，否则，转至步骤3。

步骤6每个搜索蚁群完成一次迭代后，搜索蚁群将对更新图G中弧上信息素进行一次全局更新，精英蚁群蚂蚁和蚁群系统蚂蚁分别采用公式（6）和公式（7）实现搜索路径上信息素的更新。

步骤7核心蚁群判断搜索种群间是否进行信息交换，首先根据公式（1）计算交换时机，然后通过公式（2）计算搜索种群间相似度，当相似度满足指定阈值时，根据公式（3）完成信息交换。

步骤8根据公式（4）计算搜索种群的种群淘汰裂变数，当种群淘汰裂变数小于阈值时淘汰该种群并将淘汰种群中的蚂蚁数被平均分配到其他未淘汰种群中；当种群数小于阈值时，核心种群选取搜索种群目标函数最差值的种群进行裂变。

步骤9执行循环。判断是否满足停止条件?是，则结束循环输出最优调度方案；否则，清空Tabu[][]、G[][]和S[][]，转至步骤2。

在上面求解过程中可以看出，蚁群间不断通过信息交换，发挥各种群自身的优势，避免了大量冗余操作，在提高了收敛效率同时将有效地缓解蚁群早熟和停滞的现象发生。

5 实验结果与分析

为了测试多种群蚁群算法在求解柔性作业车间调度过程中的效率，首先从某航空发动机公司柔性加工车间生产过程中提取出一个6工件在10台机器上选择加工并且每个工件有6道加工工序的柔性作业调度实例，工件可选加工机器和加工时间如表2所示。

表2 车间加工信息

算法求解实例时参数设置：核心蚁群蚂蚁数为20，α=0.6,β=3，ρ=0.3,Q=15；搜索种群蚂蚁数为所有工序节点数，其中搜索种群采用精英蚁群ASelitist和ACS作为两种子蚁群，ASelitist的初始种群量为4，参数设置：α=1，β=5,ρ=0.5,Q=100,e=2，ACS的初始种群量为3，参数设置：α=1，β=1,ρ=ϖ=0.1，两种群间每隔2代进行一次通信，种群淘汰裂变数阈值为0.35，种群最小数目为6。整个求解过程在Intel®CoreTMi3 CPU 550@ 3.2 GHz×2，RAM 2.0 GB，操作系统Windows7的计算机上用Matlab 7.0编程实现，求解结果如图5所示，不同算法求解收敛曲线如图6所示，表3是本文算法与其他算法求解结果比较。

图5 实例求解结果

图6 收敛曲线

表3 不同算法30次求解结果

从图6中可看出，ACO和GA算法在求解过程中未能找到最小最大完工时就陷入了局部最优中，出现了算法求解过程的早熟和停滞现象，而GA-ACO算法和本文算法都搜索到表2实例中的最小最大完工时间makespan且都为53，避免了算法求解过程的早熟和停滞现象。从表3中可以看出对连续运行30次所求得的平均值、最差值和平均时间三个性能指标看，本文算法都表现出了较高的搜索效率，从而证明了该算法应用于求解柔性作业车间调度的可行性。

为了进一步测试本文算法的有效性，本文选取了柔性作业车间调度Kacem基准问题中的8×8、10×10和15×10三个实例及Brandimarte设计的BRdata问题中的mk01（10×6）、mk06（10×15）和mk09（20×10）三个实例，采用上例中的实验环境和参数设置对这六个实例进行求解，与相关文献中测试结果进行了比较，比较结果见表4。

表4 与相关文献比较

从表4中可以明显看出，利用多种群蚁群算法求解六个测试实例时所得的最优值Cmax均达到了比较文献中的求解结果，从而证实了该算法应用于求解柔性作业车间调度的有效性。

6 结束语

本文针对柔性作业车间调度特点，借鉴旅行商问题的析取图表示方法建立了柔性作业车间调度析取图模型；并结合蚂蚁工作过程中分工组织的方式，提出了一种基于竞争规则的多种群蚁群算法对柔性作业车间调度析取图模型进行求解；算法求解过程中将蚁群分为核心蚁群和搜索蚁群两大类，通过两者的协同和搜索蚁群内部的竞争，有效地缓解柔性作业车间调度求解过程中蚁群早熟和停滞的现象发生，达到了全局最优。最后经仿真比较证明了该算法在求解柔性作业车间调度中的可行性和有效性。

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

[2]De Giovanni L，Pezzalla F.An improved genetic algorithm for the distributed and flexible job-shop scheduling problem[J]. European Operational Research，2010，200（2）：395-408.

[3]刘冬梅，傅卫平，来春为，等.改进遗传算法求解柔性车间调度问题[J].西北大学学报：自然科学版，2011，41（4）：611-616.

[4]张静，王万良，徐新黎，等.基于改进粒子群算法求解柔性作业车间批量调度问题[J].控制与决策，2012，27（4）：513-518.

[5]卢冰原，程八一.混合粒子群算法在模糊柔性车间作业计划中的应用[J].计算机应用研究，2010，27（10）：3721-3723.

[6]张维存，郑丕谔，吴晓丹.蚁群遗传算法求解能力约束的柔性作业车间调度问题[J].计算机集成制造系统，2007，13（2）：333-337.

[7]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（5）：503-516.

[8]王万良，赵澄，熊婧，等.基于改进蚁群算法的柔性作业车间调度问题的求解方法[J].系统仿真学报，2008，20（16）：4326-4329.

[9]李燕，陈华平，王栓狮，等.自适应蚁群算法在双向生产车间调度中的应用[J].运筹与管理，2008，17（3）：160-163.

[10]刘志勇，吕文阁，谢庆华，等.应用改进蚁群算法求解柔性作业车间调度问题[J].工业工程与管理，2010，15（3）：115-119.

[11]Huang Ronghwa，Yang Changlin，Cheng Weiche.Flexible job shop scheduling with due window—a two-pheromone ant colony approach[J].International Journal of Production Economics，2013，141（2）：685-697.

[12]张鹏，魏云霞，薛宏全，等.基于优胜劣汰的异类多种群蚁群算法[J].计算机工程，2012，38（18）：182-185.

[13]邓可，林杰，张鹏.基于信息熵的异类多种群蚁群算法[J].计算机工程与应用，2008，44（36）：16-19.

[14]Yazdani M，Amiri M，Zandieh M.Flexible job-shop scheduling with parallel variable neighborhood search algorithm[J].Expert Systems with Applications，2010，37（1）：678-687.

[15]苏子林，苑金梁，陈炜，等.柔性作业车间调度分析及其启发式算法[J].计算机工程与应用，2012，48（10）：233-237.

[16]董蓉，何卫平.求解FJSP的混合遗传-蚁群算法[J].计算机集成制造系统，2012，18（11）：2492-2501.

XUE Hongquan1，2,WEI Shengmin1,ZHANG Peng2,YANG Lin3

1.Ministry of Education Key Lab of Contemporary Design&Integrated Manufacturing Technology,Northwestern Polytechnical University,Xi’an 710072,China
2.School of Economics and Management,Xi’an University of Technology,Xi’an 710048,China
3.Xi’an Technological University,Xi’an 710032,China

To the characteristics of flexible job-shop scheduling,this paper designs the disjunctive graph model of the flexible job-shop scheduling and presents the solution of the multiple ant colony algorithm for the competitive rule.According to the labor mode of ant colony,different colonies are located in different processing nodes in the algorithm.By the command of core colony, all types of ant colonies with pheromone updating mechanism and searching traits have mutual compensation of advantages as well as mutual competitive exclusion so that they can potentially cooperate smoothly,and fulfill the scheduling requirements of flexible job-shop scheduling.Through the analysis of the simulating experiment results prove the feasibility and effectiveness of the algorithm.

flexible job-shop scheduling;multiple ant colony;competitive rule;disjunctive graph

针对柔性作业车间调度的特点，设计了柔性作业车间调度析取图模型，结合蚁群分工组织的工作方式，给出了基于竞争规则的多种群蚁群算法求解方法。算法中不同种群的蚂蚁被放置在析取图中不同的工序节点上，通过核心种群的引导，充分发挥蚁群协作竞争的并行高效特点，满足柔性作业车间调度的要求。仿真实验表明该算法求解柔性作业车间调度具有可行性和有效性。

柔性作业车间调度；多种群蚁群；竞争规则；析取图

A

TP278

10.3778/j.issn.1002-8331.1306-0315

XUE Hongquan,WEI Shengmin,ZHANG Peng,et al.Flexible job-shop scheduling based on multiple ant colony algorithm.Computer Engineering and Applications,2013,49（24）：243-248.

教育部人文社科基金（No.13YJC630224）；陕西省科技厅自然科学基金（No.2013JM8039）；陕西省教育厅科学研究计划（No.12JK0998）。

薛宏全（1978—），男，博士研究生，讲师，研究领域为计算智能，先进制造管理；魏生民（1948—），男，博士，教授，博导，研究领域为现代集成制造技术，信息化工程与管理；张鹏（1975—），男，博士，讲师，研究领域为计算智能。E-mail：msxuehq@xaut.edu.cn

2013-06-26

2013-08-15

1002-8331（2013）24-0243-06