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

为解决带有一台远程服务设备的可重入并行机调度问题,设计了一种混合禁忌搜索算法。针对传统禁忌搜索算法只从单起始点搜索、容易陷入局部最优等缺点,混合禁忌搜索算法设计了一种Restart策略。当传统禁忌搜索算法陷入局部最优时,用Restart策略重新产生初始解以进行禁忌搜索,将传统的禁忌搜索算法从单起始点搜索改进成多起始点搜索。数值实验中将混合禁忌搜索算法与启发式算法CS相比,结果表明该算法具有较高的求解质量,且其计算时间是可接受的。

Hybrid tabu search for scheduling reentrant jobs on parallel machines

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.