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

Improved taboo search algorithm for Job Shop scheduling problems

作　　者：宋晓宇[1] 孟秋宏[1] 曹阳[1] 

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

出　　处：《系统工程与电子技术》2008年第1期93-96,共4页Systems Engineering and Electronics

基　　金：国家重点基础研究项目资助课题(2002CB312204)

摘　　要：提出一种改进的禁忌搜索算法,解决传统禁忌搜索算法优化效果对运行次数和初始解依赖的不足,提高这类问题的求解质量。根据Job Shop调度问题解的特征,提出基于关键工序的邻域选择方法,采用此邻域选择方法构造禁忌搜索算法,当无邻域时,重新产生初始解进行禁忌搜索,将传统的禁忌搜索算法从单起始点搜索改进成多起始点搜索。采用改进的禁忌搜索算法对13个难的benchmarks问题进行10次求解,得到的平均值8个优于TSAB算法,得到的最优解6个优于TSAB算法、4个与TSAB算法相同。采用基于关键工序的邻域结构构造的改进TS算法具有较强的搜索能力。An improved taboo search algorithm is proposed to overcome shortcomings of traditional TS algorithm, in which the result depends on the executed number of the algorithm and initial solutions. According to the characteristics of the solutions, a new method of the neighbor selection based on the concept of a critical operation is proposed, and a new TS algorithm based on the neighbor selection is constructed. If no neighbors, the algorithm rebuilds the initial solution and proceeds with the taboo search. Thus, the traditional single startpoint search is changed into multiple start-point search. The 10 times experimental results about 13 hard problems of benchmarks show that, the makespan averages of 8 problems are better than that of TSAB, the optimal values of 6 problems are better than that of TSAB and that of 4 problems are same as that of TSAB. So, the taboo search algorithm constructed by the neighbor selection based on the critical operation has high search ability.

关 键 词：禁忌搜索算法 JOB Shop调度 Giffler&Thompson算法 

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