基于优先级分类的排课算法设计

杨 明

（南京铁道职业技术学院，江苏 南京 210031）

基于优先级分类的排课算法设计

杨 明

（南京铁道职业技术学院，江苏 南京 210031）

文章分析了国内外对于排课算法的研究现状，提出了基于等价分类的优先级排课算法的思想，包含确定算法的基本原则、算法的等价分类和优先级的确定，最后给出了算法的流程图和相关测试数据。

教务系统；算法；优先级

1 目前排课算法现状

对于课表的研究，国外最早于20世纪50年代出现。直到1962年，戈特利布最早提出了一个数学模型，用于求解课表问题。此后大家对此问题进行了深入的讨论和广泛的研究，如印度Vastapur大学的Arabinda Tripathy和加拿大Montreal大学的Jean Aubin等。Tripathy，他的主要工作是以“人”为单位进行排课，利用拉格朗日松弛法来解决，这种方法虽然可以减少变量的个数，但是人为造成课程间的冲突。其他有代表性的算法有遗传算法、蚂蚁算法等，通过实践表明，单纯的运用数据方法去解决人为因素过多的课表问题，不是切实可行的办法。

直到1976年，Even等人证明了此问题本质上就是一个NP完全问题。因为对于排课的约束条件太多，而一时也无法找到所有的约束条件，随着排课时间段和学生人数、课程数的不断增加，排列组合方案会成几何数增长，进而在寻求最优解的过程中，系统会消耗大量的时间和资源，最后到了让人无法忍受的程度，从而导致系统无法使用。

国内对排课的研究始于20世纪80年代初，林漳希、林尧瑞教授于1984年宣布了此课题研究成果，成为国内研究的基础。已经成型的成果有东南大学的UTSS系统，大连理工的智能教学组织管理调度系统3.0等。这些已经成熟的系统应用到实际工作中后，的确可以减轻排课人员的工作负担。但是这些排课系统大多是模拟人工排课，以班级作为排课的基本单元，在排课时依赖具体的教学体制和教学模式，不适合广泛推广。

2 排课算法指导思想

排课，是一项非常复杂的脑力劳动，它需要在一定的时间、空间内，在有限的资源供给条件下，实现课表的最优解。排出的课表既要满足课程教学的硬性要求，又要满足老师、学生的软性要求，由于突发因素太多，每个学校情况又不同，因此找到最优课表的概率几乎为零。

本节使用基于分类思想的优先级算法，放弃寻找最优解的过程，而是在给定资源的情况下，满足必备条件，适当满足选择条件，产生基础课表，然后在这基础课表上对其优化，从而产生满足实际需求的可行性课表。这种算法求解的过程，易于程序实现，维护简单，效率较高又能兼顾实际需要，是切实可行的解决方案。

3 排课算法基本原则

课表的编排本质上就是老师、班级、课程、时间、地点的5种资源的排列组合问题，在对这5种资源进行合理配置的时候，最基本的一个原则就是避免冲突，即任何两种资源不能出现互相冲突，例如在同一时间，给一个老师安排了两门课程。

除了这个基本原则之外，根据教学规律和课程特点，排课要遵循一定的基本规则，按照基本规则排课，不但能减少冲突的发生，而且课表的实用性会更强，这些基本规则应包含：（1）同一时间内，同一个班级只能安排一门课程；（2）同一时间内，同一个老师只能安排一门课程；（3）同一时间内，同一个教室只能安排一门课程；（4）教室的座位数应大于上课总人数；（5）上课教室类型要满足课程需要，例如不能给需要多媒体教室的课程安排一个普通教室。以上5个规则，被称为“硬”规则，所谓的“硬”规则，就是说必须要满足的规则，如果不能满足，则教学活动无法进行。

除了“硬”规则，根据教学规律和人体生物钟，排课还必须满足如下“软”规则：

（1）对于同一个班级，同一门课程，一天的课时量最多2节；（2）理论课程尽量安排上午授课；（3）实践课程尽量安排在下午授课；（4）必修课程应放到体育课程前面安排，体育课应尽量安排在第3，4节或第5，6节。以上4个规则，被称为“软”规则，所谓的“软”规则，就是可以使教学活动安排得更加合理有序。排课算法应该优先满足“硬”规则，然后尽量满足“软”规则。

