求解零空闲流水线调度问题的改进蚁群算法

摘要

This paper proposed an advanced ant colony algorithm for no-idle flow shop problem (NIFS) with makespan criterion. Improved the pheromone density initialization and updating rules by using a hybrid heuristic strategy, adoped a new state transition rule to construct an ant-sequence. Then, presented an local search algorithm based on the speed-up technology for inserting neighborhood structure for overcoming algorithm into the local convergence. And the simulation experiments show that the presented algorithm is effective and superiority in finding optimal or near optimal solutions.%针对零空闲流水线调度问题的最大完工时间,提出一种改进蚁群算法.该算法改进了信息素密度的初始化方法和更新规则,采用新的状态转移策略构建新解,结合快速插入邻域局部搜索算法,解决蚁群算法易陷入局部收敛的缺点,从而提高算法的搜索效率.基于典型算例的仿真实验,表明了改进算法具有高效性和优越性.