一种求解柔性作业车间调度问题的混合智能算法*

武 福张治娟

(1.甘肃省轨道交通装备系统动力学与可靠性重点实验室，兰州 730070;2.兰州交通大学 机电工程学院，兰州 730070)

0 引言

蚁群算法(Ant Colony Algorithm)是意大利学者M.Dorigo等人通过模拟自然界蚂蚁寻径的行为提的一种应用于组合优化问题的启发式搜索算法，它充分利用蚁群行为中所体现的正反馈机制进行求解，同时，利用分布并行计算方式在全局的多点进行解的搜索［1］。

遗传算法(GA)是模拟自然界生物遗传机制的随机搜索算法，通过选择、交叉、变异等优化过程设计人工寻优方法，其特点在于容易与其他智能算法相结合，形成更好的优化算法［2］。

粒子群算法(PSO)是由美国的Kennedy和Eberhar于1995年提出的基于群智能的进化类算法。该算法通过粒子在解空间追随最优粒子进行搜索，操作简单，易于实现［3］。

柔性调度问题是车间调度问题和并行机调度问题的综合与推广，是强NP-hard问题，其特征是某些加性以及多目标性更能反映实际生产过程，其理论和方法具有更高的应用价值，目前柔性调度问题已经成调度研究得热点，受到了许多研究者的关注，取得了不少的研究成果。国内外许多学者曾用蚁群算法(ACO)、遗传算法(GA)、禁忌搜索算法(TS)、粒子群算法(PSO)等求解柔性作业车间调度问题，取得了很好的效果［1-4］。目前国内对多目标柔性调度的研究相对较少，吴秀丽等［5］进行了基于混合遗传算法的多目标优化方法的研究，遗传算法具有大范围的全局搜索能力，但对反馈信息利用不足，当解到一定程度时往往做大量无用的冗余迭代;蚁群算法具有反馈机制但收敛速度慢;PSO算法收敛速度快，但不能保证得到最优解。针对以上各算法的优缺点，为了使各种算法取长补短，提高算法寻优的效率，本文提出了将蚁群算法、遗传算法、PSO算法进行融合的混合智能算法，并将其应用于解决多目标柔性作业车间调度问题(flexible job-shop scheduling problem，FJSP)的求解。

1 问题描述和模型的建立

FJSP问题可描述如下：假定一个加工系统有m{M1，M2，…，Mm}台机器和 n{J1，J2，…，Jn}个工件，每个工件包含Ki{Ki=1，2，…，m}道工序，记为Ji={Oi1，Oi2，…，OiKi}。工件的加工顺序是确定的，每道工序OiKi可以在多台不同的机床上加工。调度目标是合理地将每道工序安排到机器上，并对每台机器要加工的工序进行有效的排序，使加工系统的某些性能指标取得最优值(如最小制造周期、最大交货满意度、最低生产成本等)。

为了简化问题，我们先从完工时间、交货期、两个机床总负荷、最大负荷几个方面进行评价并建立如下的优化目标函数：

其中，j=1，2，…，n;k=1，2，…，m;Cj为工件 Ji的完成时间;dj为工件Ji的交货期;Pijk为工件的第i道工序在第k台机器上加工所需要的时间;Xijk为决策变量，表示工件Ji的第i道工序是否在第k台机器上加工;Xijk=0表示未选中，Xijk=1表示选中。

同时根据调度模型给出的如下假设(约束)：①不考虑机床故障，工件运输时间计算在加工时间内;②每台机床每次只能处理一道工序;③工序一旦进入加工状态就必须完成，不可以中断;④不同工件的工序间没有先后顺序要求;⑤各工序在不同机床上的加工时间是预先给定的［5-12］。

2 混合智能算法的优化原理

将车间作业调度问题描述为一个有向图［7］，图中边的属性(比如长度)代表该工序的加工时间，这样可将该加工时间的问题转化为路径规划问题。因此，为了提高收敛速度，本文提出了一种混合智能算法。首先利用蚁群算法寻找满足min{Cmax}的初始路径，然后利用遗传算法进行调度路径的优化，利用粒子群算法对蚁群算法中的信息素进行更新和调整，其中蚁群算法中下一节点选择及信息素调整是该算法的关键［1，4］。

2.1 节点的选择

假设第i只蚂蚁在节点r，则按照下述规则选取下一个节点s：

