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

采用并行遗传算法作为全局搜索算法，提出一种混合搜索策略，用于求解模糊Job Shop调度问题．根据模糊Job Shop调度问题解的特征，提出基于关键工序的邻域选择方法，并将基于这种邻域选择方法的禁忌搜索算法作为局部搜索算法，加强了遗传算法局部搜索能力．针对13个困难benchmark问题的实验结果表明，在较短的时间内，混合搜索策略的算法得到的平均满意度比并行遗传算法提高4.67%，比TSAB算法提高5.76%．采用的禁忌搜索算法改善了遗传算法的局部搜索能力，说明提出的混合搜索策略是有效的．

Hybrid Search Strategy in Fuzzy Job Shop Scheduling

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.