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

Bo Peng, Zhipeng Lü, Edwin Tai Chiu Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

106 Citations (Scopus)


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 20 years.
Original languageEnglish
Pages (from-to)154-164
Number of pages11
JournalComputers and Operations Research
Publication statusPublished - 1 Jan 2015


  • Hybrid algorithms
  • Job shop
  • Metaheuristics
  • Path relinking
  • Scheduling
  • Tabu search

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this