中文摘要：

蚁群算法的出现，为求解作业车间调度问题提供了新思路。然而，由于作业车间调度问题的可行域属性非常复杂，目前，采用蚁群算法进行求解，还存在收敛可靠性差和优化程度不高的问题。针对以上两个问题，在对工序拓扑排序的约束特性进行分析的基础上，提出基于拓扑排序的二级嵌套蚁群算法，其基本思想是：以拓扑排序为基础，采用受限主路径覆盖可行域，从而降低搜索的规模和盲目性，提升收敛可靠性；将问题分解为工艺路径优化和设备遴选优化两个级别的问题，从而构造二级优化机制，采用工艺主路径与设备支路径嵌套递归的方式，实现工序排序与设备遴选之间的相互干涉，从而提升解的满意度。比较试验表明，与目前常用的蚁群算法求解方法相比，采用基于拓扑排序的二级嵌套蚁群算法求解作业车间调度问题，具有良好的收敛可靠性、求解效率和寻优能力。

英文摘要：

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 constralnts 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 falrly 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.