Affordable Access

Publisher Website

A tabu search/path relinking algorithm to solve the job shop scheduling problem

Computers & Operations Research
DOI: 10.1016/j.cor.2014.08.006
  • Scheduling
  • Job Shop
  • Metaheuristics
  • Tabu Search
  • Path Relinking
  • Hybrid Algorithms
  • Computer Science


Abstract We present an algorithm that incorporates a tabu search procedure into the framework of path relinking to generate solutions to the job shop scheduling problem (JSP). This tabu search/path relinking (TS/PR) algorithm comprises several distinguishing features, such as a specific relinking procedure to effectively construct a path linking the initiating solution and the guiding solution, and a reference solution determination mechanism based on two kinds of improvement methods. We evaluate the performance of TS/PR on 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 20years.

There are no comments yet on this publication. Be the first to share your thoughts.