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

Abstract: 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.

Key words: scheduling, hybrid tabu search algorithm, reentrant, parallel machine, service equipment