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

摘要

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