高校大规模考试的安排方案优化

209003高校大规模考试的安排方案优化摘要本文对高校大规模考试的合理安排问题进行了研究和探讨。

由于高校在校学生的增多，学校在安排期终考试等大型考试时总会碰到各种难题，如，1、必须保证不会出现同一学生有两门考试时间冲突的情况；2、尽量使一个学生的各门考试间隔较为均衡；3、合理利用容量不同的考场；4、使每个监考老师的监考日程比较平均，且确保不发生某一时段监考老师不足的现象。

本文采用图论中的逆着色算法解决问题1，并设计程序根据已知的各种教室规模给出分配考场的最优方案以解决问题3。

为了满足2和4，我们将讨论几种考试时间分配方案并从中得到令学生、老师以及学校都满意的最优者。

为了检验模型的科学性与可行性，我们设计了一个选课程序，使得可以利用计算机对大批量学生的选课情况进行模拟，以得到一个较为接近实际的选课总表。

根据这份数据样本，我们检验了上述所有算法的实现情况，证明了模型的合理性。

并且基于利用这份样本所做的学生和老师对考试安排的满意度分析，我们最终确定了一个考试时间分配方案，从而完整地解决了提出的问题。

关键字：考试安排逆着色算法满意度一. 问题重述由于高校的在校学生的增多，学校在安排期终考试时总会碰到各种难题，如不能错开学生的各门课的考试时间，监考教师不足，或学生参加考试时间过于集中。

这些问题在大面积课程, 如高等数学和线性代数的考试，和一些全校性的选修课的考试时非常明显。

通常的做法是选修课程和必修课程分开，各有一周考试时间，选修课随堂考；大面积课程另行安排---通常这样使得大面积课程的考试和其他必修课程考试同时进行，增加安排的难度。

我们希望针对这些问题设计一个学生、教师和学校都满意的方案。

归纳起来欲解决的问题有：1. 必须保证不会出现同一学生有两门考试时间冲突；；2. 合理利用容量不同的考场；3. 安排应尽量合理，使学生、教师和学校都满意。

考虑到实际的高校规模，这个建模问题只有在做到用计算机进行大样本仿真处理的情况下才算得到真正意义上的解决：手工安排显然是难以完成的。

对问题3的处理情况的评估也建立在对大样本的统计分析基础上。

二. 基本假设1. 选同一门课程所有学生一起参加该课程考试，不考虑上课时的逻辑班级。

2. 一个学校的学生选课情况足够交错复杂以致能排在同一时间的考试科目不会过多，且用作考场的教室在大面积课程错开的前提下数量充足。

3. 教室有大、中、小三种规模。

4. 每天至多可以安排五个时间段的考试。

5. 学生选课情况已知。

三. 符号说明i C ：第i 门课程t N ：监考教师的数量a ：大型教室可容纳的考生人数b ：中型教室可容纳的考生人数c ：小型教室可容纳的考生人数j S ：第j 个考试时间段D ：考试总天数sp ：学生满意度 t p ：教师满意度四. 问题分析及模型建立（一）问题分析容易看出错开各个学生的考试时间是安排方案的前提要求：存在学生考试时间冲突的考试安排方案无疑是失败的。

本文通过运用图论中的着色算法确保考试无冲突，并遵循时间尽量短的原则。

再通过进一步调整各场考试，满足题目的其余要求。

在实际情况中，考试往往是合卷进行的，即选同一门课的学生考卷是相同的，必须在同一时间进行考试。

这样一来，考试安排时可以以考试科目作为其区分的唯一标识。

学校考试中存在全年级大部分学生都修读的大面积课程例如大学英语、微积分等。

这些课程，一个学生往往会同时选择，而且选择人数众多，造成安排考试过程中的种种困难：比如，教室的安排。

教室是考试安排中的一种重要资源，即使没有任何冲突，一门考试课程也可能会因为没有足够的教室而无法安排在某一指定时间。

这里为了简化而不考虑上述情况，即，我们认为只要大面积考试不同时出现，就有足够的教室用于安排同一时间的所有考试。

