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 20 years.
Original language | English |
---|---|
Pages (from-to) | 154-164 |
Number of pages | 11 |
Journal | Computers and Operations Research |
Volume | 53 |
DOIs | |
Publication status | Published - 1 Jan 2015 |
Keywords
- 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