求解模糊Job Shop调度的遗传算法与蚁群算法融合研究  

Study on the Combination of Genetic Algorithms and Ant Colony Algorithms for Solving Fuzzy Job Shop Scheduling Problems

作　　者：宋晓宇[1] 常春光[1] 曹阳[1] 

机构地区：[1]沈阳建筑大学信息与控制工程学院,辽宁沈阳110168

出　　处：《小型微型计算机系统》2008年第7期1286-1290,共5页Journal of Chinese Computer Systems

基　　金：国家重点基础研究项目(2002CB312204)资助;辽宁省教育厅研究项目(20060701)资助

摘　　要：提出一种算法融合策略,解决单一算法求解模糊Job Shop调度问题存在的不足,提高这类问题的求解质量.算法融合策略中,采用遗传算法和蚁群算法进行并行搜索;根据模糊Job Shop调度问题解的特征,提出基于关键工序的邻域选择方法,并将基于这种邻域选择方法的禁忌搜索算法作为局部搜索算法,加强了遗传算法和蚁群算法的局部搜索能力.采用算法融合策略的混合优化算法对以13个难的benchmarks问题经模糊化得到实例进行求解,在较短的时间内,得到的平均满意度较并行遗传算法(PGA)提高5.24%、较TSAB算法提高8.40%.采用算法融合策略构造的混合算法具有较强的搜索能力,说明提出的混合搜索策略是有效的.A hybrid strategy is proposed to solve fuzzy job shop scheduling problems, which can overcome the shortcomings of a single algorithm for fuzzy job shop scheduling problems and improve the quality of solutions. This strategy adopts genetic algo- rithms and ant colony algorithms as a parallel asynchronous search algorithm. In addition, according to the characteristics of fuzzy Job Shop scheduling, we propose a concept of the critical operation and a new neighborhood search method based on the concept. Based on this search method, a TS algorithm is designed, which can improve the local search ability of genetic algorithms and ant colony algorithms. The experimental results on 13 hard problems of benchmarks show that, the average agree- ment index increases 5.24% than parallel genetic algorithms, and increases 8. 40% than TSAB algorithm. The hybrid algorithm based on the algorithms combination strategy has high the search ability, which shows the validity of the hybrid strategy.

关 键 词：遗传算法 蚁群算法 混合算法 禁忌搜索算法 模糊加工时间 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置]