4 算法的等价分类

在设计算法时，为了实现上述规则并有效地降低算法的难度，主要采用了基于优先级的等价分类算法。为了实现规则4和规则5的要求，把教室进行分类，按照其类型分为普通教室、多媒体教室和实训室，如表1所示。

然后，再根据教室的座位数，对每个类进行进一步细分：如45人以下为一类，90人以下为一类等若干种。教室分类完成后，再进行课程类别分类，分为理论课、实践课、体育课程，体育课可以算做实践课程，但是由于排课功能的需要，所以单独划分，各个学校可以根据实际情况做出调整，如表2所示。

课程类别分类完成后，进行课程类型优先级分配，课程类型分为选修课、必修课、板块课程。优先级依次从低到高，在高职院校中，板块课程基本上都是属于必修课程的范围。在同一板块内上课的班级，一般是上课地点不同，但是上课时间都保持一致，例如大学英语、体育课。具体分类如表3所示。

课程类型完成后，进行周学时优先级设置。排课人员根据其以往的工作经验来设置该优先级，优先级的本质就是一系列上课的组合方式。比如一门课程的周学时是6，最佳的上课方式可能是：“13”“31”“51”；表示该课程一周上3次课，分别为周一的34节、周三的12节、周五的12节，第一位数字代表周几，第二位数字代表课程，如1代表12节，3代表34节，依次类推。因此，为了达到预期的上课效果，也要对时间组合模式进行分级。如表4所示。

从表4可以看出，优先级为3的上课效果要比优先级为1的好很多，同理，可以做出实践课、体育课的周学时优先级表。对于每种优先级的周学时数，可以把合理的时间组合模式放在优先级列表中，这样在处理课程时，就可以用优先级列表来匹配。这样就可以满足第6, 7, 8, 9等4条“软”规则。

表1 教室类型

表2 课程类别分类

表3 课程类型分类

表4 周学时优先级

5 算法的矩阵设置

最后来定义4张矩阵表，老师矩阵表Tn[i，j]、课程矩阵表Ln[i，j]、班级矩阵表Cn[i，j]、教室矩阵表Rn[i，j]，其中i表示一学期总的教学周数，比如通常一学期教学周共15周，i就是1—15。j表示1周的教学课时量，按照1周5天的教学计算，j的取值范围是[1.3.5.7.9.11.13.15.17.19.……]，其中，[1.3.5.7.9]代表第一天的1—2节、3—4节、5—6节、7—8节、9—10节，同理[11.13.15.17.19]代表第二天的课时。最终，要把所有的课程都安排到老师、班级、教室矩阵表中，并且要使3张矩阵表匹配成功。

4个矩阵的值为正整数，当Tn[i，j]，Cn[i，j]，Rn[i，j]=1时，表示在该时间段内，老师、班级、教室可用；Tn[i，j]，Cn[i，j]，Rn[i，j] =0，表示在该时间段内，老师、班级、教室不可用；只有当Tn[i，j]&Cn[i，j]&Rn[i，j]=1时，表示该时间段内，可以排课，同时更新Tn[i，j]，Cn[i，j]，Rn[i，j]的数值为0，这样就满足了A，B，C这3条排课的“硬”条件。

6 排课算法步骤

算法的第一步：计算课程优先级，优先级公式为：P(x)=J(x)*K1+T(x)*N*K2+S(x)*K3，其中，J(x)表示课程类型的优先级，如前所述，选修课的优先级最低，板块课的优先级最高，T(x)表示课程的周学时优先级，参考周学时优先级表，N表示该课程的教学总周数，S(x)表示教学计划中的上课人数，K1，K2，K3是可以按照实际需要调整的参数。通过这个公式，可以看到，课程的类型越高，总的学时越多，上课的学生越多。其P(x)值越大，对应的优先级也就越高；反之，P(x)值越小，其优先级越低。优先级越高的课程就先被调度，而优先级低的课程就后被调度。

算法的第二步：根据第一步算出的课程优先级，找出最高的优先级课程，根据课程起始周、学时，初始化该课程的最大可安排时间矩阵表Ln[i，j]都为1，即所有时间都可以安排。

