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

张培培 吕震宇 闫海波

摘   要：随着考试安排管理工作的不断细化，高校对自动排考提出了新的要求：一是资源分配要更加合理，将资源按照教室容量来分配，避免浪费和分配不均;二是任务分配要更加合理，将公共课和专业课的排考目标区分对待，避免公共课集中排，给学生和考试管理人员带来较重压力;三是时间选择要更加合理，择优过程中，在目标值相等的情况下，选择时段较好的。本文针对这三个管理要求，利用贪心算法，提出了新的高校自动排考系统，实践证明，该方法在满足基本考试安排管理需求的基础上，很好地满足了新的考试安排管理要求。

关键词：自动排考;管理细化;贪心算法

中图分类号：TP393 文献标志码：A    文章编号：1673-8454（2019）09-0077-05

一、引言

以往高校考试自动排考问题的数学描述[1-4]在实际考试安排管理中有考虑不周的地方，主要表现在：①资源浪费和分配不均。高校教室资源一般存在多种容量，如大教室容量为3个班，小教室容量为1个班，如某门课程任务数是10，分配了4个容量为3的教室，造成2个容量的浪费，而上千门课程造成的浪费是不容小觑的;再如某门课程有多个学院学习，前几个学院拿走了所有容量为3的大教室，最后一个学院只剩下容量为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”说明该任务被安排在该教室。

2.约束

①教室容量约束。资源j的任务数不能超过资源j的容量。

②任务约束。每一个任务必须被分配，且只能被分配一次。

③课程约束。

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

3.目标

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

Cw=w×4×Nroom

j=（w-1）×4×Nroom+1aij，C=max（C1，C2，…，C5）（9）

课程紧密程度最低的目标为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。

TN[im]=TN[im][w1]+…+TN[im][w5]

TN[im][wn]=max（TN[im][wn][q1]，…，TN[im][wn][q4]）

TN[im][wn][qr]=

2×bin

aij，bin

aij=0，

aij=0

1，

aij>0（10）

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

minTN[im]（11）

三、算法描述

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

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

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

N[m][i]B=NB

m×Ratioi/m

N[m][i]M=NM

m×Ratioi/m

N[m][i]S=NS

m×Ratioi/m（12）

N[大學英语][建工学院]B=NB

m×Ratioi/m=2×6/12=1

N[大学英语][管理学院]M=NM

m×Ratioi/m=2×6/12=1

N[大学英语][经济学院]S=NS

m×Ratioi/m=2×6/12=1（13）

四、仿真结果

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

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

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

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

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

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

五、结束语

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

参考文献：

[1][6]雷雨.面向考试时间表问题的启发式进化算法研究[D].西安：西安电子科技大学，2015.

[2]雷雨，焦李成，公茂果.求解多目标考试时间表问题的NNIA改进算法[J].西安电子科技大学学报，2016，43（2）：157-161.

[3]汪慧玲，谭子健，张韧.基于有条件随机分配下的时间表优化问题[J].湖北大学学报，2017，39（3）：253-257.

[4]周伟，吴颖，徐昶等.大型考试考务管理系统设计与实现[J].中国教育信息化，2017（7）：69-71.

[5]史文.基于遗传算法的自动排课系统设计与实现[D].成都：电子科技大学，2013.

[7]Ferland， J.A. and Roy.S. Timetabling problem for university as assignment of activities to resource. Computer and Operations Research[J]，1985，Vol.12，No.2，207-218

[8]吴金荣.解课程表问题的分支定界算法[D].北京：中国科学院数学与系统科学研究院，2002.

[9]董健兴，栾勇，闫君政.基于图论的高校排考算法[J].计算机系统应用，2011，20（5）：177-179.

[10]Yao X， Liu Y， Lin G. Evolutiondary programming made faster[J]. Evolutionary Computation， IEEE Transactions on， 1999，3（2）：82-102.

[11]蔡蜻怡.贪心算法在高校排课系统中的应用[J].电子技术与软件工程，2014（13）：225-226.

（编辑：王晓明）