Research Of Course Timetabling Based On Iterative Forward Search Algorithm

Timetabling problem belongs to a class of optimization problem for multiple constrained resources scheduling. There are a wide range of application areas, like flight scheduling and city highway scheduling. It has been proven that Timetabling is a kind of NP-completed problem and the algorithm with polynomial time complexity does not exist. Course scheduling is one of the most important application to this Timetabling problem.With the development of the higher education, requirements of the quality of instructional in universities of China is more and more high, And the scale of course scheduling has become more and more large. Moreover, course scheduling is a key factor in academic management, and it has a great influence on the student learning and the improvement of teaching quality. However, the existing scheduling method in China is increasingly unable to meet the demand. Iterative Forward Search Algorithm is a new kind of heuristic algorithm, which has been put forward recently.It has been widely used in some foreign universities for course timetabling, but there is little related work in China. In this thesis, based on the detailed analysis of this advanced algorithm, we present the corresponding improvement.The main contributions are as follows:① The factors, Constraints, related timetabling algorithms have been completely discussed in this thesis and Iterative Forward Search Algorithm’s theory and mathematical model are studied in detail.② Combined with the actual situation of domestic universities, we suggest a Constraint improved Iterative Forward Search Algorithm based on Dynamic Backtracking MAC. It not only solves the teacher scheduling problem across multiply campus and the teachers’ personal demand of instructional time, but also improves the Algorithm’s performance while facing large-scale course scheduling. ③ To Design and implement the architecture of the Algorithm.④ To Use the real-life course datasets of ChongQing University to perform two-step experiments. Then the performances and the fitness of domestic Universities of the Algorithm based on the experiment’s results are analyzed.