Research On University Timetable Problem Based On Modified Genetic Simulated Annealing Algorithm

Timetable problem is one of the most important and complicated issue in academic administration of university. Solving the issue is conductive to accelerate the process of the education informationization, overcome the disadvantages of manual course-arranging, and overcome the status quo of the inconsistency between the rarity of education resource and the abundance of students in our country.Timetable Problem is a multi-objective combination optimization problem with constraints, which is the study of how to allocate limited time to multiple events, and also has been proved NP-Completed. In order to effectively solve the problem, what this paper finished mainly work as follows:Firstly, based on full understanding of the principles of timetable, the paper carries on demand analysis to timetable problem. All kinds of potential factors, multi-restrictions of timetable problem are discussed. And the mathematic model of multi-objective combination optimization about timetable problem is designed.Secondly, the main algorithms of timetable problem are researched. Based on the research of GA(Genetic Algorithms) and SA(simulated Annealing Algorithms),the paper analyses the timetable problem based on GA and find some deficiencies,then puts forward the improved strategies to mend them. On the one hand, the genetic operators of genetic algorithm are improved. Self-adapting theory and the strategy of keeping the best individual are embedded into GA. On the other hand, the improved GA referenced SA algorithms. This combines excellent parallelism and global search of GA with the probabilistic jumping property and local search of SA algorithm.Thirdly, combined with the mathematic model about timetable problem, a kind of coding scheme is designed. An automatic curriculum scheduling system based on the improved algorithm is realized on the windows platform using Vsiaul C++6.0.Finally, real data and example are used to test this improved algorithm in the application of timetable problem, and the result is satisfying in the way of improved algorithm's performance by contrast experiments.