Mining The Course Scheduling Data With Markov Chain

Since 1950's, the timetabling problem has become a frontier researchtopic in optimization and management science. In 1963, Gotlieb proposed thefirst timetabling model as a combinatorial optimization problem. And in 1975this problem was proved to be NP-complete by Even et al. Thus it would bedifficult to find any efficient global optimization algorithm. Since then morefocus has turned to efficient heuristic algorithms in this field.The manual solution of the timetabling problem consists in scheduling aset of lectures between instructors and students in a prefixed period of time.Grouping is an efficient strategy for solving such a multi-factor optimizationproblem. All courses are partitioned into groups by their ranking. Then thecombinatorial optimization algorithms are applied to solve each groupedsub-problem. It is usually considered that the course capacity is the dominantfactor in the ranking of the courses. The advanced administration systembrings much more complexity in the relations between courses. It allowsstudents to select courses in a considerably wide range. A course rankingmodel is proposed in this paper with Markov chain, and the conceptCourseRank is given. Results of mining the courses scheduling data ofTsinghua University during the period from Year 2001 to Year 2003 arepresented, which shows that the course capacity is an important factor, but notreally the dominant one.By analyzing and mining the course scheduling data, results in this paperform a solid base for the timetabling problem of further investigations.