Study On Job-Shop Scheduling Problem By Genetic Algorithm And Artificial Immune Algorithm

With the development of the market economy, the market is becoming more and more competitive. Manufactories should range sequences rationally, take full advantage of resource, and reduce the duration and production costs. So people pay more attention to the Job Shop Problem (JSP). JSP belongs to NP-hard problem; it is the hardest solving problem of typical optimization problems.Because genetic algorithm is universal and simple, it is widely applied in the optimization of JSP. However, it is just the universal property that leads to badly flexibility. Although it can guarantee its entire convergence because of the simple algorithm, it brings the problem of premature convergence in the practical apply. In another word, few individuals' fitness are bigger than others in the process of evolution, and these individuals can occupy the entire group after few times reproductions. Artificial immune algorithm is one of the results that natural immune system mechanism is applied to optimization calculation. The algorithm adopt a adaptive selection mechanisms based on fitness and concentration, which can effectively promote good antibodies reproduction, suppress antibodies of high concentration, keep diversity of antibodies, improve the fitness of individual species and prevent degradation of population, avoiding the local convergence. However, the frequent extracting and injecting vaccines can increase the complexity of algorithm.Considering the strengths and weaknesses of the above two algorithms, a choice mechanism is introduced in this disseration. Some jobs have been done in the following aspects:Firstly, because crossover algorithm plays a key role in genetic algorithm and a good crossover algorithm can improve the evolution speed of popution; a new three-individuals cross algorithm is proposed. Secondly, the method of extracting and injecting vaccines is designed in the artificial immune algorithm, which is based on gene segments of processing machine by using extracting vaccines and injecting vaccines to the finally completed machine.Thirdly, a selection mechanism is introduced in the research of population premature convergence capability. If the population has high diversity, genetic algorithms is applied, on the contrary, artificial immune algorithm is applied.Finally, the new alogorithm in this disseration is compared with the old from the optimal solution, time efficiency and algorithm astringency by testing standard data sets.