A guided tabu search/path relinking algorithm for the job shop problem

The job shop scheduling problem with makespan criterion is valuable from both practical and theoretical points of view. This problem has been attacked by most of the well-known meta-heuristic algorithms. Among them, tabu search has emerged as the most effective approach. The proposed algorithm takes advantages of both N1 and N6 neighborhoods. N1 neighborhood is used as a path relinking procedure while N6 neighborhood with its guideposts is applied in a tabu search framework. In addition, a method is presented for updating the topological order, heads and tails in N6 neighborhood. The algorithm is tested on standard benchmark sets, outperformed all previous approaches (include i-TSAB) and found six new upper bounds among the unsolved problems. Furthermore, we have tried to collect the newest upper bounds for the other problems.