Application Of Parallel Genetic Algorithm For The Dynamic Job Shop Scheduling Problem

Job shop scheduling system is the key of affiliation between manufacturing planning and production implementation. With the rapid pace of globalization and increasingly market competition, this problem has been concerned and researched on. Optimized scheduling programs can increase productivity on the existing resources, thereby improve the competitiveness of enterprises. Job-shop scheduling problem is also the model of battlefield repairing and other areas, and proved to be NP-hard. It is difficult to be solved by general optimization methods. So it has important practical significance for solving Job-shop scheduling problem.Genetic algorithm has been widely used to solve the current shop scheduling problem. It has been found that there are two main limitations of standard genetic algorithm, to be prone to convergence to a partial optimization and tends to convergence prematurely, when using traditional genetic algorithm, as well as a number of improvements of existing methods for solving the calculation. Parallel structures and multi-population methods are applied to compose an effective arithmetic. Grade evaluation and migration strategy which are presented in the new method can protect excellent chromosomes upgrading into the elite population, then increase crossover and mutation probability in the plain population so that more individuals can be generated. Migration strategy can solve the problem that diversity of population is apt to fall in the evolutionary process.Because of the uncertainty and dynamic nature of practical processing environment in workshop, research on the static job shop scheduling problem can no longer meet the real needs. The original scheduling solution is no longer suitable, once there are interferences in the process of manufacturing. The thesis focuses on the issue of dynamic scheduling problems to solve the re-scheduling problem when there are interferences. Modular dynamic scheduling system is presented in the thesis which can rewrite data, calculate and then generate the re-scheduling scheme when there are any dynamic events through the collaboration among dynamic database module, GA module and the program download module. The new scheme will link up with the old effectively by estimating the earliest access time of machine and the earliest processing time of the job being interrupted, so that the possible conflict can be avoid.The new method is applied to standard model of job-shop scheduling problem first to demonstrate effectiveness of the new algorithm by comparative experiments, it is applied to dynamic scheduling system to solve the scheduling problem when environment changes. The experimental results show that the new method and the dynamic scheduling system can solve the dynamic scheduling problem effectively.