基于禁忌搜索法的排课系统设计与应用

张媛

（榆林学院数学与统计学院，陕西榆林719000）

随着高校规模的不断扩大与学生数量的增多，在学校教学资源有限的情况下，排课问题已成为高校管理中的关注重点。学校的排课问题需要综合教师、教室、时间和班级等各种因素，是一种具有多种约束与多目标决策寻优的NP完全问题[1-2]。求解NP完全问题的各种方法中，现代启发式优化算法具有可行性[3-5]，其中禁忌搜索算法相比模拟退火等算法性能最优。针对目前国内高校教学排课的复杂性质与现行的大学课表问题模型求解方案的不足，本文分析了有约束的多目标NP完全问题与其各种解决方法，将现代启发式的禁忌搜索算法与传统经典的网络流算法进行结合，提出了一种基于禁忌搜索算法的排课系统设计方案。该方案将两种算法优势互补，提高了问题处理的能力，并用此方案设计了排课系统。

1 排课问题分析

学校的课表编排需要综合教师、教室、时间和班级四种因素，将其进行组合并得到最优决策。因而需要进行规划，获得无冲突的课表。此外，课表还应满足课程对教室类型、老师上课时间的要求等。高校上课时间一般为周1至周5，每天上课时间分为上午、下午和晚上。相同的老师既能上一门课同时也能上多节课，若相同班级一个老师教多门课，则将教师与课程设为同一变量会引起混乱；若一个教师教多个班级，则会出现同一时间给多个班级上课的冲突等问题。教室可分布在不同教学区域，一个完善且合理的课表需要令教师与学生上下节课走动少，并可将教学区域的远近分为不同等级以进行课表的编排。总结以上问题，课表编排过程中涉及同一老师同一时间只教一门课、同一教师同一时间只安排一门课、教室容量满足上课人数等必须遵循的硬约束。同时，教师或学生的课程安排一天尽量在同一校区或教学区、同一门课安排在固定教室、多学时课程安排在不相邻的教学日等尽量满足的软约束。

2 排课问题算法设计

设由教室、时间二元组组成的元素为pairi=(ti,ri)，表示在时间ti将第i个课程任务安排在ri教室里。则由此可构成，状态空间的定义域为序列(pair1,pair2,...,pairi,...,pairn)[6-9]。序列的长度与任务的总数相等，但该做法仅适用于课程任务安排数目较少（低于1 000）的情况。当课程任务安排数目多达上千个时，则该算法性能较差。因状态邻域空间的增大而使算法速率下降，计算时间增加，且冲突事件发生概率变大。从而使得解空间中不可行解增多，算法收敛速度降低[10-11]。

针对将教室、时间二元组组成一个元素所出现的问题，本文将时间、教室当成课程排课问题中的两个子问题来进行处理以加快算法搜索效率。因此，课表编排任务过程如下：

1）预处理分组授课任务。依据完成任务所需时间对任务进行分组，不同任务其老师跟学生也应有所不同，且不同类型的教室供应数量大于需求数量。

2）对不同的任务组与时间资源进行寻优组合，使用禁忌搜索法寻找其最优组合方式，判断冲突的工作量因分组预处理而减少，从而提高算法的收敛速度。

3）对寻优后的课程任务使用冲突检查或贪心思想来安排教室，并形成课表。

排课算法流程，如图1所示。

图1 排课算法流程图

3 信息定义与预处理算法

3.1 基本信息定义

针对排课问题涉及的要素，设：

课程集合：L={l1,l2,...,lp}；

教室集合：R={r1,r2,...,rk}；

教室类型集合：S={s1,s2,...,sD}；

教师集合：H={h1,h2,...,hM}；

班级集合：C={c1,c2,...,cN}；

时间集合：T={t1,t2,...,tQ}。

3.2 基本函数定义

设c班级的人数为CNum(c)(c∈C)。

r教室的容量、类型分别为：

Cap(r)、Type(r)(r∈R)。

s类型的教室数目为

RNum(s)(s∈S)。

3.3 组合信息定义

课程任务集合，即预处理步骤的输入，为：

TASK={task|task=(c,h,l,s,w),c∈C,h∈H，l∈L,s∈S,w＞0}。其中，task=(c,h,l,s,w)表示的是班级c在s类型教室中上l课程的第w次课，老师是h。

设任务组为：

Group={g|g=(c,h,l,s),c∈C,h∈H，l∈L,s∈S}。其中，表示任务元的为g，其余含义与task相同。则预处理步骤的输出，即任务组的集合为GList={Group}。

课表单元集合为：

CT={ct|ct=(c,h,l,t,r),c∈C,h∈H，l∈L,t∈T,r∈R}。其中，ct=(c,h,l,t,r)表示t时间，班级c被教师h讲授课程l的元任务安排在r教室里。最终，输出结果即为课表单元集合。

3.4 预处理算法

基于简化排课模型的预处理算法为：点集X={x1,x2,...,xM}对应教师集合H，点集Y={x1,x2,...,xN}对应班级集合C。若xi与yi间连有w条边，则表示教师hi给班级cj上w次课，从而形成一个G（X，Y，E）的二部图[12-15]。一个课程任务组对应着G的一个匹配，实现分组的过程则是求取若干次最大匹配。

任务集合TASK是预处理模块的输入，任务组集合GList={Group}为模块的输出，本文利用网络流算法对授课任务进行预处理分组。

4 基于禁忌搜索的排课算法

