排课机制及其优化 ?

黄艺燕 洪星星 孙燕君

摘 要：本科教育综合改革提出培养跨学科人才，鼓励学生在全校范围内跨越院系自由选课，一人一张课表。排课作为选课的基础保障，如何顺利实现跨院系选课、避免选课冲突，成为近年来高校排课工作中比较突出的困难。本文探析了排课问题的实质，分析了北京大学的排课机制，提出了优化排课制度的举措。

关键词：排课机制;大学教学改革;自由选课;跨院系选课;自动排课系统

北京大学本科教育坚持以学生成长为中心，秉持“加强基础、促进交叉、尊重选择、卓越教学”教育理念，实施了包括修订完善专业培养方案，凝练核心课程体系，建设跨学科专业、跨学科项目、交叉课程模块等多层次、有特色的人才培养项目，支持学生在完成各专业毕业所需最低学分要求的基础上修读辅修或双学位，逐步建立起了全面自由的选课制度，允许学生跨院系自由选课[1]。北京大学2016版教学计划的特点是，将其他院系的专业核心课纳入本专业的自主选修课模块。这部分学分既属于专业的主修学分，同时也可以用来申请其他院系的辅修证书。这种可以两边认定学分的方式，使得学生有更大的动力去修读其他院系的核心课程。新的辅修、双学位管理办法规定，辅修、双学位专业课程与同专业主修课程同质要求，同质管理。双学位和辅修不再采用过去那种利用周末针对性开班排课的方式，而是和主修专业同班上课。另外，辅修采取申请制，事先不报名，通过跨院系选课的方式修读课程。在毕业审查阶段，完成了辅修教学计划的学生可以向相关院系申请辅修证书。跨院系选课量的增加，导致选课时间矛盾日益凸显。为此，学校教务部通过制定排课时间和考试时间对应规则，约束选课冲突和考试冲突问题。同时，通过院系教务办公室统筹、协调上课时间，解决院系内专业必修课时间冲突问题。

一、排课问题和排课机制

1.排课问题

排课问题作为多元约束问题，涉及的资源有教师、学生、教室。约束条件有：（1）同一个教室在同一个排课单元只能上一门课。

（2）同一位老师/学生在同一个排课单元只能上一门课。（3）一周的总排课单元是有限的。

（4）一个学校的教室总数是有限的。（5）一间教室的容量是有限的。（6）教室必须满足课程的容量和类型要求。

排课问题本质上是一个时间表问题。时间表是图论中的经典问题，几十年来一直是许多学者研究的热点。1963年Gotlieb将其定义为多元约束问题，并用形式化的语言进行描述并构建了数学模型，但当时没有找到有效的解决办法。1976年S.Even通过证明指出，课表问题属于NP完全类问题。这表明我们无法在有限时间内找到全局最优解[2]。此后，教育工作者和计算机专业人士的研究工作主要致力于给出局部最优解的启发式算法并取得了一些成果，例如模拟退火算法、禁忌搜索算法、遗传算法以及蚁群算法等。目前，这些排课算法在全国各高校也有应用，具有代表性的是清华大学的TISER（Timetable Scheduler）系统、浙江大学的正方现代教学管理信息系统等。北京大学于20世纪90年代自主研发了第一代排课系统，后经不断维护更新，于2005年前后开发了基于模拟退火算法的排课系统。

2.各高校主流的排课机制

目前，在国内高校中主要存在两种排课机制：一级排课和二级排课。

一级排课指的是由高校教务处负责编排课表，二级学院负责协助和核对、确认工作。这种排课模式早期比较流行，它的优点是效率高，调整性强，不易冲突。一级排课模式比较适用于办学规模不太大，资源分配权集中在教务处，而院系级个性化需求不高的高校。

二级排课指的是由高校教务处统筹协调课表的编排工作，由二级学院教务办公室或者教务人员负责课程的安排，将课程执行計划录入信息系统中。教务处借助信息系统分配资源，再对个性化需求的课程辅以人工调整。二级排课模式的优点是将排课任务分解，理清高校教务处和学院之间的权限和责任，各司其职，有效分解了排课压力，降低了排课的难度，特别适用于办学规模较大，个性化要求较高，资源冲突比较突出的高校[3]。近年来这种模式逐渐推广，已成为国内主流的排课模式。北京大学从90年代后期就开始采用二级排课模式。这种模式不仅有效地分解排课难度，而且尊重教师的上课意愿，充分发挥院系的自主协调能力。

3.北京大学现有的排课机制

北京大学将排课工作分为课程容量、时间排布阶段和教室分配调整两个阶段。教室分配调整采用系统协助分配，辅以少量的人工后期调整。学校现在使用的排课系统建设于2005年前后，采用的是给定时间下的模拟退火算法，主要解决教室资源的排布问题，以实现最大化利用教室资源。同时，由系统保证教室不冲突，避免教学事故[4]。

