儒曼，武迪，张致远

（1.北京交通大学 电子信息工程学院，北京 100044；2.清华大学 航天航空学院，北京 100084）

0 引言

“新高考”政策下，高中物理、化学、生物、地理、历史、政治成为选修课，每名学生可任选其中3门作为高考选修课，高考时计入高考总分；其余3门作为会考选修课，只判断是否合格，而不记入高考总分。在这种情况下，学校势必要走班管理，即语文、数学、英语等仍可按照固定班级教学，而选修科目则必须走班教学，以满足每个学生的选择。此时，各个学生选课情况不同，需要针对选课情况给出每名学生的“一人一课表”，在学校有限的教学资源下，排课的组合优化难度大，传统的人工排课不再适用，迫切需要一定优化策略下的智能排课算法。

一般而言，排课问题是一类NP完全问题，涉及多因素的排列组合优化，考虑实际排课需求的约束复杂多变，解空间随学生人数的增加而急剧增大。国内外学者应用了多种不同的算法解决排课问题，如遗传算法[1-2]、蚁群算法[3]、模拟退火算法[4]、整数规划[5]等。这些算法大都应用于传统的教学模式，即只存在固定班的情况。而在高考改革的新形势下，需要将走班制纳入考量范围。与传统的固定班排课不同的是，走班制排课需要制定合理的分班策略。目前采用的分班策略有如下几种：（1）不走班，缩减原有的20种选课方式，仅挑选出几种方案供学生选择。这种策略的优点是排课难度降低，但无法满足学生个性化需求；（2）小走班，如“定两科走一科”；……