文档介绍：大学自动排课算法设计与实现
田岭(清华大学软件学院,北京,100085,********** )
******@.
摘要:文章提出了一种应用于高等院校的自动排课算法。该算法针对高等院校排课要求的高
易用性、高收敛性等特点将启发式算法、禁忌搜索算法、回溯算法进行有机结合,充分发挥
启发式算法在利用应用领域经验和规则的优势,提高了自动排课的资源搜索能力。通过在实
际工程中应用,表明该算法在解决复杂的高校排课问题时有较好的效果。
关键词:自动排课、启发式算法、禁忌搜索、回溯算法
Design and Realization of University Automatic Timetabling Algorithm
TIAN Ling (School of Software Tsinghua University, Beijing 100085,china)
Abstract:This paper proposes a novel algorithm for university automatic timetabling.
According to the requirement of university timetabling for higher usability and
astringency, we integrate the heuristic algorithm with tabu search and backward
strategies. Our algorithm utilizes basic features of the heuristic algorithm with
domain knowledge and experience rules, and enhances the performance of resource
searching for the purpose of automatic timetabling. The experiment shows that our
algorithm is quite effective in solving plex problem in automatic
timetabling.
Keywords:automatic timetabling、heuristic algorithm、tabu search、backward
strategies

高校教学活动中的排课环节是对教学活动开展过程中需要的相关资源(包括课程资源、
教师资源、教室资源和时间资源)进行有机的组合,在满足学校教学活动正常开展和尽量满
足学生选课需求的前提下,找到上述资源的最优组合,实现教学资源利用的最大化。对于排
课问题的有以下几个要点:
第一、对于国内高校,排课环节在其教学管理工作中所占比重很大。目前国内各所高校
都面临着由于扩招学生带来的教学资源严重不足的情况,因此针对于教学资源日益紧张的高
校,寻找最优组合的教学资源,实现教学资源利用的最大化,避免由于教学资源的浪费而影
响学校教学活动的正常开展,成为目前大多数高效的重要需求。
第二、从理论上将,排课就是在限定条件下,寻找最优资源组合的过程。在数学上排课
属于资源调度问题,已经证明资源调度问题属于 NP 完全问题,即一般没有多项式时间算法。
也就是说在限定条件复杂和参数众多的情况下,即使通过计算机可能也无法在有限时间内找
到最优解。
作者简介:田岭男,1979 年,清华大学软件学院硕士研究生,专业方向:软件工程;
第三、排课问题需要从业务和计算机方面进行解决。业务层面的解决方式是指采取合适
的排课模式,包括依据课程的类型进行分批次的排课、采用学校一级排课与院系二级排课结
合的模式。通过业务层面解决方案的目的是降低每次排课的复杂度,争取让每次排课在一个
较小的、有限的范围内寻找最优解,然后采用逐步求精的方式寻找整体的最优解。计算机的
解决方案是指发挥计算机运算速度快的特点,在大数据量的情况下,寻找资源的最优或近似
最优组合,以大大减少人的工作量。目前常用的解决排课问题的方法有模拟退火算法
(simulated annealing algorithm)[文献 10] 和遗传算法(ic Algorithm)[文献 8、9]
等这类随机寻优算法,这类算法的共同特点是:算法计算比较简单,可不依赖于问题的性质,
对目标函数要求低、容易实现。但是这类随机搜索算法的缺点是它需要检查相当多的可行解
集,计算量大,计算非常耗时,收敛速度慢,应用在排课问题上,很有可能遗漏可行解或很
难找到最优解。
本文提出了一种