基于高校考试管理细化的排考系统研究与设计*

张培培，吕震宇，闫海波

（1.华北理工大学 管理学院，河北 唐山 063000；2.华北理工大学 教务处，河北 唐山 063000）

一、引言

以往高校考试自动排考问题的数学描述[1-4]在实际考试安排管理中有考虑不周的地方，主要表现在：①资源浪费和分配不均。高校教室资源一般存在多种容量，如大教室容量为3个班，小教室容量为1个班，如某门课程任务数是10，分配了4个容量为3的教室，造成2个容量的浪费，而上千门课程造成的浪费是不容小觑的；再如某门课程有多个学院学习，前几个学院拿走了所有容量为3的大教室，最后一个学院只剩下容量为1的小教室，由于每个教室需派遣的监考老师人数相同，优先选择大教室，但大教室数量有限，这样就造成各学院资源分配不均的现象。需将资源按照教室容量进行分配，避免出现资源浪费和分配不均的现象。②公共课集中排。公共课是所有专业或部分跨学院专业的学生都必须学习的课程，若上午考《大学英语》、下午考《高等数学》，尽管监考老师利用率高，但学生和考试管理人员任务较重，所以公共课的安排要尽量分散。专业课是针对本专业开设的课程，考生来自同一个学院，其目标为学院所派教师人数最少，可以集中排，而公共课不要集中排，所以两种课程在考试安排过程中需区分对待。③如考虑交通，一天四个时段是有优先级的，如上午第二时段好于上午第一时段，目标值相等的情况下需选时段较好的。针对上述问题，本文利用贪心算法，提出了新的高校自动排考系统，结果证明该设计很好地满足了以上管理要求。

二、考试时间表问题的数学描述

1.定义

②资源 R={r1，r2，…，rNR}可表示为{w1q1a1，…，w1q1aNroom，…，w5q4a1，… ，w5q4aNroom}，其中 ，W={w1，w2，w3，w4，w5}为天数，共 5 天，Q={q1，q2，q3，q4}为时段，一天 4 个时段，时段具有优先级，顺序为 q1，q2，q3，q4，如 q1代表上午第二时段。A={a1，…，aNroom}为教室，Nroom为教室数量，rj.room_capacity为资源j教室容量，设大、中、小教室容量分别为3、2、1个班。资源按照周一到周五，每天四个时段，每个时段按Nroom个教室排，其中教室按容量先大后小的顺序排，资源数量 NR=5×4×Nroom。

③任务 T={t1，t2，…，tNT}为某课程某学院的某个班。任务量大的课程排在前面，课程里学院任务量大的排在前面。如图1所示，虚线框起来的“1”对应资源为周一上午第二大节a001教室，任务为《大学英语》管理学院信管1班，“1”说明该任务被安排在该教室。

图1 考试安排结果示例

2.约束

①教室容量约束。资源j的任务数不能超过资源j的容量。如公式（1）所示。

②任务约束。每一个任务必须被分配，且只能被分配一次。如公式（2）所示。

③课程约束。课程任务需安排在同一时间，即课程的任一任务在任一时间所对应的aij和要相同，时间w，q对应资源 j序号起止为 （w×q-1）Nroom+1 和 w×q×Nroom+1，设某课程任务序号为{m，…，n}，在某一时间所对应aij之和相同如公式（3）所示。

任一时间需让 w=1，2，3，4，5，q=1，2，3，4。

④教室数量约束。若将教室数量约束简单定义为课程在时间w，q有足够教室可分配，即该时间的空教室容量大于等于课程任务数Nm，如公式（4）所示，则会产生资源浪费和各学院资源分配不均的现象，如图2所示。为了解决这个问题，需分别计算大中小资源需求，约束也为该时间不同容量的空教室数量大于等于课程对该容量教室的需求量。如公式（5）所示。

图2 资源浪费与学院分配不均示例

图3 教室数量约束示例

如图3所示，三个课程进行排考，总任务量为20，教室总容量为24，三门课程大、中、小教室需求如公式（8）所示。当遇到求得结果为小数，则舍弃小数，进行补齐，补齐思路为大、中、小教室资源循环补给，如《运筹学》需补齐 2 个班，大、中、小教室需求为 0、1、0。

3.目标

①公共课课程紧密程度最低。课程紧密程度Cw用一天安排的任务数量来表征，天数为w的资源j的起止序号为（w-1）×4×Nroom+1 和 w×4×Nroom，如图 4 所示，黑格为安排任务，黑格越多课程紧密程度越高，总紧密程度C为5天紧密程度的最大值，如公式（9）所示。

图4 课程紧密程度最低目标示例

课程紧密程度最低的目标为min C。

②专业课学院im所派教师人数最少。学院所派总人数TN[im]为每天所派人数之和，每天所派人数TN[im][wn]为各时段人数的最大值，假定每个教室派2个监考老师，各时段人数TN[im][wn][qr]如公式（10）所示，Tim为学院im所对应任务集合，如图5所示，虚线框有多个任务为1，但因为在同一个教室，所派监考人数仍为2，所以该学院、该资源和Σi∈Timaij若大于0则取值为1，若等于0则取值为0。

