Research On Multi-Objective Flexible Job Shop Scheduling Problem Based On Hybrid NSGA-?

Manufacturing industry is an important force to promote national economic development.As the intensification of the global market competition and the diversification of market demand,manufacturing enterprises not only need to improve product quality through advanced production and processing technology,but also need to introduce advanced management technology,and to find the best production methods for improving the production efficiency of enterprises.Reasonable and effective production scheduling strategy is a key technology for improving the management level of manufacturing enterprises because it can maximize the benefits of enterprises by maximizing the ability of resources.In the field of scheduling problem,flexible job-shop scheduling problem(FJSP)is an extension of the classic job-shop scheduling problem(JSP),and it reflects the flexibility of the job routes,that is,each operation can be processed by several different machines,and many kinds of operations can be assigned to one machine.Some objectives should be considered simultaneously in actual production,for example,it is important to meet the demand of delivery time by shortening the completion time of products,and it is necessary to reduce production costs by improving machine utilization as well.Therefore,multi-objective flexible job-shop scheduling(MO-FJSP)has attracted more and more attention of scholars in recent years.For MO-FJSP,the dissertation first studies the related constraints and objective functions of the problem,and establishes a mathematical model.Then,it is solved by using the reference-point based non-dominated sorting genetic algorithm(NSGA-?),which is one of the most advanced algorithms for solving multi-objective optimization problems.An effective neighborhood search is introduced to improve the NSGA-?.and its validity is verified by several standard benchmark instances.Finally,the prototype system for job shop scheduling problem is designed and developed based on the proposed hybrid NSGA-?.The above works actively explore the basic research of scheduling technology based on meta-heuristic algorithm.The main contents and achievements are as follows:(1)Through the analysis of the production process in the actual workshop,the constraints from equipment production capacity,process route and production calendar are sorted out.The makespan,total workload,and maximum workload are regarded as the optimization objectives for MO-FJSP,and then the mathematical model of theory and practical application is established.(2)To overcome the disadvantages of traditional optimization algorithms such as being easily trapped in local optima and having low convergence rates in solving MO-FJSP,a hybrid NSGA-III is proposed.In the hybrid algorithm,NSGA-III is adopted for global search,and neighborhood search is applied for local search.To improve the quality of the initial population,a heuristic initialization method for optimizing multi-objective is put forward.Four effective genetic operators are presented to maintain diversity of the solutions and to avoid premature convergence.To select the elitist solution from the population,the unique selection mechanism of NSGA-? is implemented.The neighborhood search method based on the critical path is utilized to refine the offspring population.In order to select the final scheme from the Pareto optimal solution set,a multi-objective scheduling strategy based on the improved NSGA-III normalization process is introduced.Finally,the internationally accepted benchmark MO-FJSP examples were used to test the validity of the proposed method.(3)A reasonable database structure is designed after the analysis for the time and space relationship of the three elements including equipment,job and production process involved in job shop scheduling.A scheduling prototype system,which mainly includes three modules:input and process of scheduling data,key parameters and constraint setting,and output of gantt charts,equipment load diagram and work order,is developed based on the hybrid NSGA-?.The system has faster calculation speed,simple operation interface and engineering application value.