量子萤火虫算法及在无等待流水调度上的应用

Quantum Glowworm Swarm Algorithm and Its Application to No-wait Flowshop Scheduling

  • 摘要: 针对无等待流水车间调度问题,提出了一种新颖的量子萤火虫优化算法用于最小化总完工时间.首先,将量子进化机制嵌入萤火虫算法中,并设计一种快速的局部邻域搜索方法,在每次迭代时只搜索部分邻域,同时采用目标增量计算邻域解变化,这样极大地加快了算法迭代速度,加速了算法收敛.最后,应用Taillard基准测试实例仿真,与目前较优的启发式算法IHA(improved heuristic algorithm)和群智能算法DGSO(discrete glowworm swarm optimization)、 GA-VNS(genetic algorithm-variable neighborhood search)及DHS(discrete harmony search)相比较,产生最好解的平均百分比偏差均下降了40%以上.实验结果验证了所提算法在求解无等待流水调度中的优越性.

     

    Abstract: We propose a novel quantum glowworm swarm optimization algrorithm for minimizing total flow time in no-wait flowshop scheduling. First, we embed the quantum evolutionary mechanism into the glowworm swarm algorithm. Then, we design a fast local neighborhood search algorithm to search the partial neighborhood of each iteration and calculate a neighborhood solution with a target increment. This algorithm not only greatly improves the solution quality, but also increase the speed of convergence. Based on Taillard's benchmark simulation, the results show that the average relative percentage deviation from the best-known solution is reduced by more than 40%, compared with the optimal heuristic algorithm IHA and the swarm intelligence algorithms DGSO, GA-VNS, and DHS. These experimental results verify the superiority of the proposed algorithm in performing no-wait flowshop scheduling.

     

/

返回文章
返回