求解作业车间调度问题的改进萤火虫算法

陶文华，侯萌萌

（辽宁石油化工大学 信息与控制工程学院，辽宁 抚顺　113001）

求解作业车间调度问题的改进萤火虫算法

陶文华，侯萌萌

（辽宁石油化工大学 信息与控制工程学院，辽宁 抚顺113001）

作业车间调度问题是将多台机器安排处理多个工件的组合优化问题，使最大完工时间达到最小。应用传统萤火虫算法求解时，萤火虫个体到达最优解附近时，相对吸引力逐渐增强，导致局部搜索能力减弱，造成求解结果在最优解附近震荡，进而使求解精度下降。为改善解的质量，本文在萤火虫算法迭代过程中引入精英选择策略，保护进化过程中的优秀个体，避免最优解丢失；为提高算法收敛速度与求解精度，对萤火虫位置更新方法引入基于种群规模和迭代次数的动态自适应惯性权重；同时对每一代萤火虫种群最优个体引入禁忌搜索算法，提高局部搜索能力。仿真结果表明本文所提出改进算法在解决作业车间调度问题上的有效性与实用价值。

作业车间调度；改进萤火虫算法；精英选择策略；惯性权重

生产调度可以被定义为寻找一个问题的最优序列，执行一组有限操作来满足约束条件［1］。这是一个决策分配资源的过程在时间上执行所需任务的集合。有效调度对任何行业的增长至重要的作用。不同文献中讨论的调度问题的类型具有不同性能的措施，如单机排序［2］，流水车间调度［3］、并行机调度［4］等。而作业车间调度［5］是其中一种重要类型的调度环境。该问题与很多组合优化类问题一样，是NP难问题。其求解方法分为精确算法与近似算法，精确算法需要大量的时间成本，对于较大规模的作业车间调度问题，精确算法所需要的时间严重超出了实际过程可以接受的范围。因而，依靠近似算法进行作业车间调度问题的研究成为近年来的一个热门方向。近似算法主要包括优先权规则调度算法，启发式算法以及基于邻域搜索的局部改进算法等。使用启发式算法求解作业车间调度问题已迅速增长，如遗传算法［6］、粒子群算法［7］、人工免疫系统［8］、离散人工蜂群［9］、离散的帝国主义竞争算法［10］、混合帝国主义竞争算法［11］等。

萤火虫算法［12］是由杨新社教授在2008年根据萤火虫通过荧光进行信息交流而提出的一种新型启发式算法。该算法模拟自然界中萤火虫群体高效的觅食、择偶的机制，原理简单，设置参数少，而且算法中萤火虫个体间依靠荧光进行信息交换形成正反馈机制，具有快速地全局搜索能力。杨娇等［13］首先将萤火虫算法直接应用到作业车间调度问题上，为解决作业车间调度问题提供了一种新的思路。但在解决问题过程中，算法易陷入局部最优，求解精度低。包晓晓等［14］在基本的萤火虫算法基础上增加了局部寻优的过程，并融合了布谷鸟算法中生物移动的莱维分布特点来求解具有退化效应的作业车间调度问题，但计算量大，求解效率低。

禁忌搜索算法（TS）［15］是一种自适应的局部搜索算法，主要思路是利用禁忌表将已出现过的最优值禁忌以达到避免算法陷入局部最优的目的，黄志等［16］提出一种求解作业车间调度问题的启发式算法，该算法结合禁忌搜索技术和前瞻思想，在试探式禁忌搜索过程中，对一个给定的可行解，每次在邻域中连续试走（移动）两步，对每两个连续的移动都用禁忌搜索过程得到一个调度。但该算法是搜索性能依赖于给定的初始解，一个较好的初始解可以使TS算法较快的收敛于全局最优解，但一个较差的初始解可能很大程度上降低算法的收敛速度。

