基于贪心法和禁忌搜索的实用高校排课系统

Interactive timetabling approach based on greedy method and tabu search

在深入分析普通高校排课的流程、特点和难点的基础上,提出一个基于贪心法和禁忌搜索的排课算法。算法采用基于优先级的贪心法构造排课的初始解,进而利用禁忌搜索获得全局较优的排课结果。设计中充分考虑了当前高校课表问题的实际情况,如课程性质对排课的要求、教师的特殊要求等。实现的原型系统同时支持自动排课和交互式排课,对于一些难度较大的问题,可以通过人机交互方式来解决。通过对高校的实际排课数据进行测试,结果表明该算法可行且能够有效地提高排课效率。

University timetabling is a widely used NP hard optimization problem, hence finding a high quality timetable is a challenging work. The hard and soft constraints of university timetabling problem were analyzed, and then an interactive timetabling system based on greedy method and tabu search was proposed. Greedy method was used to construct an initial solution at the first phase and tabu search was used to find an optimal timetable at the second phase. The prototype is implemented and the experimental results show that the approach is both practical and efficient.