A Bidirectional Coupling Scheduling Decoding Method and Hybrid Algorithm for Job Shop Scheduling Problems
Liu Zihui
Zhao Shikui
Abstract：For the job shop scheduling problem(JSP),a bidirectional coupling scheduling decoding method and a hybrid genetic-tabu algorithm with multi-dimensional enhanced search are proposed with the objective of minimizing the makspan.For the same coded individual,forward and backward active scheduling decoding are performed respectively,and then bidirectional coupling is carried out combining the head-tail lengths of machines and jobs.The proposed method integrate the advantages of left-shift and right-shift operations,enabling more effective utilization of machine idle time and improving decoding quality.This decoding method is integrated into the hybrid algorithm of genetic and tabu search algorithms to solve the JSP.In the process of local search,multiple decoding methods are used to decode a single individual to generate multiple individuals with potentially improved makespan.These individuals are then further optimized through tabu search,achieving multidimensional enhanced search for single individuals.The effectiveness of the algorithm is verified by testing benchmark examples of JSP.
Keywords：job shop scheduling problemdecoding methodgenetic algorithmTabu search
Publication Date：2026-02-28
Online Publishing Date：2026-03-19(First online date of this platform, not the publication date of the document)
Pages：14( 164-177 )