其中，τ(r，u)表示节点r到节点u间的信息素之量;η(r，s)表示节点r到节点s间的启发式因子;α、β分别表示加工路径上的信息量和启发式因子的权重;q是［0～1］之间的单位分布的随机数;q0是满足0≤q0≤1的常数;allowedi={0，1，2，…，n －1}表示蚂蚁i允许选择的下一个所有节点。否则，按(2)式选择下一个节点。

2.2 信息素的调整

2.2.1 信息素的全局更新

每次迭代后，对全局最优加工路径按式(4)进行信息素调整，其余按式(5)进行调整。

其中，e表示信息素挥发程度，e∈(0，1)。

2.2.2 利用PSO算法进行信息素的局部更新

为了进一步提高优化效果，在信息素更新中引入PSO算法［4］。如果第i只蚂蚁找到的路径满足目标函数的要求，则对该路径上的信息素进行局部调整，否则不调整。若没有局部更新，所有蚂蚁将在前一次最好加工路径的有限相邻区域内搜索。POS算法的作用是用来局部更新各蚂蚁所寻路径上的信息素，使较优路径上的信息素增加;最终使后续蚂蚁寻径时收敛于该路径。常见的惯性权值：

其中，xi表示位置;vi表示速度;random()为(0，1)之间的随机数;c1，c2为学习因子，一般取c1=c2=2;w为惯性权值，在0.7～0.9之间时算法性能最佳;pi表示个体最优粒子;g表示全局最优粒子。

2.3 遗传算法的参数设置

2.3.1 编码与适应度函数

遗传算法的一个显著特点是交替地在编码空间和解空间中工作，它在编码空间中对染色体进行遗传算法，在解空间进行评估和选择。

考虑到受工序的加工路线的约束，本算法中选择了基于工序的编码方式［5］，将调度编码为工序的序列，每个基因代表一道工序，给所有统一工件的工序制定相同的符号，然后根据它们在给定染色体中出现的顺序加以解释。

在该调度算法中，采用权重系数法计算个体的适应度，由于寻径有多种方案，而每种方案对各指标的满足程度不同，分别为每一种方案的各指标赋予随机权重，然后线性相加，即为该方案的适应度函数。多目标柔性调度的适应度函数的计算过程如下［6］：

其中，wi为权重系数，t为目标个数。

2.3.2 初始群体与染色体的选择

采用按改进后的蚁群算法搜索到的x条路径，作为初始群体，x为群体规模，根据交叉、变异的概率。采用轮盘赌法作为选择方法，选择准备交配的染色体。

2.3.3 交叉和变异操作

由于该混合算法用染色体确定工序的优先权，然后用一次通过优先分配启发式算法产生活动调度，因此不要求双亲和后代中部分调度的工序顺序一致，故采用简单的单断点交叉法，随机产生一个断点，交换双亲上断点的右端，最后调整染色体，删除多余的基因，添加丢失的基因使产生的后代合法化。变异采用基于邻域［6］搜索的机理设计，以便产生改进的后代。具体操作方法为：首先随机产生3个不同位置点，3个基因的全排列共生成6个新染色体，调用评价函数评价染色体，用具有最高适应值个体取代群体中适应值较低的染色体。

3 混合智能算法的实现

针对柔性作业车间调度多约束性、动态性以及多目标性的特点，结合蚁群算法、遗传算法、PSO算法各自的优缺点，试图提出一种将以上三种算法进行融合的混合智能算法。该算法的流程图如下：

图1 混合智能算法流程图

4 算例验证与分析

算法运行环境为Pentium 4，CPU主频2.6GHz，256GB内存，Windows XP操作系统，并采用Visual Basic6.0编写。为验证本文算法的性能，分别采用两组仿真实验验证了算法的性能。

4.1 仿真实验1

为了便于比较本算法的性能，首先选用文献［2］中的算例进行研究。该算例为8个工件，6台机床，每个工件的工序1～4个不等，共20个工序的柔性作业车间调度。参数设置为：循环次数1000，种群大小为100，蚂蚁数100，交叉概率0.05，α =4，β =2，c1=c2=2，w=0.8，w1=0.4，w2=0.5，运行10次，平均运行时间为43.4(s)。运行结果如表1所示(其中，A，B，C分别表示生产周期，最大负荷，机床总负荷)。表1中可以看出，本算法的生产周期目标A的最优解为22，最优解平均值为23.9，其均优于文献［2］的24和248。

