Abstract: Aiming at the job shop scheduling problem(JSP), a hybrid algorithm of path relinking and tabu search is proposed to optimize the maximum completion time. Combining with JSP domain knowledge to design path relinking, the forward and reverse non-delay scheduling solutions are taken as the guiding solutions respectively. There is no available idle time on the left and right side of each operation respectively corresponding to the forward and reverse non-delay scheduling Gantt chart. A forward non-delay scheduling conversion algorithm based on operation head length of the current solution is proposed. A reverse non-delay scheduling conversion algorithm based on operation tail length of the current solution is presented after reversing the job process route. A new backtracking tabu search algorithm based on elite solutions is designed, which can make full use of the historical solutions information in the iterative evolution process. Not only the updated current optimal solution is extracted and added to the elite solution set, but when the number of consecutive non-update iterations of the optimal solution reaches the set value, the better current solution in the interval generations is extracted and added to the elite solution set. The continuous replenishment and dynamic update of the elite solution pool are realized, so that the algorithm can continuously carry out backtracking search. The neighborhood structure with a wider operation moving range is adopted. The path relinking and tabu search algorithm are mixed to test the JSP benchmarks to verify the effectiveness of the proposed algorithm.

Key words: job shop scheduling, tabu search algorithm, path relinking, non-delay scheduling, maximum completion time