Research On Job-Shop Scheduling Problem Based On Improved Genetic Algorithm

Job Shop Scheduling Problem is the key for enterprises to achieve high efficiency, flexibility and reliability production. The research on practical and effective scheduling method and optimization technology has become the basis of advanced manufacturing technology. Job Shop Scheduling Problem was deeply studied in this paper and the main contents were as follows:Chapter I:This chapter introduced the research background and significance of the paper, described the basic definition, features and main solving methods of the research object—Job Shop Scheduling Problem and research situation of Non-Flexible Job Shop Scheduling Problem and Flexible Job Shop Scheduling Problem. After the comparative analysis, genetic algorithm was adopted as the main methods of solving problems, and the basic principle of genetic algorithms was expounded.Chapter II:This chapter was based on improved genetic algorithm to solve Non-Flexible Job Shop Scheduling Problem. For small-scale problems, partition coding method, a kind of anti redundant encoding method, was proposed. Then full permutation of partition coding method was listed by dictionary ordered method. And the feasibility of all codes was evaluated by searching current process method. For large-scale problems, an improved genetic algorithm—partition genetic algorithm based on partition coding method was proposed. This algorithm can significantly reduce redundant codes, narrow searching space, and improve searching efficiency. Case-studies based on some typical benchmark-examples were carried out to evaluate the algorithm, and got results.Chapter III:This chapter was based on an improved genetic algorithm to solve Flexible Job Shop Scheduling Problem. Genetic algorithm step by step which achieved processing order after machine distribution was proposed, and avoided redundancy individuals and effectively reduced the search space. In order to clear the meaning of individual and avoid producing redundant codes, double-chain structure coding was used to code the chromosome. In order to maximum uniformly distribute the limited individual and ensure diversity, population was initialized with quasi level uniform design. An evolutionary ring was proposed in this chapter. Based on this idea, intrusion selection strategy and variable probability mutation strategy were proposed, which made evolution executes by stages, ensure algorithm accelerating convergence, and avoid early mature. Based on Theory of Constraint, optimize-bottleneck-crossover was proposed, which made crossover more purposeful. The algorithm was controlled with two rules based on extreme or current-optimal-fitness. Case-studies based on some typical benchmark-examples were carried out to evaluate the algorithm, and the results show a quick speed and powerful optimizing capability.Chapter IV:This chapter was based on Artificial Neural Network to design parameters of genetic algorithm. The chapter discussed the role of each parameter of genetic algorithm. BP neural network was adopted, which can achieve any nonlinear function with arbitrary precision. First, testing parameters were uniformly designed for different job shop scheduling problems. Through a lot of tests, the best parameter of each sample problem was obtained. Then based on the problem model, a BP neural network with a three-layer structure was constructed. This neural network proved its performance after sample studies, achieving the goal solving genetic algorithm parameters for intelligent design of different job shop scheduling problems.Chapter V:This chapter was the application of HTC Corporation Job Shop Scheduling case. The actual job shop scheduling situation was modeled. In order to solve the practical problem, the system was developed based on each algorithm of this article.Chapter VI Give the summary of the whole paper; list the innovation of the paper, and point out the direction for further research.