多约束条件下的分层走班排课思路与实现

赵寅 韩思瑶

摘 要：自2011年开始，北京市十一学校开展了走班选课的课程改革试点工作，经过几年的实践探索，逐渐形成了一套分层与分类协同、高端与援助并存的多元化课程体系，在过去几年的实践中，根据实践探索提出了三种分层走班选课的排课思路：基于学生分组、基于课程分组V1.0、基于课程分组V2.0，分别适应不同的要求。并在云校公司的自动排课系统帮助下，实现了从人工排课到自动排课的转变，解决了多约束条件下分层分类课程的排课困境，提高了排课效率，为学校的分层走班选课改革提供了强有力的支持。

关键词：分层走班；排课算法；自动排课

中图分类号：G473 文献标志码：B 文章编号：1673-8454（2018）07-0055-04

一、研究背景

随着课程改革的深入，学生在自己的学习上将拥有更大的选择权利，传统的基于行政班的排课显然无法满足学生的选课需求。因此，“排课后选课”或者“选课后排课”模式将成为几乎所有学校的必然选择。越来越多的学校将不仅仅为学生提供包括高考课程在内的不同类别课程的选择，也将开设分层选择课程以满足不同层次学生需求，甚至在教学班的班级容量、学科教室建设等方面给学生更合理的学习环境。于是，学校的排课和选课将变得非常复杂，优质的排课能够让学校在有限的资源情况下完成更多的教学实践，因此一次排课、选课活动就要同时考虑多种因素，包括教师资源、教室资源、课时资源、班级容量、分层科目、分类科目、教师时间个性化等等。

十一学校2011年开始课程改革的试点工作，从2011年到2016年5年的时间内，学校经历了分层、分类、特需的课程体系建设，各年级对应的分层分类课程的选课组合也由简单的34种发展到112种之多。立足学生的发展方向、学习方式和课程的难度，北京十一学校首先对数学、物理、化学和生物等传统的理科课程实施了分层设置。对于语言与文学领域的语文和英语，则依据学科自身的特点和学生的学习需求情况， 按照“必选基础课程 + 分类自选课程”的设计思路实施。以数学为例，从数学Ⅰ到数学Ⅴ难度不断加深。如果一位学生打算将来做精算师这样的职业，高中数学就需要选择最高层次的数学Ⅴ；如果想成为一名工业设计师，选择数学Ⅱ的难度就可以了；如果将来想从事历史、文学等人文方向的工作，学习数学Ⅰ即可。[1]

经过几年的实践探索，北京十一学校逐渐形成了一套课程体系，包括 269 门学科课程、34个综合实践课程、60个自主管理课程、70个职业考察课程、250个社团课程、12个高端项目研究课程、8个游学课程和6个书院课程以及若干个援助课程等。學校希望，当这套课程体系呈现在学生面前的时候，在选择与尝试中，他们那些潜在的、真实的兴趣、需要和发展潜质能够被慢慢发现和唤醒，选择性的课程可以帮助每一位学生慢慢找到自己的优势领域，促进其发现自我并认识自我。[2]

为满足较多约束条件下多需求的分层走班选课的排课需求，我们正在探寻并提炼适合国内实际情况的可推广使用的解决方案，包括复杂情况下的排课思路、具体的选课流程、排课选课教师工作手册、选课指导及培训资料等相关资源，排课选课的网络平台等。本文将十一学校近几年来对多约束条件下分层走班选课的排课思路与实现方案进行简要阐述。

二、排课思路演化

在十一学校高中开始完全分层走班之后，我们开发了三种排课思路，分别适应不同的要求，下面做一个简单的介绍。

思路一：学生分组

此思路是十一学校分层走班后最早的思路，当时分层较简单，此思路足以满足所有要求。思路是将所有学生分成若干大组，每组中各科开设等量的班，学生的各科班级均在本组中，排课（将各个教学班安排好上课时间）时将每组当作一个大班级来排，也就是每组中各科排在同一时间，但不同科时间不一样。

以一个年级直升的理科为例：该年级直升理科共10个语文班、10个数学班（4个高层班）、10个英语班、10个物理班（4个高层班）、10个化学班（3个高层班）、10个生物班（2个高层班）。我们可以按如图1形式分成3大组，其中III表示高层，II表示低层，B表示直升，阿拉伯数字表示班号：

