求解作业车间调度问题的变邻域动态烟花算法

Dynamic Fireworks Algorithm Based on Variable Neighborhood Search for Job-shop Scheduling Problem

针对最小化最大完工时间的作业车间调度问题,提出一种基于变邻域搜索的动态烟花算法。变邻域搜索是一类重要的元启发式算法,在每一次迭代计算过程中通过搜索当前解的邻域得到一个改进的解,通过变邻域搜索方法可有效提高局部最优解的精度。与此同时,算法引入进化速度的概念,并通过进化速度计算烟花算法迭代过程中需更新的维度,实时调整相关参数,加快算法收敛,避免陷入局部最优。算例试验表明,该算法具有较好的鲁棒性,且能有效地提高算法搜索精度,加快收敛速度。

A dynamic fireworks algorithm based on variable neighborhood search is proposed to solve job-shop scheduling problem（ JSP） with objective function of minimizing the maximum completion time. Using variable neighborhood search which is an important meta-heuristic algorithm,an improved solution can be obtained by search the neighborhood of the current solution during iteration calculation,so the accuracy of the local optimal solution can be improved effectively. At the same time,the concept of evolutionary speed is introduced to the proposed algorithm and is used to calculate the dimensions of the firework algorithm iteration process. Wherefore the relevant parameters can be adjusted in real time,the convergence of the algorithm is accelerated and the local optimum is avoided. Typical example experiments show that the algorithm has certainly robustness and improves optimization accuracy and convergence.