算法的第三步：根据教学计划，确定所有上课的班级，从而得到班级的时间矩阵表Cn[i，j]，Cn存放的是班级已排时间表，然后并将其与课程时间矩阵对比，得到该课程不能安排的时间列表。

算法的第四步：根据教学任务，找出上该课程的老师，查询老师的时间矩阵表Tn[i，j]，从而得到老师已排课时间列表，然后并将其与课程时间矩阵对比，将进一步确认课程不能安排的时间列表。

算法的第五步：在确定了上课时间、班级、教师后，根据教学计划中的教室类型，例如多媒体教室还是普通教室，找到该类型教室的所有列表，然后计算列表中教室的优先级，计算公式如下：

教室优先级=（教室座位数－上课人数）×教室座位数。

从公式可以看出，优先级越小则优先级越高，优先级为0，则教室座位数和上课人数相等。按照优先级数值从小到大，生成教室矩阵时间表Rn[i，j]，得到教室已排课时间列表，然后并将其与课程时间矩阵对比，最终确认课程不能安排的时间列表。

算法的第六步：找到课程的可排时间后，根据周学时优先级表，在表中匹配优先级最高的上课时间。完成以上匹配后，就确定了课程的时间、教室、老师。

算法的第七步：更改老师时间矩阵表Tn[i，j]、班级时间矩阵表Cn[i，j]，教室时间矩阵表Rn[i，j]，同时记录选课课号，选课课号应包含学年学期、老师、课程、教室信息，并将信息写入选课临时表。

如果死锁发生在处理过程中，则可以追溯冲突操作的最近操作，对它进行重排，仍不能解决问题，继续向上排查，直到回溯第一步操作。最后将回溯不能解决的课程输出到冲突列表中，改为手工调整。系统算法流程如图1所示。

图1 法流程图

7 排课算法测试

进行排课算法测试时，将本文排课算法和购买的教务管理系统排课进行对比，选取某高职院校2014—2015学年第一学期的排课数据进行对比，对比数据如表5所示。

从表5的统计结果可以看出，采用本文算法排课后，冲突率降低8个百分点，成功率上升12个百分点，运行时间缩短了61 min。

如图2所示，横坐标表示可用时间点和课程数目的比值，当比值为1时，表明该课程只能有一个时间点安排，当比值大于1时，表明可用于安排课程的时间很宽裕，该数值反映了排课的灵活度。课表的整体优化值通过纵坐标显示，其值越大说明排课效果越好。

8 结语

本节提出的基于等价分类和优先级模式的计算机排课算法，是根据目前高职院校教务管理的实际需求而设计的，该算法简化思想，降低程序设计的复杂性。只要设计好周学时优先级表，并能较好地估算出课程优先级，便可以较好地完成整个排课过程。

表5 对比数据

图2 算法对比性能图

[1]李盘林，李立健.基于启发性知识研究生院课表编排系统[J].计算机学报，1992（11）：876-880.

[2]TRIPATHY A. Computerised decision aid for timetabling-a case analysis[J].Discrete Applied Mathematics, 1992（3）: 313-323.

[3]FERLAND J A, FLEURENT C. SAPHIR: A decision sup-port system for course scheduling [J].Interfaces, 1994（2）: 105-115.

[4]MONFROGIO A.Timetabling through constrained heuristic search and genetic algorithms[J].Software Practice and Experience, 1996 （3）: 251-279.

[5]MERLIN A, SANDRIN P. A new method for unit commitment with ramping constraints [J]. Power Systems, 1983（5）: 1218-1225.

[6]TRIPATHY A.School timetabling-a case in large binary integer linear programming[J].Discrete Applied Math Ematics, 1984（3）: 313-323.

[7]EVEN S，ITAI A，SHAMIR A.On the complexity of timetable and multi-commodity flow problems [J].SIAM Journal on Compu-ting, 1976（5）: 691-703.

[8]HOCHBAUM D. Approximation Algorithms for NP-hard Problems[M].Berkeley: PWS Publishing Company, 1997.

江苏高校哲社研究立项课题；项目名称：大数据背景下职业院校教师的挑战与发展研究；项目编号：2016SJB880057。

杨明（1978— ），男，江苏徐州，硕士，工程师；研究方向：数据库应用，软件工程。