Algorithm Research And Application Of University Timetable Problem

University Timetable Problem (UTP) is a typical combination optimization problem and uncertain management problem, which is applied widely. UTP has been proved a NP-completion problem. With the enlargement of the university and the deepening of the teaching management information, the tranditional way, arranging course by hand, and the way by using computer assistant could hardly meet the current requirement. The antomatic course arranging system, for its inherent high difficulty and complicacy, its research and realization are very important for the whole network teaching management system. In this paper, with the thought of dynamic programming, a mixed algorithm is proposed to solve this problem. And an automatic course arranging system is designed and realized by using this algorithm in the following.This paper introduces the development, main factors, constraints and mathematic model of university timetable problem first. Then it expounds a mixed algorithm which divides the course timetabling problem into two phases, arranging time by intelligent algorithm and arranging classroom by best fit algorithm, and gets the whole solution by resolving each phase of the problem. In the following, compared the mixed algorithm with classical genetic algorithm, it shows the mixed algorithm at the same time of ensuring the quality of result, reduces the complicacy, have a better performance and expansibility.After that, the database table and sub modules are designed based on the mixed algorithm and requirement, the intergration with other sub system of teaching management system is also considered. The detailed realization and the key technique are then explained by using the combination of text and diagram.Finally, it summarizes the research work, also analyzes the present problems and the work in future.