  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.
