求解可重入并行机调度的混合禁忌搜索算法  

Hybrid tabu search for scheduling reentrant jobs on parallel machines

作　　者：赵月[1] 胡玉梅[1] 

机构地区：[1]天津大学理学院,天津300072

出　　处：《计算机应用》2012年第9期2451-2454,共4页journal of Computer Applications

基　　金：国家自然科学基金资助项目(11001196)

摘　　要：为解决带有一台远程服务设备的可重入并行机调度问题,设计了一种混合禁忌搜索算法。针对传统禁忌搜索算法只从单起始点搜索、容易陷入局部最优等缺点,混合禁忌搜索算法设计了一种Restart策略。当传统禁忌搜索算法陷入局部最优时,用Restart策略重新产生初始解以进行禁忌搜索,将传统的禁忌搜索算法从单起始点搜索改进成多起始点搜索。数值实验中将混合禁忌搜索算法与启发式算法CS相比,结果表明该算法具有较高的求解质量,且其计算时间是可接受的。A hybrid tabu search algorithm was proposed in this paper for the reentrant scheduling problem on parallel machines with a remote service equipment. Concerning that only one start-point was used in the traditional tabu search algorithm which made it trapped in local optimum easily, a Restart method was established in the hybrid tabu search algorithm. When the traditional tabu search algorithm was trapped in local optimum, the Restart method was used to rebuild the initial solution and preceded with the tabu search algorithm. Thus, the traditional single start-point search was changed into multiple start-points search. Comparisons were made between the hybrid tabu search algorithm and a Coordinate Scheduling （CS） algorithm. The computational experiments show the effectiveness of the hybrid tabu search algorithm, whose optimization performance is superior to the CS algorithm. Moreover, the computation time is acceptable.

关 键 词：调度 混合禁忌搜索算法 可重入 并行机 服务设备 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP18[自动化与计算机技术—计算机科学与技术]