Genetic Algorithm And Its Applications In Production Scheduling

Genetic algorithm (GA) is a stochastic search technique which simulates the process of biologic evolution. GA is fit for the large-scale, complicated optimized problems because of the abilities of self-organized, self-adaptive, self-study and populations evolution. GA expresses the solution to problems as the process of survival of the fittest. By the evolutionary processes, including reproduction, crossover and mutation, GA convergences to the individual that best fittest the circumstance and thus finds the optimal solution or satisfying solution. With the development of computer technology, GA attracts more and more attention and Genetic Algorithms have successfully applied to many fields such as machine learning, pattern recognition, neural network, optimal control and combinatorial optimization.Production Scheduling exists everywhere in the real word, especially in the field of industry and engineering. The production scheduling problems put forward by manufacturing are essentially extraordinary complexity and these are difficult to solve by traditional optimized methods. Scheduling problems which represent all the characteristics of constrained combinatorial optimization have become a pop theme in the domain of Genetic Algorithms and also exemplifications of testing the idea of new algorithms.In this paper we introduce the scheduling problems using genetic algorithm. We present a symbiotic genetic algorithm combined with models and verify the feasibility and efficacy through large numbers of experiments.The first section gives the overview of genetic algorithm and scheduling theory respectively. The biological foundation and a general framework of GA is given. The excellences of GA compare with other traditional methods are pointed out. The basic principles study, the algorithms design and the application fields of GAs are summarized. Then, the origin, development, classification ofscheduling problems and the existing techniques and respectively advantages and disadvantages are introduced.The problem to be solved in this paper is presented in the second section. A model which could conveniently describe the relations between operations in the flexible job-shop scheduling is adopted. For process planning and job-shop scheduling are highly related with each other, we put forward a framework of symbiotic genetic algorithm based on the idea of coevolution and hybrided with a heuristic approach. For the part of processes planning, we adopt the string coding based on the machine and selection sequence. As to the genetic operators, the single-point crossover and single mutation are adopted. For the part of Job-Shop scheduling, crossover and mutation operators are based on the sequence. The coding is based on the sequence of all operations of all jobs and the decoding hybrided with Giffler & Thompson Algorithm generates the final result.We verify the feasibility and efficacy of the proposed algorithm by lots of experiments for the difficulty of theoretic analysis and the complexity of the job-shop scheduling problem. The algorithm we proposed gets the better result and the running time is acceptable.A further research issue is discussed about solving the scheduling problem using genetic algorithm.