An Improved Tabu Search Algorithm for Parallel Task Scheduling on Identical Machines

Abstract

Abstract Aiming at the parallel task scheduling problem (P |sizej|Cmax), which requires multiple machines to work collaboratively, this paper proposes an improved tabu search algorithm to overcome the shortcoming of traditional methods being prone to falling into local optima. Firstly, a hybrid neighborhood structure combining swap and insertion operations is designed to enhance search diversity and local optimization capabilities. Secondly, a dynamic tabu length adjustment mechanism is introduced to adaptively change the cycle of tabu objects according to the search process, thereby achieving a balance between breadth and depth of search. Finally, a simplified aspiration criterion is proposed to avoid the loss of high-quality solutions caused by excessive tabu. Extensive computational experiments on randomly generated test instances show that the designed algorithm achieves highly competitive performance compared with the original tabu search algorithm and the OR-Tools solver, while significantly improving computational efficiency. In particular, the proposed method reduces the average Cmax by approximately 10.6% on extra-large-scale instances, demonstrating superior solution quality and robustness.