The Research On Job-Shop Scheduling Based On The Elitist Non-dominated Sorting Genetic Algorithm

The research on the methods of the job-shop scheduling optimization and the technology of optimization has become the foundation and the key of the advanced manufacturing technology. In the manufacturing workshops, the scale of the scheduling problem is huge, involving the complicated objects, strong dynamic systems. Scheduling problem is a kind of combinatorial optimization problems,and it's also a typical NP problem.With the feature of computational complexity, dynamic binding and Multi-target, job-shop scheduling problems are proved to be typical NP difficult issues. In the fields of science and engineering, multi-objective optimization problems are hot issue, and also the difficult research. Because of the deficiencies of the traditional multi-objective optimization methods in certain complex multi-objective optimization problems, it is gradually substituted by some excellent multi-objective optimization algorithm. In the research areas of multi-objective ,the first generation of non-dominated Sorting Genetic Algorithm NSGA shows huge advantage.As the expanding of NSGA's application, its shortcomings constantly exposed. In order to solve the multi-objective optimization problem better, researchers raise the Elitist Non-dominated Sorting Genetic Algorithm (NSGA-Ⅱ) on the basis of the NSGA.The research on the NSGA-Ⅱboth in the theoretical area and applied area abroad are more in-depth,but less in the country . In this paper, the algorithm is researched and then applied to the actual job-shop scheduling problem.Because of the huge advantage of the NSGA-Ⅱin the areas of multi-objective optimization, it solves the multi-objective job-shop scheduling problem quite well.The main work in this paper:(1) The concept of the job-shop scheduling.the status quo and development trend are studied;the various methods for the job-shop scheduling problem are analyzed and compared;and the significance of this research and the main contents are also discussed.(2) The advantages and disadvantages of the genetic algorithm and non-inferior grade forefront of genetic algorithm (NSGA) are researched and analyzed in solving the multi-objective optimization problem. On the basis,the improved algorithm-NSGA with the elite strategy (NSGA-Ⅱ) are mainly researched. After comparing them , the advantage of NSGA-Ⅱin resolving the multi-objective optimization problem are summed up. The crossover and mutation operation are improved to avoid the slow convergence and the local optimum.(3) Because the multi-objective optimization of Job Shop Scheduling can not search the only optimal solution, so the mathematical model with the constrained conditions is established. Program in MATLAB language is compiled based on the the NSGA-Ⅱwith elite. And the forefront of the non-inferior grade, pareto optimal solution and Niche Matlab code are given.In the process of debugging through MATLAB7.0.1, the data shows that NSGA-Ⅱwith the elite strategy is better than the average multi-objective optimization algorithm in solving multi-target optimization problems.(4) Under the consideration of the shortest delivery time, the minimum cost of production and the balanced equipment load,the relevant models are established and NSGA-Ⅱis used to solve the problem of the integration of multi-process routes and multi-target scheduling.Finally,the optimum process route and the scheduling result come out together.Through examples analysis to prove that this method can effectively achieve the goals of the integration of multi-process routes and multi-target scheduling.