Genetic Algorithm Research And Application In Scheduling System

In 1999, with the college expansion in China, the number of college students is continually increasing. Timetabling Problem is facing enormous challenges. On one hand, resources of teachers and classrooms are limited, on the other hand, Timetabling Problem plays an important role in teaching management at the college, which exerts direct impact on teaching quality and student education quality. Traditional way of Timetabling Problem cannot fulfill the needs of teaching management. Therefore, many experts and scholars try resolving Timetabling Problem using computer.Timetabling Problem is a problem about multi-restraints and multi-objective combinatorial optimization and has been proved to be a NP complete problem.Genetic Algorithm (GA) is a global optimization algorithm. GA was first introduced by J. Holland United States University of Michigan Professor in 1962, based on a simulation of the biological genetics theory and natural selection mechanism ,which improves the individual adaptation ,through the genetic operators of Selection,Crossover,Mutation .To some extent, GA is a mathematical simulation of biological evolution. It is a very effective algorithm to resolve NP-Completed combination optimization problem. Therefore, on the basis of the successful experience and the practical situation of my college, this thesis mainly discusses how to solve the timetabling problem using GA. This thesis first summarizes the theory of GA, then introduces the timetabling problem, at the same time describes the review of research on this problem at both home and abroad. Meanwhile this thesis analyzes the constraint rules- Red Line Rule and flexible Yellow Line Rule in the timetabling problems and also analyzes th influence of constraint rules on Optimal solution. At last, with the combination of our college, this thesis studies Chromosome encoding, designs Genetic operators, proposes method of calculating the fitness function, and determines algorithm to the Timetabling Problem and implements the simulation, which proves to be very efficient and a satisfactory way to solve timetabling problem.