Research On Job Shop Scheduling Method Based On Gene Expression Programming

With the rapid development of advanced manufacturing technology,shop scheduling has become the key to achieve intelligent production,which plays an important role in improving production efficiency and reducing enterprise production costs.Job shop scheduling problem is a very common scheduling problem in actual production,and it is also a typical NP-hard problem,its research has not only theoretical value,but also important application value.Gene Expression Programming(GEP)can generate and express programs and rules,which can be used to construct heuristic methods to solve problems.This paper will study and improve the GEP,and used the improved GEP to construct dispatching rules to solve job shop scheduling problem,including classic job shop scheduling problem,distributed job shop scheduling problem and multi-objective job shop scheduling problem.Firstly,the standard GEP is improved.By improving the selection method,designing adaptive genetic operator and new solution acceptance criteria,improving the threshold setting method of outbreeding strategy,and using iterative local search for the generation of new individuals in the strategy,the GEP is improved.Combined with the idea of hyperheuristic algorithm,a shop scheduling framework based on the improved GEP is proposed.Secondly,a job shop scheduling method based on the improved GEP is proposed.According to the characteristics of job shop scheduling problem,the corresponding chromosome structure is designed,the appropriate neighborhood structure,function set and terminal set are selected,and the improved GEP is used to solve the problem.Through comparative experiments,the effectiveness of the proposed algorithm is verifiedThirdly,a distributed job shop scheduling method based on the improved GEP is proposed.According to the characteristics of distributed job shop scheduling problem,the chromosome structure is designed,the function set and terminal set suitable for the problem are selected,the improved outbreeding strategy based on iterative local search is adjusted,and the improved GEP is used to solve the problem.Numerical experiments and comparative analysis verify that the proposed method has the best performance.Then,a multi-objective job shop scheduling method based on the multi-objective improved GEP is proposed.Combined with the multi-objective optimization theory,the fast non-dominated sorting and crowded distance sorting of NSGA-Ⅱ are introduced into the improved GEP,and the new solution acceptance criteria and the improved outbreeding strategy based on iterative local search are adjusted to be suitable for multi-objective optimization,and the multi-objective improved GEP is used to solve multi-objective job shop scheduling problem.Numerical experiments and comparative analysis verify that the proposed algorithm is superior to the comparison algorithms.At the end of the paper,the research work is summarized,and the future research directions are prospected.