结合禁忌搜索算法与萤火虫算法的优点，文中提出一种解决作业车间调度问题的改进的萤火虫算法。首先利用参数少，易操作的萤火虫算法进行全局搜索，并引入精英选择策略，对每一代种群中的优秀个体进行保留并产生下一代种群，以提高算法寻优速度；给出一种自适应权重的萤火虫位置更新方法，提高求解精度；对萤火虫算法全局寻优后得到的最优位置萤火虫采用禁忌搜索算法进行局部寻优，加强算法跳出局部最优的能力，有效地避免陷入局部最优。同时，禁忌搜索算法每一次迭代的初始解均由萤火虫种群重新产生，可以有效改善禁忌搜索算法对于初值敏感的缺陷，提高了局部搜索能力。针对典型作业车间调度问题的仿真实验表明本文所提出算法的有效性与实用价值。

1　作业车间调度问题的描述

作业车间调度问题是一类典型的组合优化问题。该问题可描述为在一个加工系统中，有n个待加工的工件在m台机器上进行加工，每个工件的加工顺序是确定的，但不要求一致。而且各操作的加工时间已知。一个工件完成一道工序过程中不能中断，当这个工序完成时，这台机器才可以加工下一个工件。本文的调度目标是确定每个机器上工序的加工顺序和每个工序的开工时间，使最大完工时间最小。

2　基于改进萤火虫算法的作业车间调度实现

2.1基本萤火虫算法

萤火虫算法首先在问题求解空间中随机初始化N个萤火虫个体，每个萤火虫个体代表作业车间调度问题的一个可行解，其中第i（i=1，2，L，N）个萤火虫在D维空间中的当前位置并都带有自身具有一定荧光亮度，大小与所求解具体问题的目标函数值有关。目标函数值越好，萤火虫的亮度越强。亮度强的萤火虫吸引亮度弱的萤火虫，使亮度弱的萤火虫向亮度强的萤火虫移动。萤火虫移动后位置进行更新。随着迭代过程的进行，种群中亮度弱的萤火虫不断向比自己更亮的萤火虫靠近，最终大多数的萤火虫会聚集在最亮的萤火虫周围，最亮的萤火虫的位置就是问题的最优解。

2.2禁忌搜索算法

禁忌搜索算法（TS）是一种具有记忆能力的局部搜索算法，用s表示一个可行解，V（s）表示其对应的移动集合，Cmax（s）表示完工时间，C*表示当前最小完工时间，t表示当前迭代次数。设s′表示禁忌搜索的初始解。禁忌搜索算法求解问题的步骤为：

步骤1：设置禁忌搜索的最大步长maxiternum，令迭代次数iternum=0，设置禁忌表T=Ø，C*=Cmax（s*），s=s*；

步骤2：iternum=iternum+1，找出移动集合V（s），若V（s）=Ø，迭代停止，返回新解s*；

步骤3：应用邻域搜索程序，找到移动v′∈V（s），求出新解s′和新的禁忌表T′，令s=s′，T=T′；

步骤4：如果Cmax（s）＜C*，则设置C*=Cmax（s），s*=s；

步骤5：如果未达到停止准则，转步骤2；否则停止迭代，得到新解s*。

停止准则设置为：禁忌搜索次数达到10次或所得到的最优解5次未改变。

2.3改进的萤火虫算法

首先本文为了保护在进化过程中曾经出现的优秀个体，引入精英选择策略。将父代萤火虫种群和子代萤火虫种群合并成一个新的种群，并计算个体的适应度，根据适应度的大小选取新种群中前50%个体作为父代进行新一轮进化操作得到下一代萤火虫种群。

其次，考虑当运行至后期时，萤火虫个体会达到或接近最优个体附近，此时，萤火虫的相对吸引力将会逐渐增强，导致算法局部搜索能力减弱并可能造成求解结果在最优值附近震荡，进而导致求解精度下降，求解效率降低。为此，在位置更新公式中引入惯性权重，以提高萤火虫算法的局部搜索和全局搜索能力。

惯性权重设置为随种群规模及算法迭代次数的增加而减小，为此，对萤火虫位置更新方式作如下改变：对于萤火虫更新前的位置，引入一个服从正态分布的随机变量ω，使其与种群规模大小和迭代次数相关，其表达式如下：

其中，n是种群规模，k是迭代的最大次数，t是当前迭代次数，σ是标准差，a是常数。

进而得到引入惯性权重后的位置更新公式如下：

