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

Topological Sorting-based Two-stage Nested Ant Colony Algorithm for Job-shop Scheduling Problem

作　　者：罗亚波[1] 

机构地区：[1]武汉理工大学机电工程学院,武汉430070

出　　处：《机械工程学报》2015年第8期178-184,共7页Journal of Mechanical Engineering

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

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

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]