An Improved Genetic Algorithm And Its Application To Job Shop Scheduling

Genetic algorithm has strong applicability and robustness and it also does not depend on the specific problem areas. It is an open algorithm, so it is easy to combine with other algorithms to get a better algorithm which has better performance. According to these, the genetic algorithm is selected generally to solve NP-Hard problems such as job-shop scheduling problems.In the study of genetic algorithm for job-shop scheduling problems, the author encounters the problems that the genetic algorithm has the slow rate in convergence and premature convergence. After in-depth analysis and experiments, the reason is found and it is caused by the algorithm's local circuitous search and sensitivity to initial parameters. Directed against the shortcoming of the genetic algorithm such as the slow rate in convergence and premature convergence, this paper improves the genetic algorithm with tabu search algorithm and the strategy that adjusts the algorithm parameters adaptively and dynamically. By putting the tabu search to the process of the genetic algorithm, the improved genetic algorithm succeeds in avoiding circuitous search, promotes the rate in convergence and avoids disadvantages such as premature convergence. And the algorithm speeds up the overall convergence rate directly. The algorithm parameters adaptive strategy tries to adjust the algorithm's crossover probability and mutation probability dynamically according to the evolution of the algorithm's populations. The improved algorithm reduces the algorithm's accuracy depending on the initialization parameters and solves the initial value of the sensitivity issues. By comparing the solution result with the current pop algorithm, the simulation experiments demonstrate that the proposed improved genetic algorithm has higher reliability and better performance.On the other hand, the improved algorithm is used on the job-shop scheduling. The various links of the improved genetic algorithm and a detailed description of the entire process are then given for solving job scheduling according to the improved genetic algorithm. And a job-shop scheduling system model is designed and implemented based on the improved genetic search algorithm. Through the experiments with the implemented model, it further demonstrates the effectiveness of the improved algorithm.