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

An Improved Taboo Search Algorithm for Fuzzy Job Shop Scheduling

目的提出一种改进的禁忌搜索算法,解决传统禁忌搜索算法优化效果对运行次数和初始解依赖的不足,提高这类问题的求解质量.方法根据模糊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.