A tabu search/path relinking algorithm to solve the job shop scheduling problem. (January 2015)

• Record Type: Journal Article
• Authors: Peng, Bo; Lü, Zhipeng; Cheng, T.C.E.
• Is Part Of: Computers & operations research. Volume 53(2015)
• Page Start: 154
• Page End: 164
• Publication Date: 2015-01
• Subjects: Scheduling -- Job shop -- Metaheuristics -- Tabu search -- Path relinking -- Hybrid algorithms; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2014.08.006
• Languages: English
• ISSNs: 0305-0548

Abstract

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.