Flow shop问题的蚁群优化调度方法

An Ant Colony Optimization Algorithm for Flowshop Scheduling

提出了一种新颖的蚁群优化算法 ,用于解决流水作业 ( flowshop)的优化调度问题 .算法中 ,流水作业调度问题以结点或弧模式有向图表示 ,人工蚁受有向图上信息素踪迹的指引 ,在图上搜索并一步步构造出问题的可行解 .算法中的信息素踪迹更新过程作为蚁群间的间接通信机制 ,将引导整个蚁群收敛到问题的优化解 .信息素踪迹更新过程中的停滞状态脱离机制以及信息素踪迹限制机制能帮助人工蚁跳出局部最优解 .算法局部搜索过程中采用的基于关键路径的邻域结构缩小了问题的搜索空间 .与其他算法在 Taillard流水作业调度测试问题集上的比较试验表明 ,本算法性能更优 ,且具有更强的自适应和鲁棒性 .

A novel Ant Colony Optimization algorithm is presented for flowshop scheduling problem. In the algorithm, the flowshop scheduling problem is represented by a directional graph. Guided by pheromone trail, each artificial ant travels in the graph iteratively to construct its tour that represents a feasible solution. The pheromone trail updating procedure acts as an indirect communication mechanism within the ant colony, leading all the ants to converge to good tours. The stagnation step out mechanism and the pheromone trail limit mechanism in pheromone trail updating procedure are developed to help ants stepping out of stagnation effectively. The critical block based neighborhood structure of the problem in the local search procedure reduces the searching space of the problem and increases the probability of ants finding good solutions. Comparisons with other well\|performed algorithms on Taillard′s benchmark problems show that the algorithm proposed in this paper performs better and has stronger adaptability and robustness.