对教学任务进行分组后的任务集GList进行时间分配，主要目的是得到一个最优的从任务集到时间集的函数映射HF：GList→T。其中，最优化求解问题本文采用的是禁忌搜索算法。

4.1 排课问题定义域

假设任务集GList与时间集合T分别为GList={G1,G2,...,Gk,...,GK}、T={t1,t2,...,tq,...,tQ}。x=(a1,a2,...,aQ)表示定义域，且各分量与时间元素对应，表示为：

4.2 目标函数

时间集合是以两个课时为单位，表示课程在课表中被安排的节次。高校上课时间一般为周1至周5，一天有4节课，每周有20单元的上课时间。根据教学效果的优次对不同时间段的课时加以时间权值进行优先规则的分配，时间权值表如表1所示。表中，数值为使用pt（t）所表示的时间t的权值。

表1 时间权值表

课程安排的优先顺序需要根据课程的重要程度进行确定。本文采用分配权值进行标识，课程l的权值为 pc（l），目标函数值为：

其中，g.l表示访问任务元g中的信息。

4.3 参数描述

1）初始解和适配值函数。

首先通过随机组合的方式产生从1～K的随机排列组合，并在随机排列中插入0以形成长度为Q的初始解。

本文采用的适配函数为：

adt(x)=f(x)-w×cols(x)。式中，目标函数值为f(x)，冲突次数为cols(x)，比例系数为较大整数w。冲突情况一种为同一天安排了同一门课程的两次课；另一种为临时安排的课程与事先安排的课程的冲突。

2）邻域结构、禁忌对象和候选解。

交换整数序列的解x中元素的位置，即可得到其的邻域解[16]。邻域映射函数FN（x）定义如下：

互换位置的两个整数形成一个二元组，用来表示禁忌对象以使得简化计算。候选解整数序列集合可由邻域函数确定[17]。对邻域空间元素的适配值进行计算，并按从大到小的顺序排列，存放在列表中。从列表表头开始找起，找到满足特赦准则的禁忌解或非禁忌解，且具有最大适配值来替代当前解。

3）禁忌表及其长度。

用二维数组构成禁忌表用来存放禁忌的二元组，其中表长为固定值，且将相应位置的元素设为禁忌的长度与迭代次数的和用来表示禁忌对象的“任期”。若算法迭代过程中的迭代步数大于禁忌对象相应元素值，则表明此禁忌对象“任期已满”，称为非禁忌的。反之，代表禁忌对象仍处于被禁忌状态。

4.4 禁忌搜索算法步骤

禁忌搜索算法步骤为：

1）禁忌表初始化为空，即元素值全为0，随机产生初始解x，设置迭代步数为iter，其初始值为0，最大值为Iter_Max，最优解为best_x←x，最优适配值为best_v←adt(x)。

2）判断iter≥Iter_Max是否成立。若成立，则算法结束；否则进行下一步，且iter←iter+1。

3）利用映射函数求得当前解的领域解N（x），并确定y∈N(x)的适配值adt(y)，并由二元组以及适配值构成候选解列表，且维持适配值不减。

4）从候选解列表表头开始判断每个候选解y是否满足adt(y)＞best_v。若满足，则将y确定为当前的解，同时更新禁忌表相应元素任期以及重新计算最优适配值best_x←x,best_v←adt(x)；若不满足，则继续下一步骤。

5）对候选解所对应的禁忌属性进行判断，并更新其中具有最佳状态的非禁忌对象为当前解[18]，同时更新禁忌表中相应禁忌“任期”。

算法流程，如图2所示。

图2 算法流程图

5 教室分配

在求得课时分配的最优解x*后，需要确定每个授课任务时间与教室，从而生成最终的课表单元集合。之前假设任意时刻教室供给数量大于需求数量，因而无解情况不会发生，通过贪心算法来对教室进行分配，步骤如下：

1）i←0。

2）i←i+1。若i大于预设的值Q，算法结束；反之，取课时分配的最优解x*的第i个元素ai，进行步骤3）。

3）判断ai是否大于0。若成立，则取GList第ai个元素并进行步骤4）；否则返回步骤2）。

4）j←0 。

5）j←j+1 。若j＞|Gai|，返回步骤（2）；否则进行下一步。

6）取Gai的第j个元素g。若班级g.c已分配了教室r，且教室类型满足要求，则进行步骤8）。

7）寻找教室能够容纳的学生数略大于班级人数的教室r(Type(r)=g.s)，则进行下一步。

8）CT←CT⋃{(g.c,g.h,g.l,r,ti) }，转5）。

算法结束，输出最终周课表CT。

6 仿真验证

运用某高校真实课程数据对本文算法进行仿真验证，在满足各种需求的情况下无冲突产生，且迭代次数少，搜索效率高，所设计的系统参数调整方便[19]。图3、图4即为所设计的系统主界面图、课表查询与打印图。

图3 系统主界面图

图4 课表查询与打印图

7 结束语

针对目前国内高校教学排课的复杂性质与现行的大学课表问题模型求解方案的不足，本文分析了有约束的多目标NP完全问题与其各种解决方法。将现代启发式的禁忌搜索算法与传统经典的网络流算法进行结合，提出了一种基于禁忌搜索算法的排课系统设计方案。该方案将两种算法优势互补，提高了问题处理能力，并用此方案设计了新的排课系统。通过实验验证与实际使用情况表明，所设计的系统操作性强且搜索速率得到较大提高，能够完成目标要求，同时，具有可用性与可适性。