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

关键词：作业车间调度问题 蚁群算法 拓扑排序 递归 

单位：武汉理工大学机电工程学院 武汉430070