面向新高考“3+X”走班制排课的优先度算法

2021-03-26 03:29儒曼武迪张致远
电子元器件与信息技术 2021年11期
关键词:课表科目约束

儒曼,武迪,张致远

(1.北京交通大学 电子信息工程学院,北京 100044;2.清华大学 航天航空学院,北京 100084)

0 引言

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

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

在遗传算法的基础上,针对走班制的分班策略,文献[8]提出了教学班组合的概念,将所有班级分成若干个批次, 每个批次下划分若干个走班组合以简化排课过程;文献[9]从课表时段分配转为天课时分配,即对每个课程班每天的课时数目进行决策;文献[10]采用按选课组合分班,结合遗传算法解决排课问题。上述方法均假设了一定的人为分班策略,限制了解空间的大小,而且对于教学资源的约束情况考虑较少,在资源紧缺的情况下上述排课算法难以生成排课结果。

本文采用大走班的方式,将选修课时和固定课时分开,着眼于选修课时的排课算法。针对学生的选课情况以及学校的教学资源约束,本文排课算法以优先度为指标逐渐构建走班制班级,最终给出一个可行的选修课排课方案。通过设计优先度指标自动生成走班制的动态班级分班结果,无须额外制定分班策略。

1 课时分区处理

针对新高考“3+X”改革实行的走班制排课,本文将所有教学课时分开处理。第一类是固定课课时区。所有学生在这些课时中只上语文、数学、英语、体育、音乐、美术等行政班科目,这一部分与传统的排课相同,可以用固定课排课方法解决;第二类是选修课课时区。所有学生在这些课时中只上物理、化学、生物、地理、历史、政治。此类课时区又细化为两类课时区:1、高考课时区,即学生选考的科目所在课时;2、会考课时区,即学生未选考,将参加会考的科目所在课时。换言之,就是所有学生同一时间的上课科目类型相同。

由于课时分区只是将走班与固定班分开,未改变固定课时总数,因此课时分区不会减少固定班排课的节空间,但这样的课时分法可以把固定课和选修课分开处理,从而简化排课过程。本文即针对其中的选修课时区提出一种能够得到可行解的算法策略。由于高考课时区和会考课时区排课过程相似,以下的数学模型和算法策略部分只讨论高考课时区排课问题。

2 优先度算法

选修课时区的排课问题是:在有限的教师数和教室数的条件下,已知所有学生选课情况,对所有学生的高考课时进行排课并尽可能减少排课失败人数。此时,学校的教学资源约束为:选修课各科目教职工人数,可用于选修课排课的教室总数及每间教室容量。已知条件为学校的年级课表模板(含课时分区方案),高考课和会考课每周的课时数,以及所有学生的6选3情况。

2.1 数学模型

首先定义高考课课表。每位学生都选择了三个科目作为选考科目,因此对于同一个学生而言有三类高考课时,对应三门高考课。定义下面的课程矩阵:

下面介绍如何无冲突地将学生有序放入课程表中。课程表需要满足的硬约束条件如下:

(1)同一时间一个学生不能排两门课程;

(2)同一时间一个教室不能排两门课程;

(4)每一课时任一课程学生数不能超过该教室最大人数r,即:nij≤r(i=1,2,3;j=1,2,…,m)。

其中本文算法满足前两个约束条件。约束(3)为教师约束,它反映了教师资源有限性,为满足此约束应当尽可能使同一时间科目类别多样。约束(4)为教室约束,此约束反应了教室空间的有限性,排课时如不能很好地满足此约束,将增加排课失败学生的人数,对后续排课任务造成障碍。

