模糊Job Shop调度中的混合搜索策略的研究  

Hybrid Search Strategy in Fuzzy Job Shop Scheduling

作　　者：宋晓宇[1] 朱云龙[1] 尹朝万[1] 李富明[1] 

机构地区：[1]中国科学院沈阳自动化研究所

出　　处：《信息与控制》2006年第3期382-387,共6页Information and Control

基　　金：国家973计划资助项目(2002CB312204);国家自然科学基金重点资助项目(70431003)

摘　　要：采用并行遗传算法作为全局搜索算法,提出一种混合搜索策略,用于求解模糊Job Shop调度问题.根据模糊Job Shop调度问题解的特征,提出基于关键工序的邻域选择方法,并将基于这种邻域选择方法的禁忌搜索算法作为局部搜索算法,加强了遗传算法局部搜索能力.针对13个困难benchm ark问题的实验结果表明,在较短的时间内,混合搜索策略的算法得到的平均满意度比并行遗传算法提高4.67%,比TSAB算法提高5.76%.采用的禁忌搜索算法改善了遗传算法的局部搜索能力,说明提出的混合搜索策略是有效的.*A new hybrid strategy is proposed for fuzzy job shop scheduling problems, which adopts parallel genetic algorithm as the global search algorithm. According to the characteristics of the Job Shop scheduling solutions, we propose a new method of neighbor selection based on the critical operation, and use a taboo search （TS） algorithm based on the neighbor selection as the local search algorithm. The local searching ability of genetic algorithm is enhanced. Experimental results on 13 hard problems of benchmarks show that, in a short time, the hybrid search strategy increases 4.67% on the average agreement index than that of parallel genetic algorithms, and increases 5.76% than that of Taboo Search Algorithm with Back jump tracking （TSAB）. The adopted taboo search algorithms improve the local searching ability of the genetic algorithm, proving the effectiveness of the presented hybrid strategy.

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

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