Research And Application On Job Shop Scheduling Problem Based On Improved Genetic Algorithm

Job Shop Scheduling Problem (JSP) as an important part of Computer Integrated Manufacturing System (CIMS) engineering is indispensable, and has vital effect on production management and control system. In the competion ecvironment nowadays, how to use the assignments quickly and to plan production with due consideration for all concerned has become a great subject for many manufactory.Through the research on mathematics model of JSP and optimized algorithm, the improved adaptive genetic algorithm (IAGA) obtained by applying the improved sigmoid function to adaptive genetic algorithm is proposed. And in IAGA for JSP, the fitness of algorithm is represented by completion time of jobs. Therefore, this algorithm making the crossover and mutation probability adjusted adaptively and nonlinearly with the completion time, can avoid such disadvantages as premature convergence, low convergence speed and low stability. Experimental results demonstrate that the proposed genetic algorithm does not get stuck at a local optimum easily, and it is fast in convergence, simple to be implemented. Several examples testify the effectiveness of the proposed genetic algorithm for JSP.Meanwhile, based on the good characteristics of genetic algorithm (GA) and simulated annealing algorithm (SA) in achieving near optional solution of this problem, a hybrid algorithm (GASA) which combines GA and SA is proposed for the solution of JSP. GASA with the advantage of GA's local searching and SA's whole searching can increase the diversity of individuals in population and robust of algorithm. At last, the simulation results show the feasibilities and availabilities of GASA and show that GASA can improve the deficiencies of GA and SA in the optimization on JSP.Finally, the job shop scheduling system based on IAGA and GASA is designed and realized, and the functions and operations of the system modules are introduced detailedly. The scheduling results obtained by applying the scheduling system to benchmark and a practice problem satisfy the requirements and show the feasibilities and availabilities of IAGA and GASA further.