An improved tabu search approach for efficient job-shop scheduling

An improved tabu search (ITS) algorithm for the job shop scheduling problem (JSP) that assigns jobs to machines to minimize the makespan and optimize task sequences. Conventional tabu search (TS) often suffers from local stagnation when solving complex JSPs, leading to high computational costs and inefficient scheduling. To overcome these limitations, the proposed ITS incorporates an insertion-based initialization to generate high-quality starting solutions. It combines a disjunctive graph model with an N5 neighborhood structure to enhance search depth and improve scheduling accuracy. In addition, a Lévy flight perturbation mechanism is introduced to strengthen global exploration and prevent premature convergence. The ITS was evaluated on ten benchmark JSP instances; the results demonstrate that it outperforms existing state-of-the-art algorithms and ITS variants in terms of convergence accuracy, schedule compactness, and resource utilization efficiency. Overall, the findings confirm that ITS provides a robust and practical approach to solving complex JSPs, both small- and large-scale.