# A Tabu Search/Path Relinking Algorithm to Solve the Job Shop Scheduling Problem

arXiv: https://arxiv.org/abs/1402.5613 · HTML: https://mlsanity.com/paper/1402.5613/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2014.

## Built on by (most cited first, 2 of 2)

- [Attention-based Reinforcement Learning for Combinatorial Optimization: Application to Job Shop Scheduling Problem](https://mlsanity.com/paper/2401.16580/) (2024)
- [A new neighborhood structure for job shop scheduling problems](https://mlsanity.com/paper/2109.02843/) (2021)

## Abstract (arXiv)

We present an algorithm that incorporates a tabu search procedure into the framework of path relinking to tackle the job shop scheduling problem (JSP). This tabu search/path relinking (TS/PR) algorithm comprises several distinguishing features, such as a specific relinking procedure and a reference solution determination method. To test the performance of TS/PR, we apply it to tackle almost all of the benchmark JSP instances available in the literature. The test results show that TS/PR obtains competitive results compared with state-of-the-art algorithms for JSP in the literature, demonstrating its efficacy in terms of both solution quality and computational efficiency. In particular, TS/PR is able to improve the upper bounds for 49 out of the 205 tested instances and it solves a challenging instance that has remained unsolved for over 20 years.