陈 辉，何 军

(安徽商贸职业技术学院 教务处，安徽 芜湖 241002)



排课问题的数学模型研究

陈 辉，何 军

(安徽商贸职业技术学院 教务处，安徽 芜湖 241002)

通过对排课问题中课程、班级、教师和场地的约束条件进行数学抽象，将排课方案的优化表示为场地利用情况和课时安排合理性的评价，给出了一个较为精炼的排课问题数学模型，在一定的问题规模下，得到了较好的排课效果。在此基础上，针对高校排课实际应用场景，基于贪心算法给出了排课问题的一种高效的近似求解方案，为基于排课的教务管理信息系统的构建提供了参考借鉴。

排课问题；排课算法；整数规划模型；贪婪算法；Lingo

排课涉及班级、教师、教学场地和各种教学资源的调配，是教学管理中复杂性最高、难度最大的问题。人们一直都在尝试利用计算机信息手段来实现自动排课。早在1962年Gotlieb即在其著作“The Construction of Class-Teacher Time Tables”中研究了排课问题的数学模型[1]，并将其视为组合规划问题进行相应地深入研究。S.Even等在1976年完成了运筹学中时间表问题(Timetable Problem,TTP)的复杂度分析研究，并首次证明排课问题作为时间表问题的具体应用，是“多项式复杂程度的非确定性问题(NP完全问题)”[2]。随着90年代计算机技术的逐渐普及，课表的计算机编排开始大量出现，但由于问题本身的复杂性，在高校这样复杂的教学场景中，计算机通常只是作为手工排课的辅助手段。直到Paecher等通过对时空排列和布局寻找，找到了处理时间表问题的一些方法[3]。近年来，随着遗传算法、模拟退火算法、蚁群算法等智能算法的兴起，国内学者对排课问题投入了大量的研究[4-10]，在取得丰富成果的同时，也存在着普遍的问题。……