若某一个学生是数学、物理、生物高层，则应被分到B1或B2组。只需在B1组或B2组中为他选择合适的班级，如图2所示：

同时，在学生具体分组和分班时，还需考虑人数均衡、男女生均衡等各种细节要求，这也是一项比较复杂的任务。本思路的优点是排课自由度较大，教师和学生的课表都会相对舒服一些。但也有不足，学生选择性小，只能在同组间选择班级，当分层更复杂或者各科分层不均衡时完全不可用。因此其适用范围为：文理分科或者6选3、7选3均适用，但要求无分层或分层情况比较简单。

思路二：课程分组v1.0

当十一学校的课程分层又进一步细化时，思路一就不能满足排课需求了。比如数学高层中，我们将竞赛学生放在同一个教学班，将学AP和自招的学生分在两个教学班，还有一部分学生虽然愿意学高层，但并不学自招或竞赛课，这样的学生又放在另一个教学班。对于一个很多科都是高层的学生来讲，他的高层班几乎是被指定的。因此按思路一排课的话，很难同时满足所有学生的需求。为了解决这个问题，我们提出了思路二，也就是课程分组的方法。

此思路将所有课程分成若干大组，每组中各科开设一些班，排课时保证不同组的任意教学班上课时间不一样，每组中的教学班可以排在同一时间，学生各科跨组选择班级。在学生具体分组和分班以及排课时，仍需考虑很多细节问题。

以一个年级为例：此年级直升理科共有10个语文班、10个数学班【III（B）1竞赛、III（B）2&III;（B）3AP和自招、III（B）4普通高层】、10个英语班、10个物理班【III（B）1竞赛、III（B）2&III;（B）3AP和自招、III（B）4普通高层】、10个化学班【III（B）1竞赛、III（B）2&III;（B）3普通高层】、10个生物班（2个普通高层）。我们可以按如图3形式分成3大组：

此分组形式表示每组中的数学和生物不能一起上课，且每组中数学或生物有可能和物理、语文一起上，也可能和化学、英语一起上，并且要保证不同列的课时间一定错开。

如果某一个学生是数学高层且要上自招【数IIIB（2）或数IIIB（3）、物理普通高层（物III（B）4】、生物普通高层，那么该学生数学只能分在B2或B3组，又因为物理只能在B3，所以数学不能分到B3组，因此只能在B2组，于是生物也只能在B2组。此学生可以按照图4形式分班：

此思路学生的选择性大，但对排课的限制较大，课程分布较分散。只适用文理分科，但分层情况可以很复杂。

思路三：课程分组v2.0

由于早几年十一学校每届学生文科班较少，因此思路一和思路二都只考虑了理科的排课，理科排好后，文科单排即可。但2017级新高一开始高考科目6选3，不再有文理之分，加之十一学校又开始进行语文和英语学科的分类课程，因此，仅高考科目学生就有将近5000种选择。此时不但要将政治、历史、地理一起分组，物理、化学、生物、政治、历史、地理各班所开教学班数量还各不相同。因此课程分组v1.0方法就不再适用，基于此方法进行改进，我们提出思路三：由于语数外三科是必选内容，分组时将此三科绑定，而其他六科另行分组。此思路对文理分科或者6选3、7选3均适用，且分层情况可以很复杂。

以十一学校2017级高一为例，此年级共有9个语文班【一个语文III（B）、一个语文I（B）、7个语文II（B）】、9个数学班【数学III（B）1竞赛、数学III（B）2AP和自招、数学III（B）3普通高层、3个数学II（B）、3个数学I（B）】、9个英语班【3个英语III（B）、5个英语II（B）、1个英语I（B）】、8个物理班【物理III（B）1竞赛、物理III（B）2&III;（B）3&III;（B）4AP和自招、4个物理II（B）】、8个化学班【化学III（B）1竞赛、化学III（B）2&III;（B）3普通高层、5个化学II（B）】、5个生物班【生物III（B）1竞赛、生物III（B）2普通高层、3个生物II（B）】、4个历史班、2个地理班、2个政治班。

我们采用了如图5、6所示的分组方式：

与课程分组v1.0不同的是，每组中物理、化学、生物、历史、政治、地理各科班级数如何配比才能保证学生能够无矛盾且较均匀地分配好是一个巨大的问题。单靠人工计算来完成分组，需要大量的时间。因此从2017级高一开始，我们借助云校公司的自动排课系统进行学生的分组和分班，并取得较好的结果。

