A Novel Bi-Directional Convergence Ant Colony Optimization with SA for Job-Shop Scheduling

The bi-directional convergence ant colony optimization can effectively solve job-shop scheduling, but it often fall into local optimization result. While the simulated annealing has some characteristics can make the convergence process jump out of the local optimum. In this paper an application of the simulated annealing to be integrated into the bi-directional convergence ant colony optimization is proposed to tackle the complex job-shop scheduling problem. First, we propose an improved ant colony optimization structure for this problem by extending the convergence process with a simulated annealing procedure for the job-shop scheduling problem. Then we develop a new solution generating rules, which uses random choose, judge, exchange three steps for constructing the simulated annealing to fit the special job-shop scheduling problems and improve the constructed solutions. Therefore, when the ant colony optimization fall into a local optimum, simulated annealing is used to help the intermediate result jumping out of local optimum, and the global optimum is improved in turn. We compare this algorithm to an exist bi-directional convergence ant colony optimization by Wang, Cao and Dai to job-shop scheduling. Simulation results show that our algorithm works well when applied to the complex job-shop scheduling instances.