Research On Job Shop Scheduling Problem Based On Genetic Algorithm

As the time of global economy integration and knowledge economy is coming, the competition between enterprises will be more drastic. Many sequences and small quantity become the focal point of the market which manufactory racing to control.In order to increase their core capability of competition, enterprises must improve their inner production management, manufactories should be asked to range sequences rationally, take advantage of resource, shorten time limit for a project and reduce cost of producting. So people paid attention to the JSSP more and more.Job-Shop Scheduling Problem is the simple models of many actual Job-Shop Scheduling Problem, it is a typical NP-hard question. problem, and it is difficult to solve by regular method. In recent years, some intelligent algorithms have been used for it such s GA(Genetic Algorithm ) and SA(simulated annealling), heuristic algorithm, etc.As a method in evolutive computer field, GA is applied widely in parameter optimization such as global search. When it's applied in JSSP, there are several distinct merits compared with other methods. As an uncertain stochastic optimal algorithm, GA is applied in all kinds of fields in the past 20 years. And because of its independence, global optimization, and implicit parallelism in complex problem solving, GA is developed and applied in many fields by more and more people.In this paper, GA is applied to solve complicated shop floor scheduling problem. firstly, It introduces the methods and developments about job shop scheduling problem inside and outside, expatiates the basic conception and principle about genetic algorithm, and solving JSSP base on Genetic Algorithm.Secondly, In order to overcome the weakness of premature convergence in GA, a target of judgment premature degree in genetic algorithm is proposed, then an improved adaptive genetic algorithm which combining with simulated annealling algorithm is also proposed and applied in the job shop scheduling problem.At the last, an Partheno DNA Genetic Algorithm is studied. The Partheno DNA Genetic Algorithm that repeals the crossover operators of traditional genetic algorithms while uses the reproduction manner with only parent. The initial population of partheno DNA genetic algorithm need not be varied; there is no "immature convergence" of partheno DNA genetic algorithm and the searching efficiency is higher, so it was applied in the job shop scheduling problem.