◆范 萍

基于禁忌搜索算法的高职院校排课问题初探

◆范 萍

（泰山职业技术学院 山东 271000）

排课问题一直是各学校备受关注的重要问题。本文对禁忌算法在高职院校排课问题中的应用进行探讨，通过目标函数保证重要课程的排课时间，通过冲突函数，可以兼顾学生、老师的利益。

排课问题；禁忌搜索；冲突函数

排课问题一直是各学校关注的重要问题，随着国家对职业教育的高度重视，高职院校发展迅速，招生规模不断扩大。编排合理的、科学的、人性化的课表对高职的教学管理起着至关重要的作用。排课问题首先需要合理安排时间和教师资源，保证老师能正常为学生上课，学生能正常入教室听课，此外还需注重人性化，如尽量将老师的课程安排集中，避免老师多次来校上课，尽量将同一门课两次授课间隔时间在一天以上，保证同学的听课质量等。

排课问题被证明是一个多约束条件的NP-hard问题，无法保证在多项式的时间内找到最优解。禁忌搜索算法是对局部搜索算法的扩展，通过设置禁忌对象，跳出局部最优化，得到全局最优解。对优化课表，解决排课冲突问题起到很好的作用。

1 排课问题的要求

为保证课程顺利开展，排课需要满足基础条件和优化条件。

1.1 基础条件

一个班级只能在同一时间内上一门课。

一个老师只能在同一时间内教一门课。

两门课不能在同一时间内安排在同一个教室。

教室容量应不小于学生容量。

1.2 优化条件

同一门课程两次授课时间在一天以上：

老师的课程安排尽量集中、连续授课，根据老师时间安排课程时间。

必修课、限选课尽量安排在上午，选修课、通识课安排在下午和晚上。

基础条件是排课必须满足的条件，优化条件是完善课程安排的条件，不是必须满足的条件。探讨排课问题时，做如下假设和简化：

（1）教室资源充足。各类型教室数远远大于同一时间段的需求。

（2）一天共有5个大课时，每门课每次上课仅占一个课时。

（3）不存在合班上课的情况。

（4）课表由学校统一安排，不存在课程提前被安排的现象。

2 排课问题的建模

教师集合：T={t1，t2，…，tm}；

班级集合：C={c1，c2，…，cn}；Num（ch）表示班级ch的人数。

课程集合：L={l1，l2，…，lu}；

教室集合：R={r1，r2，…，rv}；Cap（rk）表示教室rk的容量。

教室类型：S={s1，s2，…，sz}；Type（rk）表示教室rk的类型，Type（rk）∈S

时间集合：P={p1，p2，…，pd}；

教师时间偏好集合：A={A[t1][ p1]，…A[t1][pd]，…A[tm][pd]}

授课任务集合：TASK={task |task =（c，t，l，s，w），c∈C，t∈T，l∈L，r∈R }表示教师h在班级c讲授课程l，需要s类型的教室，每周共讲授w次课。

最终的课程表CT={ct |ct =（c，t，l，p，r），c∈C，t∈T，l∈L，p∈P，r∈R }表示在p时间段内，教师t在r教室为c班级讲授课程l。相较于TASK，最终课表CT将需要教室类型s、上课次数w具体为上课教室和每次上课具体时间。

排课首先要满足基础条件：

（1）一个班级只能在同一时间内上一门课。

设i≠j，

当cti.c＝ctj.c

必有 cti.p≠ctj.p

（2）一个老师只能在同一时间内教一门课。

设i≠j，

当cti.t＝ctj.t

必有 cti.p≠ctj.p

（3）两门课不能在同一时间内安排在同一个教室。

设i≠j，

当cti.c＝ctj.c and cti.r＝ctj.r

必有 cti.p≠ctj.p

（4）教室容量应不小于学生容量。

Cap（cti.r）≥Num（cti.c）

为了保证排课的顺利进行，将排课步骤分为三步，第一步对课程表进行预处理，设置任务组Group={g | g=（c，t，l，s），c∈C，t∈T，l∈L，s∈S}，可采取贪心算法或网络流算法，将任务组安排到不同时间段，保证同一个任务组单位能在一个时间段内完成。对任务组预处理后得到Glist={Group}。

第二步对课程表进行禁忌搜索，优化课程安排的时间，这是本文详细探讨的部分。第三部对为课程安排相应的教室。

3 禁忌算法

3.1 定义域

时间集合为时间集合：={1，2，…，p}。定义域为一个长度为的整数序列，表示：=（1，2， …，o）。定义域中各分量跟时间元素是一一对应的。

即若o所对应的时间段内有任务安排，则显示任务安排的编号，若安排则显示0。

3.2 目标函数

