Study on the convergence of converse ant colony algorithm for Job Shop Scheduling Problem

摘要

A hybrid algorithm of converse ant colony optimization (HCACO) was proposed by Markov chain theory, which was applied to enhance the performance of the intelligence optimization algorithm for resolving Job Shop Scheduling Problem and overcome the disadvantages of the slow convergence speed and stagnation behavior when solving Job Shop Scheduling Problem as well. In order to improve the probability of escaping from the local optimization, we inducted converse ants into the ant colony. Meanwhile, each solution of ACO with certain probability pursued the process of parallel SA algorithm to accelerate the coverage speed and improve the quality of solutions of Job Shop Scheduling Problem. Under the guidance of the above converge theory, we found the optimums of FT10, LA19 and LA38 in a shorter period when we applied HCACO to 13 typical benchmarks Job Shop Scheduling Problems, which demonstrated the convergence and effectiveness both in theory and practice.