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

摘要：

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

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

分类号：TP301(计算技术、计算机技术)

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

在线出版日期：2015-05-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：178-184