An ant colony optimization algorithm for flowshop scheduling

A novel Ant Colony Optimization algorithm is presented for a flowshop scheduling problem. In the algorithm, the flowshop scheduling problem is represented by a directional graph. Guided by a 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 search space of the problem and increases the probability of ants finding good solutions. Comparisons with other algorithms on Taillard's benchmark problems show that the algorithm proposed in this paper performs better and has stronger adaptability and robustness.