图5 学院所派教师人数最少目标示例

学院所派教师人数最少的目标公式如（11）所示。如图5所示，管理学院的公共课《大学英语》已排在w1q1，若要监考教师人数少，专业课《运筹学》需排在同一天但不同时段。

三、算法描述

排考问题是一类典型的时间表问题，是对考生、考场、时间、考试科目和监考人员等因素进行配置的决策性问题[5]。关键技术包括：进化计算、贪心算法、整数规划、图着色等[6]。Ferland[7]和吴金荣[8]提出把时间表问题化成整数规划来解决，但是计算量很大，只适用于规模非常小的课程表的编排。董健兴[9]等人则提出可以用图论中的染色问题来求解，可惜图论的染色问题本身也是一个NP完全问题。进化算法其获得全局最优的可能性较大，但对初始种群的选择有一定依赖性，易产生早熟收敛的问题[10]。贪心算法将整体划分成多个子问题，先做出子问题的最优解，逐步来达到整体最优，该方法简单快速，被广泛使用[11]。

本文采用贪心算法解决自动排考问题，贪心策略为每次挑选排在最前面的课程进行排考。任务按照先公共课后专业课，公共课按先大课后小课排，课程里面按学院任务量从大到小排，专业课按照先大课后小课排。选出一个课程，循环时间，进行约束判断，将所有满足约束条件的时间w、q以及目标值V放入链表List，当时间循环结束，遍历List，找到目标值最优的情况，当目标值相等，选择时段较好的，即q较小的时间，遍历完List就确定了最优的时间，将该时间教室资源按比例进行分配，更新排考结果A。算法N-S图如图6所示。

图6 考试安排算法N-S图

在前面的教室数量约束中，可以得到所有课程大、中、小教室分配数量，如图7所示，而公共课教室还需根据学院任务比来计算学院大中小教室数量，学院任务比Ratioi/m为课程m学院i任务量与课程m总任务量的比值，课程m 学院i分配大（B）中（M）小（S）教室数量如公式（12）所示。假设《大学英语》有三个学院需要分配，计算《大学英语》三个学院的大中小教室数量如公式（13）所示，当遇到结果为小数时，则与课程分配一样，舍弃小数进行资源补齐，如图3所示。

图7 公共课大中小教室分配示例

四、仿真结果

实验数据来自华北理工大学春季学期考试安排18周数据。

1.公共课监考人数、课程紧密程度与公共课任务资源比的关系

设公共课任务资源比RatioT/R=公共课任务数/总资源容量，随RatioT/R增大，监考人数会增多，课程紧密程度也会增大，如图8所示，当RatioT/R在40%之内，教师数量急剧上升，课程紧密程度增长缓慢，这是因为公共课安排在先，任务安排较分散，当RatioT/R超过40%，教师数量增速放缓，课程紧密程度急剧增加，这是因为需在同一天不同时段安排课程。真实考试安排数据RatioT/R低于40%，以保证公共课较低的课程紧密度。

图8 公共课监考教师数量、课程紧密程度与任务资源比的关系

2.专业课任务比与专业课监考人数比的关系

专业课任务比RatioT_Pro/T=学院专业课数量/学院总任务数量；专业课监考人数比RatioP_Pro/P=（学院所派总人数-学院公共课所派人数）/学院所派总人数。如图9所示，在RatioT_Pro/T≤30%时，专业课额外所需派出的老师数量几乎为零，这是由于将专业课尽量排在与公共课同天不同时段，监考教师利用率较高，随后老师数量剧烈上升，所以不能再将专业课排在与公共课同天。真实数据为90%以上学院的RatioT_Pro/T低于30%，保证了监考教师较少。

图9 学院专业课任务比与学院专业课所派教师比的关系

3.资源利用率、资源分配均匀度与任务资源比的关系

学院im教室容量为l的分配差异Liml为理想分配结果与真实分配结果的平方差，如公式（14）所示，理想分配为学院总任务数量与总任务数量的比值，实际分配为学院占用教室容量为l的教室数量除以容量为l的教室总量与任务资源比的乘积，如公式（15）所示。学院im资源分配差异Lim为三个容量差异的最大值，总体资源分配差异L为各学院资源分配差异均值，NI为学院数量，分配均匀度E为差异L的倒数，如公式（16）所示。资源利用率RatioT/RInUse为总任务量与使用教室容量的比值，如公式（17）所示。如图10所示，无论任务资源比RatioT/R怎样变化，均匀度和资源利用率均近似为100%，保证了较好的资源利用率和分配均匀度。

五、结束语

本文指出了公共课与专业课的目标不同，需区分对待，算法对于两种课程是通用的，实验结果表明，当公共课比例不高的情况下，紧密程度较低，同时实验结果也表明，当大部分学院专业课任务比较低时，可保证监考教师较少的目标，实现了任务分配的优化。最后，算法结构中指明，当目标值相等的时候，选择较好的时间段，从而实现了时间选择的优化。

图10 公共课资源分配均匀度与任务、资源的关系