下面的步骤是向空课表中放置学生。如果无序地放置学生会使算法十分复杂,需要对所有学生进行分类处理,分类的标准是学生选课情况。由于实行走班制的选修课只有六种,因此学生所有的选课情况只有C63=20种。将所有学生先根据选课情况分为20个集合,再根据每种情况的学生人数由大到小对20个集合进行排序。排课时先排人数多的集合再排人数少的集合,这样可以尽可能确保大多数学生成功排课。对于每个学生来说,需要上的高考课只有三种,分别对应高考课的三类课时。因此对同一个学生来说,可以选择的方案只有A33=6种。分别对这六种情况进行分析,分析的方法即为计算每种情况的优先度,最后将采用优先度最高的方案放置学生。放置的方法即为在每个课时查找对应科目的课程,若满足bi j(r-nij) > 0,则向cij的学生列表中添加此学生。如果没有找到,新建一个该科目的课程单元并添加。这样既可以确保同一时间一个学生不排两门课程,满足约束(1),又可以确保同一间教室只上一门课,满足约束(2)。

定义逻辑变量:

其中1表示课时i班级j处的课程科目满足方案,0表示不满足方案。学生插入过程如图1所示。不同颜色代表不同科目,若标1的插入情况表示当前情况,课表每格的数字代表对应课程的逻辑变量l的逻辑值。则可得出当前情况的科目三个课时组合为A、B、C(如右图所示),则在课表中对应可插入的位置坐标是:课时1:(1,1)或(1,6),课时2:(2,3)或(2,7),课时3:(3,3)或(3,7)。遍历所有学生并进行相同操作即可完成课表的生成。

图1 学生插入过程示意图

下面确定优先度的计算方法。优先度是算法的核心,它的定义方法直接决定排课策略的优劣。直观地来看,优先度应当与每个课时教室剩余容量有关。因此定义每种方案的剩余量ζ:

由于要尽可能使科目分布均匀,因此教师修正项为负值。因为一般情况下教师资源相对于教室资源更加充裕,所以教师约束要弱于教室约束,因此设定教师约束项加权k在0到1之间,表示其权重小于教室约束。由上式不难看出,在方案给定的情况下,表达式中参数除k外均为常量。对于不同的初始数据,k的值是不同的。需要在算法中不断改变k的值不断排课,最终取最优解作为最终结果。

2.2 数学模型

算法除去数据输入和输出以外共分两部分,分别是课时生成部分和教师分配部分。课时生成部分算法如图2所示。其中ε为给定的变化单位,为尽可能减少运算次数,实际设定变化量ε=-0.01。生成课表时若返回false,则表明该条件下课表生成失败,立即进入下轮循环。其中,生成课表的算法策略如图3所示。

图2 课时生成算法流图

图3 课表生成算法流图

指定的k值下生成课表后,有可能会出现某些教室学生极少的情况,有时一个教室只有不到10人,形成教室和教师资源浪费[11]。此时应当以停开限度作为标准(学生人数小于L的课程应当视为停开),令人数过少的课程停开,然后再尝试将此课程中的学生添加到其他非停开课程中。即需要完成的操作为:

优化过程如图4所示。A格代表停开课程,B格代表因停开而同时改变学生列表的课程,C格代表插入学生的非停开课程。

图4 课表优化示意图

优化课表的算法策略如图5所示。

图5 课表优化算法流图

优化后未排入的学生记为排课失败学生。判断课表优劣的指标为排课失败人数,人数越少课表越好。由于课表优化时有可能产生新的停开课程,因此也应将停开课数作为评价标准,停开课数越少的课表越好。评价时首先比较两课表排课失败人数,如排课失败人数相同,比较停开课数。将上述算法策略分别运用于高考和会考情形,就可以分别获得高考和会考课时方案及相应的排课失败学生列表。教师的分配部分如下:首先,由于已满足教师约束,即tj≥si j(i=1,2,3;j=1,2,3,4,5,6),因此一定能成功分配教师。但如果分配时不加策略,将导致教师上课数不均匀,即同一时间只有某几科的教师在上课的情况。为确保教师上课数分配均匀,在随机分配教师后,在每一个选修科目的教师中查找上课数最多和最少的教师,将上课数多的教师的课还给上课数少的教师。重复上述操作,直至最多和最少相差小于等于1。分别在高考和会考的情况下完成上述操作,即可得到一个教师分配均匀的方案。

