【作者】 彭涛；

【导师】 白峰杉；

【作者基本信息】 清华大学 ， 数学， 2005， 硕士

【摘要】 自二十世纪五十年代,时间表问题(Timetabling Problem)成为一个备受关注的研究课题。1963年,Gotlieb提出了第一个课程时间表(课表)问题的数学模型,将课表问题描述成一个组合优化模型。到1975年Even等人证明了课表问题属于NP-完全问题(NP-Complete Problem),因此很难寻求一个有效的整体优化算法。而后对于课表问题的研究,人们更多关注于它的有效近似算法。经典课表问题是预先根据各种需求安排课程,学生在排好的课程表上选择课程。针对大学排课表这个多因素优化决策问题,分组优化决策是一种行之有效的算法策略。分组策略,可以将课程按优先等级逐次分组,每组再采用组合优化方法进行求解。通常认为课程的规模是优先等级的决定性因素。实行学分制,需要在自由选课的模式下允许学生在一定的范围内选择课程,这就使得课程的关联关系更趋复杂。本文将课程的关联关系描述为一个Markov链,从而提出了课程优先度(CourseRank)的概念。通过对清华大学2001~2002,2002~2003年度学生选课数据的分析和计算,结果表明课程的规模仍然是重要的因素,但并不完全是决定性的。本文对课程数据的分析和挖掘,为进一步优化时间表问题的算法,打下了坚实的基础。更多还原

【Abstract】 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.更多还原