不同的上课时间具有不同的赋值，如可按表1为各上课时间段赋值，使用（）表示时间段所具有的权值（∈）。

表1 各上课时间段赋值

各课程的重要程度也不同，为各课程用（）表示课程具有的权值（∈）。目标函数值可以如下定义：

该式中，表示访问任务元g中的课程信息。

3.3 适配值函数

排课问题的目的是尽最大可能减少课程冲突，协调老师、学生的上课权益。本文禁忌搜索算法的目标是是适配值函数（）=（）-1（）-2（）-3（）的值最大。（）为目标函数，即保证课程安排时间加权后最合理。1（）、2（）、3（）为三个冲突函数。、、为三个较大整数，根据解除冲突的重要性赋予不同权值。

3.4 冲突函数

1（）表示为累计老师时间冲突。表示教师时间冲突权重。首先定义老师偏好冲突1（，）为：

通过遍历整个定义域内，查找每个非零定义域元素对应的任务组中的老师是否在定义域对应的时间段内有空，若有空侧无冲突，若没时间则增加冲突1。

基于1（，），定义1（）为老师时间冲突之和：

2（）表示为老师课程分散程度，表示教师课表集中度权重。首先定义连续函数2，

即连续授课则无冲突，非连续授课冲突记为1。

定义教师课表分散程度2（），表示老师不连续授课的总次数。

3（）表示为学时安排合理冲突，表示学时安排合理权重。首先定义连续函数3，

即当一门课时两次时间在同一天内，则记为有冲突，否则记为无冲突

3.5 邻域结构及候选解

解是一个整数序列，交换中两个元素的位置就能得到其邻域解。使用互换操作定义来定义域映射函数（）如下：

：=（1，2，…，o，o，…o，…o）→{（1，2，…，o，…，o，o）}（1≤≤，≠）

若邻域解的适配值大于当前解的适配值，则设该解为候选解。

3.6 禁忌表及禁忌对象

禁忌表长度动态变化，前期规模小，得到更多分散解，后期规模大，最优解趋于集中。禁忌对象为二元组，由两个交换位置的整数组成，简化方便。

3.7 特赦准则及终止准则

如某邻域解的适配值大于当前最优值，则设该邻域解为最优解，忽略其是否被禁忌的状态，同时更新禁忌表。终止准则：迭代步数达到某个固定次数后终止。

3.8 禁忌搜索算法步骤

（1）给出算法参数，随机产生初始可行解x∈X（此解为预处理后的可行解），初始化各参数。禁忌表设为空，迭代步数gen为0，设定最大迭代步数max-gen，x*=x，ads（x*）=ads（x）。

（2）如果gen> max-gen，终止算法，输出最优结果; 否则gen=gen+1。

（3）根据选择策略从当前移动集合FN（x）中选取非禁忌移动产生新解x’。

（4）若ads（x’） >ads（x*），则用x’代替最优解x*，ads（x’）>ads，更新禁忌表，跳转（2）。

（5）如果ads（x’）> ads（x*），更新最优解x=x*，ads（x*）=ads（x’）更新禁忌表T，跳转（2）。

4 禁忌搜索算法优势

通过禁忌搜索算法可以合理分配各任务组时间。此后进行第三步，分配各任务组所需要的教室。本文中假设教室足够充足，因此不存在无解现象。可通过贪心算法求得教室分配。

本文重点讲述禁忌搜索在高职院校排课问题中的应用。禁忌搜索算法全局搜索思想有效优化课表。设置适配值，搜索结果一方面尽可能符合目标函数的要求，即满足重要课程安排时间合理性，另一方面又要避免冲突，保证教师时间安排合理、课程安排集中，学生上课效率高等。兼顾了排课问题的基础条件和优化条件，对排课完善有一定作用。

[1]李静，赵建平.高校排课系统优化模型的可行性研究[J].数学的实践与认识.2018（20）.

[2]张媛，祁兰.基于禁忌搜索的排课系统的设计[J].电子设计工程. 2016（22）.

[3]刘长彬.基于遗传算法和禁忌搜索算法的排课系统研究[J].软件导刊. 2014（10）.

[4]夏季.排课问题的数学模型设计[J].信息与电脑（理论版）. 2014（02）.

[5]徐亮.高校智能排课系统的研究[J].电子设计工程. 2013（07）.

[6]王慧君，方明.浅谈高校课程表的编排[J].中国科技信息. 2010（11）.

[7]丁振国，赵宏维.禁忌搜索求解排课问题的应用研究[J].微电子学与计算机. 2008（04）.

[8]王伟，余利华.基于贪心法和禁忌搜索的实用高校排课系统[J].计算机应用.2007（11）.