3 数值仿真

3.1 算例设置

本次实验的目的有两个:

(1)检验算法可行性,依据实例数据给出排课方案。

(2)找到合适的停开限度设置策略并改进算法,并得到较优解。

本次实验采用某校某年级真实选课数据,包括1451名学生,选修教师43人,32间教室,每间教室容量55人。其中学生选课结果统计和每科教师人数如表1所示,此处只列出选择指定高考课的学生人数。

表1 实例1原始数据表

为证明本系统能够在学生人数较少时获得可行解。本实验对真实数据进行精简获得另一份测试数据。测试数据包括248名学生,选修教师18人,9间教室,每间教室容量45人。其中学生选课结果统计和每科教师人数如表2所示。

表2 实例2原始数据表

3.2 数学模型

首先,实例1在min≤ 19、实例2在min≤ 25时会考、高考均无排课失败学生,且满足所有约束。其次,在没有排课失败学生的前提下,评判最终课表优劣的标准为教室资源利用率。为方便绘图,以冗余率作为标准。教室资源冗余率η定义如下:

本次仿真设定的优化次数为1次,改变停开课程限度直至高考或会考课表出现排课失败学生。以冗余率为因变量,得到散点图。用最小二乘法拟合曲线如图6、图7所示。

图6 实例1冗余率拟合曲线

图7 实例2冗余率拟合曲线

分析实例1或实例2的冗余率拟合曲线可知,在不出现排课失败学生的前提下,停开限度越高冗余率越低,排课效果越好,这与直观判断相符。为获得本算法下的较优解,改进图1所示算法如图8所示。改进的部分是在不出现排课失败的前提下不断提高停开限度,取停开限度最高的方案作为最终解。

图8 课时生成改进算法流图

依照上图方法可以无须设置停开课程限度,直接获得该算法策略下的较优解。运行程序得到的部分结果如表3、表4所示。

表3 实例2课时方案

表4 实例2教师分配方案

3.3 仿真讨论

算法策略能够成功完成两组实例下的高考和会考排课任务,验证了算法的有效性;并且分析得到停开课限度与教室资源利用率之间的关系,从而改进算法以获得较优解。

在获得高考和会考的三类课时并分配教师完毕后,在高考和会考课时区中分别依照时间顺序周期地填充课时,填充的轮数为一个高考或会考科目一周内的总课时数。这样处理的好处是无论课时区在时间顺序上的罗列情况如何,都能够保证同一个教师不会在上完一个班的课后再给此班级上课,实现了教案对齐的实际需求,并尽可能保证了每个科目课时均匀。选修课时区的规划可以依照学校的具体需求设计,但应保证不在相应教师的非排课时间之内。此部分内容与本文算法无关,不再赘述。

4 结论

本文给出了一种走班制下选修课排课的优化度排课算法,并通过数值算理验证了该算法的有效性。为直接得到算法策略下的较优解,算例还验证了停开限度对教室资源利用率的影响,实现更加智能的排课过程。本文算法的优点在于1、满足学生的选课需求,完成走班制下的排课任务。2、算法运行时间短,实现简单。但此算法也存在缺点1、固定班教学与走班教学分立,不能做到同一时间既有走班也有固定班。2、教室空间资源存在冗余。此外,本文没有讨论分层教学(不同水平的学生在不同的班)、合班课程(两个班级在一个教室同时上课)、教师水平区分(不同教学水平的教师分派不同的教学任务)等更深层次的排课需求,后续还应解决诸如此类学校排课的个性化问题。

猜你喜欢
课表科目约束
学生出招解决”日课牌“问题
2024年拟在河北招生的普通高校招生专业选考科目要求发布
如果我是校长
约束离散KP方程族的完全Virasoro对称
高校开设专业的首选科目和再选科目要求浅析—以法学(类)专业为例
自我约束是一种境界
各地区学生课表
适当放手能让孩子更好地自我约束
汉语或成俄罗斯高考科目
CAE软件操作小百科(11)