Abstract: In order to optimize the maximum completion time, a hybrid solving method with a new neighborhood structure is proposed for the job shop scheduling problem (JSP). In the hybrid algorithm, genetic algorithm is adopted for global search, and local search is achieved based on neighborhood structure. In the design of the neighborhood structure, the calculation method of operation head and tail length, and the key operations searching method are studied based on Gantt chart. Through the analysis of various neighborhood structures and related theories, it points out that the foundation of neighborhood structure is to guide the key operations to utilize machine idle time, and can be divided into two types direct use and indirect use. The two utilization ways are both comprehensively considered, and the corresponding movement strategies are defined according to the type of key operations with scientific guidance. The effective movement range is expanded, breaking through the location restrictions of inside, direct adjacent before and behind of the operation block. The experimental results of 43 benchmarks show that the proposed algorithm has good performance. In addition, the new neighborhood structure can further be integrated with other intelligent algorithms for solving JSP problem.

Key words: genetic algorithm, job shop scheduling problem, local search, makespan, neighborhood structure