Abstract: Ant colony algorithm is a new approach to solve the job-shop scheduling problem (JSSP). However, there are still some difficulties in solving JSSP by current ant colony algorithm due to the complex attribute of feasible zone, such as the low reliability of convergence and the weak ability of optimization. Facing with the two difficulties above, based on the analysis on the constraints features of machining processes topological sorting, a topological sorting-based two-stage nested ant colony algorithm is proposed. The thinks of the novel methodologies include: the searching range is downsized and the blindness of searching is reduced at a fairly large scale by employing the topological sorting algorithm to limit the majority searching paths, which covers the feasible zone as yet, consequently the reliability of convergence gets improved; The problem is divided into two sub problems of the machining process optimization and the machines selection optimization to construct the mechanism of two-stage optimization. The interaction between the optimization of scheduling and the optimization of machines allocation is realized by two-stage nested recursive algorithm involving majority process flow and branch of machines selection, so that the degree of satisfaction of the solution is effectively improved. The contrastive experiments demonstrate that the novel methodologies used to solve JSSP have higher reliability of convergence, efficiency of searching and the capability for finding better solutions compared to the normal ant colony algorithm.

Key words: ant colony algorithm, job-shop scheduling problem, recursion, topological sorting