Abstract: Aiming at the job shop scheduling problem(JSP), a search-enhanced multi-operation joint movement neighborhood structure and approximate evaluation method is proposed to optimize the maximum completion time. The idle time utilization mechanism of the transpose of two operations on the edge of the critical operation block is analyzed, and the idle time boundary range of the existing multi-operation joint movement neighborhood structure is effectively extended. While exchanging the two operations on the edge of the critical operation block, based on the extended idle time boundary range judgment condition, to find a job pre-operation of the forward operation according to the earliest start-completion time, and exchange it with the immediately adjacent machine pre-operation. According to the latest start-completion time, to find a job post-operation of the backward operation, and exchange it with the immediately adjacent machine post-operation. The new multi-operation joint movement neighborhood structure can make full use of the adjacent idle time of the original critical operation block and the idle time formed by the moving operations as much as possible, thereby achieving a more enhanced search. Based on the operation head and tail length theory, an approximate evaluation method for multi-operation joint movement neighborhood is studied. The JSP benchmarks are used to test, and the results verify the effectiveness of the strengthening multi-operation joint movement neighborhood, and the proposed approximate evaluation method has high accuracy. As the basic research of JSP problems, neighborhood structure and approximate evaluation are of great significance for JSP to achieve effective solving that combining knowledge of problem characteristics.

Key words: job shop scheduling problem, multi-operation joint movement, neighborhood structure, approximate evaluation, maximum completion time