Research And Application Of Course Scheduling System Based On Genetic And Tabu Search Algorithm

Curriculum arrangement is one of the most important and complicated problems in the school management.With more and more lessons,students and the limited resources in the classroom circumstances,it would be difficult in a short time to arrange the schedule which all teachers and classes were satisfied.It is a binding, multi-objective combinatorial optimization problem,and has been proved to be a NP complete problem.This thesis analyzes the nature of university curriculum problems,as well as the strengths and weaknesses of the problem solving.It also designs a model for the curriculum arrangement in the university.This model takes into account the general factors and constraints in the actual situation.As genetic algorithms are suitable for solving with many parameters,many variables,many goals and in many regions with poor connectivity NP-HARD problem.Optimize smart optimization algorithm,this thesis consider the use of genetic algorithms to solve the problem of arrangement,but the genetic algorithm has precocious phenomenon,it can quickly converge the local optimum rather than global optimal solution,so we combine the tabu search algorithm which is one of the local search methods.GA combined with TS to solve the problem has achieved good results.This thesis concludes the following research works:1.The system completely discusses the influence factors,the main constraints, objectives and difficulties of curriculum arrangement problem,and uses mathematical model to completely describe the curriculum arrangement.2.It designs the course scheduling system data structure and researches the algorithm various.3.It researches the chromosome coding,genetic operators and phase variation of tabu,to form a multi-objective optimization algorithm schedule. 4.This thesis use VS2005 for developing the model.SQL SERVER2000 is a good tool for the database implementation of the GA combining TS intelligent Timetable system.And the analysis data shows that the system is expected to meet the requirements with satisfactory results.