排课问题分组优化决策中的CourseRank

CourseRank in the grouping strategy of course scheduling problems

时间表(T im etab ling)问题是NP-完全的,因此很难寻求一个有效的整体优化算法.分组作为重要的优化策略,可以将课程按优先等级逐次分组,每组再采用组合优化方法.通常认为课程的规模是优先等级的决定性因素.然而选课的模式允许学生在一定的范围内选择课程,这就使得课程的关联关系更复杂.该文将课程的关联关系描述为一个M arkov链,进而给出了课程优先度(CourseR ank)的概念.通过对清华大学2002年度学生选课数据的分析和计算,结果表明课程的规模仍然是重要的因素,但并不完全是决定性的.

Course scheduling is an NP-complete combinatorial optimization problem, so it would be difficult to find any efficient global optimization algorithm. Grouping is an efficient strategy for solving such a multi-factor optimization problem. All courses are partitioned into groups by their ranking. Then the combinatorial optimization algorithms can be applied to solve each grouped sub-problem. It is usually considered that the course capacity is the dominant factor in the ranking of the courses. The advanced administration system allows students to select courses in problem more complicated. A course ranking a considerably wide range,which makes this model is proposed in this paper using Markov chain,and the concept CourseRank is given. Results from mining the course scheduling data of Tsinghua University of 2002-2003 academic year are presented,which shows that the course capacity is an important factor,but not really the dominant one.