求解模糊Job Shop调度问题的改进禁忌搜索算法  

An Improved Taboo Search Algorithm for Fuzzy Job Shop Scheduling

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

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

出　　处：《沈阳建筑大学学报（自然科学版）》2006年第5期841-845,共5页Journal of Shenyang Jianzhu University：Natural Science

基　　金：国家科技攻关项目(2002BA107B0903)

摘　　要：目的提出一种改进的禁忌搜索算法,解决传统禁忌搜索算法优化效果对运行次数和初始解依赖的不足,提高这类问题的求解质量.方法根据模糊Job Shop调度问题解的特征,提出基于关键工序的邻域选择方法,采用此邻域选择方法构造禁忌搜索算法,当无邻域时,重新产生初始解进行禁忌搜索.结果采用改进的禁忌搜索算法对以13个难的benchmarks问题经模糊化得到的实例进行求解,得到的平均满意度8个优于TSAB算法,得到的最优满意度5个优于TSAB算法、4个与TSAB算法相同.结论采用基于关键工序的邻域结构构造的改进TS算法具有较强的搜索能力.An improved taboo search algorithm is. proposed to overcome shortcomings of traditional algorithms in which the results are dependent on the executed number of the algorithm and original solutions. According to the characteristics of the solutions, we propose a new method of neighbor selection based on the concept of a critical operation, and construct a new TS algorithm based on the neighbor selection. If there are no neighbors, the algorithm rebuilds the original solution and processes the taboo search. The experimental results on 13 hard problems of benchmarks, instances fuzzed, show that, the average agreement index of 8 problems is better than that of TSAB, the best agreement indexes of 5 problems are better than that of TSAB and that of 4 problems are the same as that of TSAB. The taboo search algorithm constructed by the neighbor selection based on the critical operation has high search ability.

关 键 词：禁忌搜索算法 模糊加工时间 JOB Shop调度 Giffler&Thompson算法 

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