面向作业车间调度的基于拓扑排序的二级嵌套蚁群算法研究

来源：机械工程学报杂志2015年第8期北京时间：

作者：罗亚波

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

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

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

基金资助：国家自然科学基金(51375357)和中央高校基本科研业务费专项资金(2012-II-015)资助项目