A Bidirectional Coupling Scheduling Decoding Method and Hybrid Algorithm for Job Shop Scheduling Problem

Aiming at the job shop scheduling problem(JSP), a bidirectional coupling scheduling decoding method and a hybrid genetic tabu search algorithm with multi-dimensional enhanced search are proposed to optimize the completion time. For the same coded individual, forward active scheduling decoding and reverse active scheduling decoding are carried out respectively, and then bidirectional coupling is carried out combining the head and tail length of the machine and the job. The bidirectional coupling scheduling decoding method can integrate the advantages of left-shift and right-shift of operations, make better use of idle time on the machine, and improve the quality of decoding. This decoding method is integrated into the hybrid algorithm of genetic algorithm and tabu search algorithm to solve JSP problem. In the process of local search, multiple decoding methods are used to decode a single individual, and then multiple individuals with better maximum completion time are obtained, and then tabu search is performed on these individuals to achieve multidimensional enhanced search for a single individual. The effectiveness of the algorithm is verified by testing the benchmark example of JSP problem.