最后，将禁忌搜索 （TS）思想融入到萤火虫算法中，提出一种改进的萤火虫优化算法。新算法结合了FA和TS各自的优点，在求解作业车间调度问题前期利用萤火虫算法得到较好的初始值，同时种群最优值放人禁忌表，在算法运行后期，由于萤火虫种群聚集在最优萤火虫附近导致算法搜索能力减弱，利用禁忌搜索算法中禁忌表的记忆功能，使其跳出局部最优解，并且在搜索过程中允许接受劣解。

禁忌搜索算去的引入思路是：引入一个灵活的存储结构和相应的禁忌准则以避免迂回搜索，并通过特赦准则赦免一些被禁忌的优良状态。禁忌表用于存储最近几次的迭代中萤火虫所到达过的求解空间中的位置，在之后的迭代过程中，已经出现过的位置被禁忌而不能达到。当禁忌表中记录的位置达到所设计的禁忌表的最大长度或是禁忌表中的某个候选解的位置优于种群历史最优解的位置时，解禁该候选解，这个条件称为特赦准则。引入禁忌搜索的思想可以提高算法局部搜索能力与运行效率，并有效避免算法进行迂回搜索导致陷入局部最优。

应用本文所提出的改进的萤火虫算法求解作业车间调度问题的步骤为：

步骤1：初始化种群。设置萤火虫种群规模，最大的迭代次数，禁忌表的长度，禁忌搜索的最大步长，最大荧光亮度及光强吸收系数。加工工件的工序采用字符串编码方法，随机选择并排序编码工序直到所有工序都被编码。编码中萤火虫的位置长度等于优化问题中的所有工序数；萤火虫种群大小决定候选解的数量或者解空间里的搜索数量。

步骤2：随机初始化萤火虫的位置，计算萤火虫的目标函数值作为各自最大荧光亮度。本文对于作业车间调度问题，优化问题的目标函数为最小化最大完工时间，即minCmax，调度顺序的优劣选择也由Cmax决定。

步骤3：选取前50%个体计算萤火虫相对亮度，根据相对亮度决定萤火虫的移动方向。

步骤4：根据式（2）更新萤火虫位置得到下一代萤火虫并与上一代萤火虫组成新的种群。根据萤火虫的新位置，重新计算萤火虫的亮度。

步骤5：选取当前种群中的最优个体按禁忌搜索算法进行局部搜索，达到禁忌搜索停止准则时转步骤6。

步骤6：判断是否满足最大迭代次数，如果满足则转入下一步，否则，迭代次数增加，转步骤3进行下一次搜索。

步骤7：输出全局最优解（最小完成时间）和最优个体（即最优排序）。

3　仿真结果与实验分析

仿真实验环境为：Windows XP操作系统，CPU为P4，内存为2 GB，采用Matlab R2011b编程实现该算法。

为了便于验证本文提出的改进的萤火虫算法在解决作业车间调度问题中的可行性，仿真对象采用国际标准实例FT10（10×10），LA06（15×5），LA10（15×5）。算法参数设置如下：种群大小设置为 N=40，迭代次数为200，光强吸收系数γ=0.1，禁忌表的长度maxIterStep=5，禁忌搜索的最大步长maxNoneNum=10。

为了说明本文提出的改进的萤火虫算法解决作业车间调度问题的有效性，针对FT10、LA06、LA10两种测试例的仿真结果如表1～3所示。

表1　针对FT10 20次仿真实验的结果比较

表2　针对LA06 20次仿真实验的结果比较

表3　针对LA10 20次仿真实验的结果比较

从测试结果可以看出，改进的萤火虫算法和基本的萤火虫算法均能搜索到已知的最优值，验证了改进萤火虫算法在处理作业车间调度问题上的可行性。

4　结束语

文中针对作业车间调度问题，充分利用萤火虫算法简单易操作的特点，结合禁忌搜索算法，得到了一种高效，高求解精度，且能有效避免求解过程陷入局部最优的禁忌-萤火虫算法，通过对几类较大规模的标准作业车间调度问题的仿真实验，验证其可行性与实用价值。不足之处在于算法中引进了新的可调参数，对算法带来了一定影响，因此，从理论上进一步分析算法的收敛性及收敛速度及参数对结果的影响将是我们下一步的研究内容。

