Abstract: Aiming at the job shop scheduling problem (JSP), an effective multi-operation joint movement neighborhood structure is proposed to optimize the maximum completion time. The neighborhood structure truly makes the blind search of the JSP solving algorithm more scientific and effective, and moving more operations simultaneously is the key to further improve the performance of the neighborhood structure. According to the neighborhood structure of exchanging 2 operations, it is theoretically analyzed how to perform multi-operation joint movement to optimize the maximum completion time. The shortcomings of existing multi-operation joint movement neighborhood structure are analyzed. A scientific and effective multi-operation joint movement neighborhood structure that exchanges up to 3 pairs of operations simultaneously is proposed. While exchanging the edge operations of the critical operation block, the job pre-ordering operation of the forward-moving operation is found according to the earliest start-up time, and the forward-swap is performed. The post-ordering operation of the backward-moving operation is found according to the latest start-up time, and the backward-swap is performed. A more general feasible solution guarantee condition for exchanging 2 operations is proposed. On this basis, the feasible solution conditions for the simultaneous exchange of 2 pairs of operations and 3 pairs of operations are extended. The JSP benchmarks are tested to verify that the proposed neighborhood structure has good performance and is of great significance for designing a more efficient JSP solving algorithm.

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