A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem

A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem

0.00 Avg rating0 Votes
Article ID: iaor20083729
Country: United Kingdom
Volume: 34
Issue: 11
Start Page Number: 3229
End Page Number: 3242
Publication Date: Nov 2007
Journal: Computers and Operations Research
Authors: , , ,
Keywords: heuristics: tabu search
Abstract:

Tabu search (TS) algorithms are among the most effective approaches for solving the job shop scheduling problem (JSP) which is one of the most difficult NP-complete problems. However, neighborhood structures and move evaluation strategies play the central role in the effectiveness and efficiency of the tabu search for the JSP. In this paper, a new enhanced neighborhood structure is proposed and applied to solving the job shop scheduling problem by TS approach. Using this new neighborhood structure combined with the appropriate move evaluation strategy and parameters, we tested the TS approach on a set of standard benchmark instances and found a large number of better upper bounds among the unsolved instances. The computational results show that for the rectangular problem our approach dominates all others in terms of both solution quality and performance.

Reviews

Required fields are marked *. Your email address will not be published.