Abstract: Aiming at the job shop scheduling problem（JSP）, a hybrid algorithm based on obstacle graph model and tabu search is proposed to optimize the maximum completion time. In the obstacle graph model, an effective path search algorithm is designed which scientifically inserts the removed jobs into schedule, and then the job-level search is achieved. In the tabu search algorithm, the neighborhood structure is utilized to realize the moving operations search. By mixing the two algorithms, the collaborative search on job-level and operation-level scales is realized. When an algorithm falls into local optimum, solution from the neighborhood solutions of the current algorithm is selected and inputted into the computing of another algorithm, and the two algorithms cooperate to get high quality solutions. The effectiveness of the proposed algorithm is verified by JSP benchmark instances test. By studying the characteristics of the path of obstacle graph, a new node expansion method is designed, which can not only find the shortest path of obstacle graph, but also provide a reference for other path search methods. At the same time, the proposed hybrid algorithm can also be regarded as an effective algorithm framework.

Key words: job shop scheduling, obstacle graph model, tabu search algorithm, path planning, maximum completion time