宋 婷，王 栋，许玉龙，王 昂

1.河南中医药大学 信息技术学院，郑州450046

2.华中师范大学 国家数字化学习工程技术研究中心，武汉430079

3.河南农业大学 信息与管理科学学院，郑州450046

随着我国高等教育的快速发展，不断扩大的教学规模和教学改革要求对如何科学集约的调配各种教学资源、合理高效地安排大学课程时间表提出了新的挑战。大学课程时间表问题（university course timetable problem，UCTP），即大学排课问题，本质上是一个具有NP难度的多约束组合优化问题[1]，这意味着不存在完整精确的快速求解算法。启发式算法通常可以在较短时间内获得一个令人满意的解，实现求解效率和质量之间的平衡。因此，设计高效的启发式算法，是求解组合优化问题的主要途径。这类算法通常可分为：直接启发式方法（包括贪婪算法[2]、图着色算法[3]等）、局部搜索算法（包括禁忌搜索[4]、模拟退火[5]等）、群智能算法（包括蜂群算法[6]、蚁群算法[7]、遗传算法[8]等）。由于该问题的复杂性，为吸引更多学者的关注和研究，学术界已举办过多次国际时间表竞赛（international timetabling competition，ITC）[9]，提供了公开的大学排课模型以便于广大研究者在同一基准下聚焦于算法与理论研究。在竞赛当中和其后的研究中，研究者往往混合多种启发式算法共同参与问题的求解，例如Müller[10]采用基于约束的混合局部搜索算法，合并爬山法、大洪水算法、模拟退火算法共同提升寻找最优解。Lyu等[4]将一种自适应禁忌搜索的混合启发式算法应用于大学课程时间表。Geiger[11]采用了一种基于阈值接受准则的随机邻域混合算法来克服求解UCTP 时的局部最优问题。……