The Symmetrical Neighborhood Structure For Solving Flexible Job-shop Scheduling Problem

With the gradual transformation of customer needs to individualization and diversification,the market has increasingly higher requirements on enterprise production efficiency.Improving the efficiency of manufacturing logistics operation is an important aspect of improving enterprise production efficiency.The further research on FJSP can make contributions to enhancing the efficiency of manufacturing logistics operation,including improving logistics response speed and reducing costs.This study will explore the flexible job-shop scheduling problem(FJSP)based on tabu search and neighborhood structure analysis.First of all,in order to represent the solution of the FJSP intuitively,this article will use the solution graph to represent it,and at the same time,the concept of reverse solution graph,between the solution graph and its corresponding reverse solution graph.There is a symmetry relationship between the solution graph and the reverse solution graph,which provides the essential theoretical basis for the subsequent symmetry analysis of the neighborhood structure.Secondly,based on the symmetry property of neighborhood structure,this paper proposes a generic neighborhood structure,GNS.This neighborhood structure is compared with the existing six neighborhood structures of job-shop scheduling problem and the two neighborhood structures of FJSP.It is deduced through mathematical proof that GNS includes these six neighborhood structures of job-shop scheduling problems.In certain cases,GNS also includes the two neighborhood structures of FJSP.To a large extent,GNS has unified the above neighborhood structures,making them more relevant,and at the same time,the proofs related to the neighborhood structures above will be easier to understand.Thirdly,we have applied GNS to the tabu search algorithm,designed a comparative experiment based on this algorithm and selected three differently sized benchmark questions for testing.Experimental results show that the proposed tabu search algorithm based on GNS has faster efficiency and better solution quality when solving benchmark problems of different scales,confirming the effectiveness of GNS.Finally,the conclusions are summarized and the future research directions are prospected.