这是基于假设2“一个学校的学生选课情况足够交错复杂以致能排在同一时间的考试科目不会过多”的。

并且考虑到现在许多大学大规模的校区教学楼总有足够的备用教室和自习教室，我们认为这样简化是合乎情理的。

在计算机仿真检验中，我们发现对于大面积课程，程序必然安排给它较多的大型教室，故我们给大型教室数目加了上限20，这对整个模型没有太大影响。

按通常情况，每场考试持续两个小时，我们假设每天至多可以安排五场考试，即，上午两场，下午两场以及晚上一场。

为使问题明确，我们对几个要求的理解如下：➢对教师充足的理解：即，在同一时间进行的考试每个考场必须有两名教师监考且任何教师不能同时监考两个考场。

在此基础上，每个老师尽量监考他所教授的科目。

➢对教室分配合理的理解：在安排每门考试时，以占用教室数最少为原则；在此基础上，使对于每间考场，空置的位置最少。

➢对方案使学生满意的定义：1、对每个学生，相邻考试考试间隔尽量均匀。

2、学生一般是希望能尽快结束考试的。

为了做到这一点，我们在决定考试日程方案时总是考虑把考生更多的时间段放在前面。

➢对方案使教师满意的定义：1、对于每个老师，监考的场次需大致相同；2、因为老师需要休息，对于每个老师，尽量不出现连续监考的情况，监考安排也需尽量均匀。

➢对方案使学校满意的定义：1、使考试持续的总时间尽量短；2、设计的安排方案应该简便易行，不致过于繁复，难以实现。

综合考虑，最终对于监考方案的确定分四个过程：1.将所有参加考试的科目分在不同时间段，保证每个学生不会遇到在同一时间段考两门的情况，并且尽量使总持续时间最少。

2. 为各门考试安排教室。

保证在同一时间段的各个考场都能有两名监考老师，同时考虑教室的合理利用。

3. 分配各门考试的时间。

根据每天至多可以安排五场考试的假设将所有科目分配到天，并遵循尽量使学生满意的原则。

4. 为各个教师分配监考场次。

每个老师尽量监考他所教授的科目，并满足使老师满意的条件。

（二）模型设计1. 分配各门考试的时间。

1) 步骤1首先，为了保证考试的总持续时间最少，我们将第一个步骤归化为如下问题：某学校有n 门课程1,,n C C 需要进行期末考试安排，同一个学生在同一时间只能参加一门考试，求该校期末考试最少需要安排多少场次的考试。

（问题1）我们将看到这与下面的问题是等价的。

下面（1）~（3）引自参考资料[1]。

（1）图节点着色问题① 图节点着色问题定义[图的着色问题]图G 的一个图节点着色是指k 种颜色1，2，...，k 对于G的各节点的 一个分配，使得任意两个相邻的节点分配以不同的颜色。

而G的色数()G χ是指图G 节点的着色数k 的最小值。

② 图节点着色问题的变换定义[互补图]：图G (V ，E1)，E 为边的全集（任意两个属于V 的节点之间都有对应边所构成的边的全体），则称图H(V ，E —E1)为图G(V ，E1)的互补图。

定义[图的逆着色]：图G 的一个逆着色是指k 种颜色1，2，...，k 对于G 节点的一个分配，使得一种颜色的任意两个节点都相邻。

而G 的逆色数()G ϕ是指G 逆着色数k 的最小值。

定理：图G 的互补图H 的逆色数()H ϕ等于图G 的色数()G χ。

证明：假设图G 的色数()G k χ= ，用k 种颜色对图G 进行一次实例着色，然后把图G 转换为互补图H ，根据定义可知这个实例着色也是图G 互补图H的逆着色的一个实例，所以()()H G ϕχ≤，同理可证明()()H G χϕ≤， 所以()()H G ϕχ=。

根据定理，图节点的着色问题可以变换为求互补图的逆着色问题从而得到解决。