在课程容量和时间排布阶段，院系教务办公室根据历年的经验积累，人工排定课程的上课时间和上课人数，并录入系统。院系教务办公室在排课时需要遵循的原则有：（1）同年级同专业的专业必修课不冲突。（2）同专业不同年级必修课不冲突。（3）同年级同专业的必修、选修不冲突（尽量不冲突）。（4）同年级全院必修和所有各专业的必修不冲突。（5）不同年级的全院必修尽量不冲突，等等。上述五条原则的优先级由高到低，根据实际情况按顺序尽量满足。

但上述这些原则没有考虑到跨院系选课、辅修以及双学位学生的选课需求。近年来，随着教学改革不断深入和自由选课制度逐步完善，北大已经不是过去那种专业课由院系统一安排（同一个专业的学生统一上相同时间、相同地点的课程），仅公共课自由选择的机制，面临着一个学生一张个性化课表的复杂问题。以往单靠院系教务办公室人工协调课程时间分布的排课模式受到了很大的挑战。在排课问题上需要突破旧有的经验，寻求更广泛、更灵活的排课方法。

二、排课时间问题的制度调整

在高校教学管理中，排课的具体实施因校而异。各校排课机制首要是适应本校的资源情况、权责分工情况，最关键的是要能保障学校的教育教学理念落地。排课算法理论研究大多考虑的是排课问题的学术特点，为了方便将其模型化、形式化描述，会忽略现实中的各种复杂因素和差异化问题，比如教师偏好、学生偏好、课程特点、教室资源、信息系统基础情况等。因此，在选择排课算法的时候，要考虑各校的具体情况，并针对实际情况，对排课机制和具体实现算法做出调整和优化。

在深化本科教学改革，实现“以学生成长为中心”“立德树人”大背景下，笔者通过研究北大现行的排课机制和排课数据，发现现有的机制存在改进空间。

1.排课时段的分布调整

根据2016—2017年春季学期开课情况，我们统计了本科教学班的时段排布情况，发现每天的3～4节课和7～8节课是排课的热门时段。这两个热门时段的课程班级数占比接近50%，而1～2节课程的班级数占比为15.5%，这表明在当前排课机制下存在着排课时段利用率不足的

假如课表在时段排布上再均匀些，那么从宏观角度来看，学生在时间上的选课自由度就会增加，这样可以一定程度上减少时间冲突。因此从2017—2018学年开始，我们在排课制度上增加了对排课时段的要求，原则上各时段应均匀排课，适当增加1～2节时段的课程，同时限制热门时段课程在院系所有排课时段总量的占比。对于超过比例的，学校教务部门在审核执行计划时不予通过，最终审核不通过的院系将无法参与安排教室。以下是排课制度中关于排课时段的相关规定：

为给学生选课提供更多的选择，各院系课程应合理安排好时间，排课时应统筹安排各时段课程。原则上各时段均匀排课，尤其要增加1～2节时段的课程。

各院系安排在3～4节时段的课程不能超过院系所有排课时段总量的20%。不符合以上要求的，系统审核执行计划时不予通过。最终审核不通过的院系将无法参与安排教室。

上述制度开始执行后，院系的排课时段分布渐渐趋向均匀，整体上相对合理。但是该制度在执行过程中依然遇到了一些挑战，例如受授课教师的意愿、习惯等因素影响，院系拒绝调整上课时段，或一些课程找不到合适的时段安排。另外，我们不得不承认，宏观上分布相对均匀的课表，并不等于微观上学生选课就不冲突，不等于学生就能顺利选上需要选的课程，更不代表学生就对课表的排布满意。

那么，什么才是真正的好课表？怎么排课才是让人满意的课表呢？

2.关于课表优劣的衡量

好的课表可以让每个学生顺利完成四年教学计划，而更优的课表是学生在完成四年培养计划基础保证上，还可以自由选上自己想选的课程。

课表优劣的衡量指标应该包含：（1）学生所在专业教学计划要求的课程能顺利选上。

（2）学生主观上喜欢上的课，不会因为时间冲突而无法选。第一点是一张合格的课表必须满足的硬性指标，而第二点是一个主观性指标，难以具体获得，并且人人满意的课表在现实中是不存在的。从教学管理角度看，应该让尽可能多的学生顺利选上教学计划所要求的课程。

假如用数据挖掘的方法去分析教学计划的数据和学生的历史选课数据，是否对我们的排课有所启发呢？因为学生需要选什么课，这个信息在教学计划中已经给出答案。而学生喜欢上什么课程，在历史选课数据中也可以捕捉到一定的证据支持。所以，借助计算机的运算能力挖掘数据，启发排课时间分配，算出来的课表会优于院系教务办公室的人工排课。

3.对人工安排课时的分析

我们观察和分析了院系教务办公室人工安排课时的具体操作，发现每个排课工作人员并不是在一张全空白的纸上排布全院的课程，而是在上年度相同学期排课结果的基础上进行当前学期的排课工作。具体包括：与原有课程的授课教师确认是否照以往时间安排上课;寻找新的合适的上课时间，分配给新开设的课程。当发现冲突的时候，人工寻找调整空间。这表明，课表排布本身就是一个每学年都在迭代、优化的过程。因此，我们借助计算机安排课表时，历史的排课数据也是我们分析和提取有用信息的数据源。