三、自动排课过程

在2017级高一学生的排课中，借助云校系统的自动排课算法，我们成功完成了新高考形势下的走班排课。这个过程相比以前复杂很多，利用算法与工具的提升，结合人的个性化判断与经验，共同解决了人工无法处理学生选择性的量级增长的问题，同时提取出教务排课规划，并形成走班排课规则集合。

整個自动排课过程大致分为以下三步：（见图7）

第一步：资源评估

在排课前期，项目组需要对整个学校的各项资源情况进行汇总、分析、评估，才能根据实际情况进行规则制定。

排课需求分为基本信息和特殊规则。基本需求包括课时安排、学科分层信息、学生选课信息、教师信息、教室信息等。特殊规则包括指定节次年级不排课、指定节次教师不排课、指定节次课程不排课、指定节次上课程限制、教学班人数限制、指定节次学生不排课、指定学生在指定教师名下课程等。

分析发现，虽然上述需求均属于比较常见的需求，但其难度却远远高于之前的排课方式。分层使学生可以选择适合自身难度的课程，但同时也会大大增加走班排课的难度。分层数越多，将导致学生选课组合的可能性越多，从而使排出课程表的难度大大增加。学生选课组合越多，越难保证每个学生都能上到自己所选的课程。

针对现有资源的情况以及学校对课程开展的需求，排课项目组会在走班方式（大|中|小）、作息安排等方面进行排课的调整，以保证排课能正常完成。

第二步：自动排课

资源评估完成之后，就是自动排课环节。排课教师会根据具体情况，设置自动排课的各项要求，如满足学生的选科需求、满足教师对任课时间的需求（教研活动、教案齐头、个性化要求）、课表无时间冲突、教学班男女生比例均衡、同科目不同教学班学生数量均衡、有更多自主空间。

接下来平台的自动排课算法会根据需求，进行后台计算，完成排课。关于自动排课算法，早在上个世纪七十年代，就成为一个学术问题被广泛研究，代表性研究范式被视为NP完全问题来解决。NP问题是一个涉及多因素的优化组合问题，难以从数学上给出解的存在性，求解算法。[3]作为一种借鉴了自然选择、变异机制的随机搜索算法，遗传算法利用群体搜索技术，可以高效解决组合优化问题。在探索自动排课算法的过程中，本项目组基于“走班制”的排课约束，给出了智能化遗传算法，定义了相应的选择算子、交叉算子、变异算子和适应度函数等，解决“走班制”模式下的排课问题，从而有效提高学生学习效率，降低教务管理工作的复杂度，提高高校教育教学计划完成力度。

第三步：教务微调

自动排课的算法，能处理批量计算，解放手动排课的繁杂工作，但很难完全满足一线教师与年级的全部个性化需求，比如特殊学生、教师的班级调整，因此自动排完课之后，仍然需要教务教师根据需求在平台上进行适当调整。如教师上课时间微调、学生分配微调、学生换科调层、学生上课时间与自选课微调等。

经过教务教师调整之后的课表，能在现有资源下，尽可能地在更多方面满足师生的课程需求。

四、总结与展望

在学生日益增长的个性化课程需求的基础上，排课的复杂度呈指数级增长，研发一套适合国内实际情况的可推广使用的排课解决方案的需求十分迫切。十一学校在过去的几年中不断探索研究、在实践中不断总结经验，提出了一套在多约束条件下分层走班选课的排课思路，并与云校合作实现了自动化排课功能。为学校的走班选课改革提供了强有力的支持。

排选课是个复杂的系统工作，但同样也是个逐步标准化的产品。课题研究团队接下来将在排课流程优化、提升学生个性化选择满意度、提升平台工具易用性、智能化策略推荐等方面继续探索研究，并通过改进设计与案例匹配来更快速地完成排选课流程。

参考文献：

[1]李希贵，秦建云，郭学军.普通高中育人模式创新及学校转型的实践研究[J].中国教育学刊，2016（1）.

[2]李希贵，郭学军.普通中学学校转型：路径选择与实施策略的研究[J].课程·教材·教法，2014（4）.

[3]杜立智，符海东，张鸿，黄远林.P与NP问题研究[J].计算机技术与发展，2013（1）.

（编辑：王天鹏）