（2）问题1转化为图节点着色问题问题1可转化为一个图节点着色问题：G = (V ，E)，其中V(G) = {C1，C2...，Cn}，每一条边CiCj(CiCj ∈E)的两个端点Ci 和Cj 表示某一位同学的两门考试课程。

于是考试能够安排的最少场次等于图G 的色数()G χ。

由于相邻节点着不同色，保证了不会出现考试时间冲突。

构建简单无向图H = (V ，E)，其中H(V) = {D1，D2...，Dn}，每一条边DiDj(DiDj ∈E)的两个端点Di 和Dj 表示这两门课程可以安排在同一场次考试。

于是考试最少需要安排的场次等于图H 的逆色数()H 。

显然图H 是上述图G 的互补图，根据定理，对求解图G 色数和求解图H 逆色数的结果是一样的。

（3）逆着色问题的解决算法由考试安排问题按节点逆着色构建的简单无向图，其节点的度数反映了对应科目和其它科目组合到一起的难易程度。

不同的考试科目对应节点的度数是不均匀分布的。

根据这个特点我们采用如下算法步骤。

① 遍历图，找出度数大于零且度数最小的节点X 。

② 图是否有边存在，没有则算法结束。

③ 节点X 是否与其它节点相邻，没有则转①。

④ 找出和节点X 相邻的度数最小的节点Y 。

⑤ 合并节点X 和Y 。

⑥ 刷新图后转①。

算法结束后图中的节点数就是图的逆着色数。

图1：假设有A 、B 、C 、D 、E 、F 六门课，相连的两门（如A 和E ）表示至少一位同学这两门考试课程都要考。

图2. 图1的补图 图3：图2的逆着色。

解为：AB 可同时考，DE 可同时考，CF 可同时考需要说明的是，该算法不能保证得到最优解：我们得到的逆着色数不一定是最少的，但该算法较为简洁有效。

算法的有效性见第五部分模型检验。

（4）针对其他要求及程序实现的一些问题的说明① 用程序实现算法（3）时必须注意的是合并节点X 和Y 的过程。

我们注意到，该算法中的“节点”不一定是一个点；它可能是一个K 阶完全图，K 〉1（经过合并后认为是一个点了）。

节点在这里定义为完全图和单一的点的并集。

步骤②、③中的“相邻”实际指的是节点X 与节点Y 中任意两个单一点之间都有边相连。

这时，X 与Y 一起构成一个更高阶的完全图，从而可以合并为一个新节点。

这时该算法的正确性不难加以说明：以上过程可以保证每个节点中任意两个单一点间都有边相连，因此可以着同色。

最后的节点数就是图的逆着色数。

② 由于我们只是假设用作考场的教室在大面积课程错开的前提下数量充足，故图G 中任意两门大面积课程间必须人为地以边相连，否则如果出现同时举办大面积考试则教室可能会不够用。

③ 实现算法的程序中，我们用零一矩阵（对称阵）表示图。

有边连接的两点在矩阵中对应位置为1，否则为0。

④ 在输入一组学生选课表（包括总课程数和每个学生选择的课程表列）时，根据该算法可以将所有科目不相交地分划在若干个时间段内。

对于确定的输入这种分划是唯一的。

这样，我们就确定了需要多少个时间段完成考试，以及每一个时间段包括哪些考试。

2) 步骤2我们还需要考虑的是：对于安排在一个时间段内的所有考试，是否有足够的教师来进行监考。

如果上一步给出的某时间段内同时开考的科目占用教室过多以致监考教师人数不足，则须对将这一时间段的考试拆分在两个时间段中。

因为教室安排时遵循的原则是使每门考试占用的教室数目尽量少，所以，第i 门课程考试需要教室的数量可以由第i 门课程的选修学生数除以大型教室可容纳的考生人数后向上取整直接求得，即，i i x n a ⎡⎤=⎢⎥⎢⎥ （1）每个教室安排两名监考教师，则同一时间j S 的考试科目（假设为1,,m j j C C ）必须满足以下不等式：t j j i i N n m ≤∑=12 （2） 其中t N 为监考教师总人数。