［1］Jacek B，Wolfgang D，Erwin P.The job shop scheduling problem：Conventional and new solution techniques［J］.European Journal of Operational Research，1996，93（1）：1-33.

［2］akar T.Single machine scheduling with unequal release date using neuro-dominance rule［J］.Journal of Intelligent Manufacturing，2011，22（4）：481-490.

［3］Mirabi M，Ghomi，S.M.T.F，Jolai，F.A two-stage hybrid flowshopschedulingprobleminmachinebreakdown condition［J］.Journal of Intelligent Manufacturing，2013，24 （1）：193-199.

［4］Ying，K.C，Lee，Z.J，Lin，S.W.Makespan minimization for scheduling unrelated parallel machines with setup times［J］. Journal of Intelligent Manufacturing，2012，23（5）：1795-1803.

［5］Meeran S，Morshed M S.A hybrid genetic tabu search algorithm for solving job shop scheduling problems：A case study［J］.Journal of Intelligent Manufacturing，2012，23（4）：1063-1078.

［6］Hasnahmoin.N，Sin OC，Omar M.Hybrid genetic algorithm with multiparents crossover for job shop scheduling problems ［J］.Mathematical Problems in Engineering，2015：1-12.

［7］Lin T L，Horng S J，Ka T W，etal.An efficient job-shop scheduling algorithm based on particle swarm optimization［J］. Expert Systems with Applications，2010，37（3）：2629-2636.

［8］Qiu X，Lau H.K.An AIS-based hybrid algorithm for static job shop scheduling problem［J］.Journal of Intelligent Manu-facturing，2014，25（3）：489-503.

［9］Yin M，Li X，Zhou J.An efficient job shop scheduling algorithm based on artificial bee colony［J］.Scientific Research and Essays，2011，6（12）：2578-2596.

［10］Hosseini S，Khaled A A.A survey on the imperialist competitivealgorithmmetaheuristic：Implementationin engineering domain and directions for future research［J］. Applied Soft Computing，2014，24：1078-1094.

［11］HosseiniS，KhaledA，VadlamaniS.Hybridimperialist competitive algorithm，variable neighborhood search，and simulated annealing for dynamic facility layout problem［J］. NeuralComputingandApplications，2014，25（7-8）：1871-1885.

［12］Yang X S.Nature-inspired metaheuristic algorithm［M］. Luniver Press，2008.

［13］杨娇，叶春明.应用新型萤火虫算法求解Job-shop调度问题［J］.计算机过程与应用，2013，49（11）：213-216.

［14］包晓晓，叶春明.改进的萤火虫算法求解具有学习退化效应的JSP问题［J］.数学理论与应用，2014，9（3）：65-75

［15］Zhang C，Li P，Guan Z，Rao Y.A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem［J］.Computers and Operations Research，2007，34 （11）：3229-3242.

［16］黄志，黄文奇.一种基于禁忌搜索的作业车间调度算法［J］.计算机工程与应用，2006（3）：12-14．

Improved firefly algorithm for job-shop scheduling problem

TAO Wen-hua，HOU Meng-meng
（School of Information and Control Engineering，Liaoning Shihua University，Fushun 113001，China）

Job-shop Scheduling problem（JSP）is a combinatorial optimization problem to arrange muti workpiece on multi machines to obtain minimize the maximum completion time.Fireflies wander nearby the optimal solution at the late stage of traditional firefly algorithm to solve JSP，causing strong mutual attraction and weakening the local search ability and declining the solving precision.Elite selection strategy is introduced aiming at protecting the excellent individuals to improve the solution quality.Dynamic adaptive inertia weight corresponding with the population scale and iteration number is introduced to the location update method to improve the convergence speed and solution precision.Apply tabu search algorithm to the best individual of each generation to enhance the local search ability.Simulation results demonstrate the effectiveness and merits.

job-shop schedule；improved firefly algorithm；elite selection strategy；inertial weight

TP29

A

1674－6236（2016）09-0113-03

2016-02-01稿件编号：201602004

国家自然科学基金青年基金项目（61203021）

陶文华（1972—），女，浙江绍兴人，硕士，教授。研究方向：生产调度优化理论与应用。