基于优先度与回溯算法的高职院校排课系统设计与实现

柯红香

(漳州科技职业学院 通识课程部，福建 漳州363200)

排课管理作为高校教学管理和实施的重要工作之一，是维持高校正常教学秩序的前提，其涉及范围广、受限制的条件多，排课时需考虑上课时间、教学场所、教师及学生等多方面因素[1]。传统的手工排课方式容易造成排课因素冲突、教学资源分配不合理、管理效率低等问题，影响了教学工作的正常运转，已无法满足现有教学管理的需要[2]。本文针对某高职学院人工排课效率低下、自动化程度低、用户满意度不高的问题，在充分研究回溯算法的基础上，提出了一种基于排课资源优先度的回溯算法的排课系统。

1 回溯算法

回溯算法是一种基于深度优先的系统性搜索问题解的算法，其解决问题的一般步骤为：(1)针对问题定义解空间，解空间至少包含一个(最优)解；(2)确定搜索的解空间结构；(3)按深度优先的策略从根节点出发搜索解空间树。搜索开始时，根节点为活节点，也是当前扩展节点，搜索向纵深方向移动至下一个新节点，这时新节点也变成当前扩展节点。搜索至新节点首先判断是否包含问题解，若包含问题解，继续按深度优先的策略搜索该子结点。若不包含问题解，当前扩展节点不再纵深移动，并标记该节点为死节点。跳过该节点回溯至最近的一个活节点，从另一分支进行搜索[3]，重复以上搜索过程，直至找到所要求的解或遍历解空间树的所有活结点时为止。此外，回溯法的搜索过程可使用剪枝函数避免无效的搜索。剪枝函数包含两类：约束函数和限界函数，可剪去互斥约束条件的路径和不能得到最优解的路径，从而提高搜索效率。换言之，回溯算法是一种特别适合通过构建约束条件来提高程序效率的枚举搜索方法[4]。

回溯算法在排课系统的应用广泛，研究集中在排课算法优化，旨在避免排课因素的冲突，使排课结果可用。但是排课算法却很难兼顾课表的最优化和合理性，特别是合理性很难靠算法实现[5]。为此，本文通过参考文献对比国内外排课算法基础上，结合高职院校具体排课需求，将文献[6]和文献[7]基于排课资源优先的改进后的回溯排课算法应用于本系统。对排课资源——时间片(Time)、课程(Course)、教室(Room)、班级(Class)四大因素设置优先度和对应的权值，建立不同资源优先度的联系，模拟人工排课经验，设置约束条件尽量避免排课过程中产生过多的冲突和引起过多的回溯，从而提高排课效率和合理性。

2 排课管理系统设计

2.1 需求分析

除了维护功能之外，本系统应包括以下主要功能：①教学基本信息管理，该功能主要有学年学期设置、专业班级设置、教学场地管理、课程信息、学生学籍和教师信息管理；②开课计划管理，即专业班级所开设课程、教师可承担课程的增删改操作；③课表编排功能，该功能是系统的核心功能，应能完成班级课程中任课教师、上课时间和教室安排三者之间的匹配；④课表查看功能，使有相应权限的用户可以查询排课结果。

2.2 系统功能模块设计

根据需求分析，系统主要由基本信息管理、开课计划管理、编排课表、查询课表和系统维护五大模块组成，其功能结构如图1所示。

图1 系统功能模块

2.3 数据库设计

数据库概念设计是通过系统需求分析反映用户观点的数据结构化的过程[8]，其目的在于用符号的形式正确反映实际事物及事物与事物间的联系。本系统主要涉及教师、课程、教室、学生四个实体，其间的联系具体为：教室和课程的安排关系、教师和课程的授课关系、学生和课程的学习关系。主要数据表单描述如下：

(1) 教师信息表(Teacher)：用于任课教师信息的增删改查。教师可以教授一门或多门课程，如表1所示。

表1 教师信息

(2) 学生信息表(Student)：用于学生信息的录入、修改、删除和查询。学生信息包括学生编号、姓名、性别、民族、出生年月、入学年份、所在班级、身份证等信息。学生数据表单设计与教师类似。

(3) 教室信息表(Classroom)：用于存放教室名称、类型、容量等信息，具体字段如表2所示。

表2 教室信息

(4) 课程信息表(Course)：用于存放全校开设的所有课程信息，包括课程代码、名称、类型、学分和学时等属性，具体字段如表3所示。

表3 课程信息

(5) 排课结果表(ArrangedResult)：排课结果表的主键是一个全键值，其结构如表4所示。

表4 排课结果表

3 系统实现

3.1 自动编排课表功能实现

3.1.1 排课资源优先度 利用回溯算法实现课表编排时需要计算排课资源的优先度。排课资源优先度分为时间片数组(TimeArray)、课程数组(CourseArray)和班级数组(ClassArray)。按照课程类型、班级周课时数、是否必须在某个时间片上课等属性，将属性进行线性组合得到一个权值，权值大表示所受的约束条件越多，优先排课。排课资源优先度的设置如表5所示。

表5 排课资源优先度设置

3.1.2 课程编排的回溯算法实现 排课以班级为单位，按时间片的优先度进行遍历。首先从班级数组ClassArray中读取优先级较高(即权值较大)的班级，再读取班级对应的CourseArray中的某一门课程，接着从TimeArray中读取一个时间片，并将该时间片与任课教师上课时间进行校验。若校验通过，再将时间片与教室数组RoomArray可用时间进行校验。若各节点满足排课条件，则结束该门课程编排；否则，回溯至上一节点寻求另一个时间片和教室，直至完成所有课程的编排。若遍历所有节点，仍无法满足课程资源分配，则提高课程的优先度，通过一定限度的回溯调整先前课程安排，再为当前课程分配其他资源，直到成功为止，其算法流程图如图2所示。

图2基于回溯算法的排课流程图 图3课程辅助编排算法流程图

3.2 课程辅助编排功能实现

系统还设计了辅助编排功能，以解决因客观条件变动导致小部分课程无法被妥善编排的问题。图3为课程辅助编排的算法流程图。实现后的效果如图4所示。

图4 课程辅助编排界面

4 结语

排课问题本质上一个组合优化问题，其复杂性较高。本文在深入研究回溯算法的基础上将之应用到高职学院排课系统的开发过程中。系统采用C#作为开发语言，Windows 7作为开发平台，Microsoft SQL Server 2012作为数据库服务器，系统部署在Microsoft IIS8应用服务器上。系统经测试后投入使用，效果良好，提高了排课工作的运行效率，用户的满意度也同时得到了提高。