The Design And Implementation Of University Timetabling Based On Genetic Algorithm

Curriculum scheduling problem is a typical combination and optimization problem with multi-constraint and multi-objective, and has proved to be a Nondeterministic Polynomial(NP) completed problem. Curriculum scheduling problem not only involves in many factor, these factors also have interactive constraint and what’s more different schools have different case, which makes it hard to create a relatively stable pattern of curriculum scheduling. With the expansion of colleges and universities, to achieve automated and human curriculum scheduling with the help of compute software has become a consensus and also an ideal way to solve the scheduling problem.Genetic algorithm is a highly parallel and adaptive random search algorithm. It draws from biological mechanisms of natural selection and evolution. It is a very effective solution to NP-complete problem, as it has simple idea, robustness and easy to implement.In the thesis, GA is applied to solve curriculum scheduling problem. It start with the basic theory of GA. It describes the characteristics, implementing factors and the mathematics theories of GA and analyses the problem of some popular algorithm for curriculum scheduling at present. And then it discusses the main factor, constraint, target to solve and difficult of the curriculum scheduling problem,and also creates the mathematics model of the problem and proposes the architecture and technical route of the solution to curriculum scheduling problem. At last, it applies Pareto GA and by considering the characteristic of our school curriculum scheduling, it brings some improvements to the existing GA, that is it introduces a certain heuristic algorithm at the mutation step. It also tests the improved algorithm and the result shows that the algorithm improves the convergent rate as well as ensures the diversity of the population. At the process of the algorithm implementing, it considers conflicts detection and elimination, which effectively ensures the population diversity and avoids the population falling into the situation of local optimal solution.