三、排课再优化

排课再优化是指通过学校往年排课数据，结合各院系专业教学计划，挖掘出课程间关系，找出哪些课程是学生倾向于同一学期选修。然后，再利用启发式排课算法求解课表，避免出现专业课上课时间冲突的情况。这样排出的课表将很好地支持学生的跨院系选课和辅修，以及双学位选课，也减少了教务排课的人力劳动。

1.挖掘历史选课数据，分析学生选课行为，得出课程对子

北京大学每学期专业课的选课数据占全部选课数据60%左右，约6万条。这里面隐藏着学生的选课行为模式，例如一些专业课经常被哪些专业的学生一起选，我们将这样的课程称为课程对子。当同时选课人数达到某个值的时候，我们需要关注并尽可能在排课时将上课时间错开。这样，我们从选课数据挖掘出课程对子，并作为排课时分配上课时间的参考依据。

2.对历年来主修与辅修、双学位的修读情况进行数据分析，得出专业对子

我们经过研究发现，主修和双学位的修读存在一定的聚集性。例如，数学学院、物理学院学生更倾向于选信息学院的双学位，而光华管理学院、经济学院学生更倾向于选数学的双学位课程。这就要求学校在排课的时候，要更多地考虑将这些院系相应的专业课程排布开，以避免冲突。我们对现有的双学位修读情况进行分析，以得出类似的专业对子。

3.分析教学计划的课程模块，挖掘跨院系选课的潜在需求

教学计划定义了完成专业学习所必需的所有课程及学分规则，这是学生选课的依据。北京大学2016版教学计划除了凝练专业核心课这一最大特点之外，还有一个创新的做法，即每个专业都将学部内或学部外其他院系的专业核心课程纳入本专业教学计划的自主选修模块中。这样的教学计划意味着学生有了明确的跨院系选课要求。分析每个专业教学计划中其他院系的专业核心课，就可以挖掘出学生潜在的跨院系选课需求。在排课阶段，这部分数据具有很好的指导意义。

4.分析历史排课数据，挖掘课程的排课规律，继承良好的时间排布经验

通过分析历年的排课数据，会发现一些课程有着特殊而相对稳定的排课习惯，而这些习惯是需要保持的。例如，部分院系开设的平行班需要设置在同一时段，以方便统一安排考试;许多通选课、公选课每学期都固定排在某一天的某一节课;一些数学类课程倾向于安排在上午，而许多通选课、公选课等倾向于安排在晚上。这些好的排课经验，需要计算机排课系统继承下来。

5.自动排课系统

在完成上述几项数据分析之后，我们着手开发一个自动排课系统，将挖掘出来的课程对子、专业对子当成排课的规则集合，通过计算机自动搜索的方式进行排课。院系只需事先录入专业必修课程的班级情况，在时间上只填写一周上几次课、每次课连上几节的需求，便可由系统自动分配出建议的上课时间。从尊重教师意愿、满足其授课时间要求的角度，我们还要求自动排课系统允许教师设置有关上课时间的具体期望，并按意愿强度设置备选的若干个时段，以便更好地满足教师的教学需要。

我们邀请计算机专业的三名学生建立了自助排课系统的模型，并利用系统的自动运算搜索获得了2017—2018学年第一学期的课表。在此过程中，我们以图染色算法为起点，逐步考虑各种跨院系选课、主修和辅修/双学位、课程的排课习惯等因素，进而优化算法求解课程的时间排布。同时，我们创新性地增加点权和边权。点权赋值参考的是历年排课数据中的排课习惯、排课规律，边权赋值参考的是上述数据挖掘中计算出来的课程对子、选课的热度等。

相较于往年教务手工排课，自动排课系统排课出来的课程分布结果更加均匀。过去教务人工排课有一定的集中性，上午1～2节课安排比较少，周一3～4节课和周三3～4节课安排最多，超过了270个教学班;而自动排课系统排出来的课表相对均匀，排课最多的是周一1～2节课和7～8节课，有225个教学班，好于人工排课。

参考文献：

[1] 孙燕君，贺熙. 自由选课背景下高校考试管理问题的探索——北京大学的实践[J].北京大学教育评论：2014年高等教育管理专刊，2014（12）.

[2] 陈辉，何军. 排课问题的数学模型研究[J].沈阳工程学院学报（自然科学版），2017，13（3）：273-274.

[3] 劉慧，崔泽永，郭嘉. 基于我校实际的二级排课管理模式研究[J].科教文汇，2018（1）：117-118.

[4] 耿幼平，方明，陈光. 模拟退火算法在排课问题中的应用[C]//中国高等教育学会教育信息化分会第九次学术年会论文集，2008.

[责任编辑：夏鲁惠]