多约束条件下排课系统模型的创建

黄岭 秦春娣 陈伟

摘要：该文在探讨国内外对排课问题研究的基础上，结合学校的教学体制的特点，提出一个多约束条件下采用任务优先级、分治策略和贪心算法相结合的排课系统模型，并给出该模型关键库的创建过程和后续加强改进的方向。

关键词：教务;排课;多约束;算法模型

中图分类号：TP312      文献标识码：A

文章编号：1009-3044（2019）17-0064-03

开放科学（资源服务）标识码（OSID）：

Abstract： On the basis of discussing the problems of course scheduling at home and abroad， and considering the characteristics of the school's teaching system， this paper puts forward a model of course scheduling system which combines task priority， divide-and-conquer strategy and greedy algorithm under multi-constraints， and gives the process of creating the key database of the model and the direction of further improvement.

Key words： Educational Administration; Course Scheduling; Multiple Constraints; Algorithmic Model

人工智能技术的不断发展带来的是人类双手的解放，这也为人类可以摆脱繁杂重复性劳动，转而从事思考创新带来了前所未有的机遇。多年来排课问题一直是困扰学校教务的一个难题，而且以前的纯手工安排课程现在看来也越来越无法适应当今飞速发展的教学需要，这一发展态势要求学校必须综合运用信息化手段来实现课程的安排与布局，以提高排课的效率和精度，同时也可以节约人工成本。排课问题是典型的资源调度问题，该问题已被证明为NP完全问题。课程表排课过程中的课程调度算法具有相当的难度[1]。

1 排课系统模型约束条件的分析

自动排课功能的实现其实是在总结传统人工排课的经验，建立模型让计算机模拟人的思维来选择合适的排课方案。排课问题是一个以各种特殊要求为约束条件，对时间、教师、班级和教室四个因素进行组合规划的问题，简而言之就是解决之间的冲突[2]。排课问题所涉及上课时间、上课教师、上课班级和上课教室等元素，不但需要符合已制定的教学计划，而且还要尽可能满足各种特殊要求，这是一个组合规划的问题，其实是要调和各元素之间的矛盾冲突，换言之就是要借助计算机技术权衡各种制约条件，最终达到课程安排合理化的方案。

经过整理后可把排课过程中的约束条件分为三种：基本硬约束、硬约束和软约束。

1）基本硬约束（Base-hard Constraints）是指教师、班级和教室在时间上不可发生的冲突，包括“同一时间同一班级不能上两门不同的课程”;“同一时间同一教师不能上两门不同课程”;“同一时间同一教室不能上两门不同课程”，这些是排课最基本的约束条件，也是所有排课模型都会涉及的约束条件。

2）硬约束（Hard Constraints）是指根据各个学校的实际需求，在排课时必须遵循的原则，没有它的排课也就没有实际意义了。比如“课程按照最小两节或四节进行”;“课程的总周数和周课时有要求”;“课程有特定教学场所和资源的要求”;“教室大小保证能容纳下班级学生数”;“可手工预排某些课程”;“考虑多个校区教室间的扭转时间”;“体育课不排1-2节”;“实践类课程特殊安排方式”。

3）软约束（Soft Constraints）是指在排课过程中能满足最好，不能满足无碍的约束条件。它的违反与否往往取决于排课模型完成的程度。比如“一周内每个班级的课程分布尽可能均匀”;“教师希望在某些时间段上课”;“教师不希望一天连续上六节及以上的课”;“给各时间段设置优先级”;“上下午中间课程切换教室之间的距离尽可能短”。

2 排课系统模型算法的分析

当前主流的排课算法，主要包括回溯算法、遗传算法、贪婪算法、模拟退火算法、蚁群算法等，下面对这五种常用算法的特点加以描述。

1）回溯算法（backtracking algorithm）在求问题的所有解时，要回溯到根，且根的所有子都已被搜索过才结束;而在求问题的任一解时，只需搜索到问题的一个解就可结束。其优势是程序结构明朗，易于理解;占用空间小;适用于解决组合数较大但有限的问题。其不足体现在时间复杂度较大，回溯层次多时过于耗时。

2）遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。其优势是快捷简便易操作;具有并行计算能力和并行性;容错性强;可扩展性良好。其不足体现在缺乏灵活性;算法较为复杂，易过早收敛;约束增多效率下降。

3）贪心算法（greedy algorithm）是采用从顶向下、依次迭代的方法做出继代选择，每次迭代都会把所要解决问题缩小规模。其优势是具有不可回溯性，有后效性;能在很低的时间复杂度下得到局部最优解。其不足该种算法侧重明显，无法从全局层面考虑均衡优化。

4）模拟退火算法（Simulated annealing algorithm）是来源于固体退火原理，是一种基于概率的算法。其优势是计算过程较简单;在约束条件少的前提下，能很快获得最優解;适用于并行处理。其不足在于较难选择参数，资源开销相对较大;执行时间长，收敛速度慢;不易得到全局最优解。

5）蚁群算法（ant colony optimization）是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。其优势是健壮性明显;全局搜索能力强大;并行实现方便。其不足是执行效率较低，搜索时间长; 容易出现停滞现象[3]。

3 排课系统模型的建立

