The Research Of Job-shop Scheduling Problems Based On Improved Genetic Algorithms

With the development of science and technology, the scale of modern production is becoming larger and more complex, the competition between companies is more intense, and this gives higher demands to enterprise management to suit to modern production. Job-shop scheduling is the core of enterprise management, and effective scheduling technology can not only intervene and adjust the production state, but also rationalize the allocation of resource to improve the production efficiency. Therefore, the researches and application of job-shop scheduling problems (JSP for short) have been the focus of academic and business. But, job-shop scheduling problems are combinatorial optimization problems with multi-constraint, multi-objective and random, known as NP-hard, and thus efficient scheduling algorithms for this kind of questions are the key of researches.Genetic algorithm (GA for short) which simulates the process of biological evolution is a kind of probability search algorithm, and is widely used in scheduling optimization because of its simple thought, implicit parallelism, versatility and robustness. GA has been the best solution methods for job-shop scheduling problems, but it has some shortcomings such as complex design for GA operators, slow convergence, and so on.Based on the mathematic model of job-shop scheduling problems, this paper made some improvements for GA from the designing of GA operation and the adaptive of GA parameters.Firstly, this paper went deep into the basic theory, discussed the implementation techniques of GA, designed a series of reasonable GA operations, and put forward new crossover operator and new mutation operator for the job-shop scheduling problems. The new crossover operator which makes some operation sequences between jobs unchanged from parent-chromosomes to child-chromosomes can preserve some good gene fragments for the population, and this makes the optimization ability of genetic algorithm better. The new mutation operator named neighborhood-inversion mutation which adds the neighborhood search of variation chromosome to the inversion mutation makes the search area of mutation bigger and the chromosome fitness after variation better. Therefore, the new crossover and mutation operators can speed up the evolution. Secondly, Adaptive is the important feature of GA, and this paper researched the adaptive of crossover probability and mutation probability under the individual level, and put forward two improved non-linear adaptive genetic algorithms (AGA for short) based on the linear AGA. The two improved algorithms which adopted the hyperbolic cosine function chx and the hyperbolic tangent function thx to adaptive genetic algorithms respectively were named Ch-AGA and Th-AGA for short, and they can make crossover probability and mutation probability non-linear changed with the individual fitness to improve the slow convergence of traditional linear adaptive genetic algorithms. The improved adaptive genetic algorithms were applied to solve the job-shop scheduling problems and the classical examples of Benchmark were used to prove the validity of the improved algorithms.Finally, the test platform for job-shop scheduling problems was designed on the Visual Studio.NET 2005 which took the improved GA as the core algorithms, and the GA procedure were compiled by VB.NET. The test platform which can achieve the functions of scheduling data store, GA running and result analysis provides a preliminary and common platform for algorithms and related issues to extend.