表1 算法运行结果

4.2 仿真实验2

为了进一步验证算法的有效性，采用混合智能算法(ACO+GA+PSO)对表2所示的三个标准测试用例(8×8，10×10，15×10)进行求解，对每个测试用例运行15次，9次得到最优解.并与一些典型的优化算法求解结果进行对比，比较结果如图2所示。进行比较的优化算法包括：混合粒子群算法(PSO+SA)［3，11］、改进遗传算法(IGA)［4，11］、粒子群禁忌搜索算法(PSO+TS)［5，12］。ACO+GA+PSO 算法(本文算法)主要参数：种群大小为100，蚂蚁数为50，交叉概率为0.05，迭代次数为2000，α =4，β =2，c1=c2=2，w=0.8，w1=0.4，w2=0.5。

表2 求解结果比较

从表中可以看出，对于每个标准用例，最小生产周期目标比文献［3～5］中最好的结果降低了1～2个单位，相应的性能也提高了约7% ～18%;最大负荷目标在8×8用例中和文献［3，4，6］中最好的结果持平，而在其它两个用例中也分别降低了1～2个单位，性能也得到了相应的提高;但各用例的总负荷目标略微有所下降，比最好的指标高了3～6个单位，性能下降了约4%～6%。由此可见，提出的新的混合智能算法对求解多目标优化问题取得了良好的效果。

5 结论

本研究在蚁群算法的基础上提出了新的求解多目标柔性job-shop调度问题的混合智能算法。FJSP与JSP的不同在于增加了机器选择这一环节，使得求解更加复杂，采用蚁群算法寻径生成初始群体，利用遗传算法进行调度的路径优化，利用粒子群算法对蚁群算法中的信息素进行优化，使算法能够快速跳出局部收敛，达到全局最优。经仿真比较，证明该算法是有效、可行的。这种将不同算法优势相结合的策略对于类似FJSP的组合优化问题，具有较好的求解效果，这也是未来发展和研究的方向之一。

［1］刘志勇，吕文阁，谢庆华，等.应用改进蚁群算法求解柔性作业车间调度问题［J］.工业工程与管理，2010，15(3)：115－119.

［2］白俊杰，王宁生，唐敦兵.一种求解多目标柔性作业车间调度的改进粒子群算法［J］.南京航空航天大学学报，2010，42(4)：447 －453.

［3］袁坤，朱剑英.一种求解多目标柔性Job Shop调度的改进遗传算法［J］.中国机械工程，2007，18(2)：156－160.

［4］吴秀丽，孙树栋，余建军，等.多目标柔性作业车间调度优化研究［J］.计算机集成制造系统，2006，12(5)：731 －736.

［5］ZHANG Guohui，SHAO Xinyu，LI Peigen，et al.An Effective Hybrid Particle Swarm Optimization Algorithm for Multiobjective Flexible Job-shop Scheduling problem ［J］.Computers and Industrial Engineering，2009，56(4)：1309 －1318.

［6］宋晓宇，朱云龙，尹朝万，等.应用混合蚁群算法求解模糊作业车间调度问题［J］.计算机集成制造系统，2007，13(1)：105 －109，125.

［7］刘晓霞，谢里阳，陶泽，等.柔性作业车间多目标优化研究［J］.东北大学学报，2008，29(3)：362 －365，382.

［8］余琦玮，赵亮，潘双夏.基于遗传算法的柔性作业车间调度优化［J］.组合机床与自动化加工技术，2004(4)：34－36.

［9］XIA Weijun，WU Zhiming.An Effective Hybrid Optimization Approach for Multi-objective Flexible Job-shop Scheduling Problems［J］.Computers and Industrial Engineering，2005，48(2)：409 －425.

［10］ZHANG Guohui，SHAO Xinyu，LI Peigen，et al.An Effective Hybrid Particle Swarm Optimization Algorithm for Multi-objective Flexible Job-shop Scheduling problem［J］.Computers and Industrial Engineering，2009，56(4)：1309 －1318.

［11］雷德明.现代制造系统智能调度技术及其应用［M］.北京：中国电力出版社，2011.

［12］刘民，吴澄.制造过程智能优化调度算法及其应用［M］.北京：国防工业出版社，2008.