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

Interactive timetabling approach based on greedy method and tabu search

作　　者：王伟[1] 余利华[2] 

机构地区：[1]浙江医学高等专科学校基础部,杭州310053 [2]浙江大学计算机学院,杭州310027

出　　处：《计算机应用》2007年第11期2873-2876,共4页journal of Computer Applications

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

关 键 词：排课 优先级 贪心法 禁忌搜索 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]