Research And Implementation On JSP Based On Improved Genetic Algorithm

JSP (Job shop problem) is a typical NP-hard problem, which means that it is impossible to find the global optimum in polynomial complexity. GA (Genetic Algorithm), as a current optimized algorithm, has been used widely for the JSP. While solving JSP, GA displays the very strong applicability, but the optimized capability of GA is dependent on the heredity parameters strongly, especially the crossover rate and the variation rate. The unfitness parameters usually make the optimized capability of GA to give discount greatly. For searching the GA superior parameter, there are many thorough researches, but these researches usually launch from the engineering background and the engineering application, few of which commence from the GA foundation mathematical model. To solve the problem more effectively, a lot of researchers have improved the traditional GA and also added the heuristic theory into GA, which has become popular. In this paper, a Virus Evolutionary Genetic Algorithm (VEGA) and a Partheno Genetic Algorithm (PGA) are respectively proposed for JSP.To overcome the disadvantages of prematurity and slow convergence in genetic algorithm, a new Improved Virus Evolutionary Genetic Algorithm (IVEGA) was designed. IVEGA searches the solution space in both depth and width. In the algorithm, we added a knowledge-base of host chromosome into the genetic process and introduced another knowledge-base of virus chromosome into the virus infection process, which has avoided the loss of the excellent solution and shrunk the searching space by using learning theories. Besides, an encoding method based on integer is presented which can avoid noneffective chromosomes for problem that switch solutions to chromosomes and reverse the transformation easily. The results in solving the eleven classical Benchmarks problem showed the effectiveness of the new algorithm.Considering the deficiency of Traditional Genetic Algorithm (TGA) in solving Job Shop Scheduling Problem, such as the difficulty to ensure the superior parameters and "immature convergence", A PGA based on integer coded was formulated to solve the Job Shop Scheduling Problem. This improved algorithm brought a single individual group during the evolution process, and the crossover operator of TGA was cancelled. The algorithm caught through a single chromosome, and inherited the characteristic of GA, such as genetic iterative. Emulation results which involved three different sizes FT problems show that the method convergence expedited as size extended, and also can give good stable solutions for solving job shop problems.