通过对常用的几个算法的比较，排课系统模型的建立可采用任务优先级、分治策略和贪心算法相结合的算法模型，这样一来可以减少单一算法过于侧重局部，无法顾及全局均衡的问题，二来还可降低自动排课时课程调度产生的逻辑复杂性。任务优先级考虑运用在课程优先级调度时，根据教学计划建立优先级公式为每门课程划分优先级别，然后依据优先级公式所得出的顺序从高到低进行课程调度;而在设计时间模型库时，也采用任务优先级的方法，将归纳总结的最佳上课的时间组合模式设置为较高优先级。分治策略主要运用在借助分治策略将排课过程分成时间分配和教室匹配两个阶段来完成。贪心算法主要运用在时间分配阶段，借助贪心算法的算法思想，在尚未分配的时间模型中选择优先级别较高的时间模式来进行时间分配，以确保相应课程的教学效果最佳。

3.1 时间模型库的创建

排课系统地最终目标还是要以学生上课的最佳教学效果为根本。从之前分析的基本硬约束、硬约束和软约束条件已看出诸如：根据教学和学生学习的认知规律，一天或一周中哪些时间段的学习效果最佳;一周多次上课，给学生预留复习消化知识的间隔时间;特殊资源要求课程考虑优先排课。这些就需要排课人员需要具备丰富的排课经验，并且能够依据教学计划合理规划、组建时间组合，划分相应的时间模式优先级，还可根据后续排课过程出现的异常及时调整时间模型库的相应参数。

具体来说可以根据不同的课时要求把课程自高到低分为：K3（理论类课程：学习认知规律效果相对较好的上午时段）、K2（实践类课程：上下午时间段都可）、K1（类似体育课程：一般不安排在1-2节和晚上）几种等级。然后根据每种等级课程不同周课时数的所有可能的时间组合进行优先级分级T1、T2……，并按照优先级的高低顺序依次存入时间模型库。K3级别课程的2课时、4课时、6课时时间分配模型如表1所示。

上表中J11、J12……表示相应每天的节次，如“J11”中的第一个“1”表示周一，第二个“1”表示当天的1-2节课;“J22”中的第一个“2”表示周二，第二个“2”表示当天的3-4节课;“J54”中的“5”表示周五，“4”表示当天的7-8节课，其他依次类推。

3.2 课程优先级计算模型的确定

课程优先级计算模型主要结合各个学校教学计划和实际需求而定。分析大部分学校的教务需求，主要包括以下几个方面：一是开课班级较多的，如公共基础课应该优先安排;二是纯理论课或专业理论课应该优先安排;三是周课时较多的课程应该优先安排;四是课程需要特殊功能教学场所的，如阶梯大教室、多媒体、机房等应该优先安排;五是课程对上课时间有特定需求的应该优先安排。结合这些需求，可建立如下课程优先级计算模型公式：

公式里的K（n）表示前面已经设置的三种课程等级：K3（理论类课程：学习认知规律效果相对较好的上午时段）、K2（实践类课程：上下午时间段都可）、K1（类似体育课程：一般不安排在1-2节和晚上）;W（n）表示相应课程的周课时数;C（n）表示相应课程的开课班级数量;R（n）表示相应课程在教学场所或上课时间上的特定要求。这里的P1～P4可根据具体需要进行参数的微调，以适应教学需要，保证排课完成率[4]。

3.3 各排课时间数组模型的确定

排课模型初始化时需要给教师、教室和班级分别创建给建立排课时间数组。以某教室初始排课为例：建立某教室初始排课时间数组模型为（12345  12345 12345 12345  12345）。每一组数据中的“1、2、3、4、5”分别表示一周中的五天，而其中总共六组数据分别表示一天中的五个教学时间，当为某教室分配时间后， 相应的教学时间位就置0。例如， 某教室的排课时间数组为（ 01111100111111111011 11110） ， 则表示该教室在周一的1-2 节， 周二的3-4 节， 周三的3-4节和7-8 节，和周五的9-10节已经安排了课程， 剩下来的非0教学时间是还可以安排课程的。同样的方法可完成对教师和班级的排课时间数组创建。

3.4 排课系统模型运行流程

完成各数组及库的模型创建、初始化后，先使用之前建立的课程优先级计算模型公式对所有课程的优先级进行判断，取出获得优先级最高的课程开始排课;把查询出的该课程班级的排课时间数组与该课程的排课时间数组相乘，得到上该课程班级的排课时间数组;然后再与该课程任课教师的时间数组相乘，得到该教师担任该班课程的时间数组;接下来根据该课程的计划课时和之前建立的时间模型库相匹配;最后根据该课程对教学场地的需求查找合适的教室。

4 后期排课模型的改进

关于课程优先级值的定义还可以结合问卷调研形式综合得出，这样更加科学合理;增加排课满意度参考指数并加入历史排课经验参考模型;涉及功能性教室的选择，在资源紧张的情况下，班级人数或机位数可以有所宽松（可以选择区间或临界值的方式），以适应不断变化的排课需求。

参考文献：

[1] 钟嘉鸣， 高春鸣. 智能排课系统及多约束条件下的资源分配模型[J]. 教育信息化， 2002（4）： 56-58.

[2] 梅晓勇. 基于动态规则构造的排课系统设计与实现[J]. 微机发展， 2002（6）： 12-14.

[3] 耿振余. 软计算方法及其军事应用[M]. 北京： 国防工业出版社， 2015（12）.

[4] 杨興旺. 基于回溯法的排课算法[J]. 电脑知识与技术， 2009（19）.

【通联编辑：谢媛媛】