1、209003高校大规模考试的安排方案优化摘要本文对高校大规模考试的合理安排问题进行了研究和探讨。由于高校在校学生的增多，学校在安排期终考试等大型考试时总会碰到各种难题，如，1、必须保证不会出现同一学生有两门考试时间冲突的情况；2、尽量使一个学生的各门考试间隔较为均衡；3、合理利用容量不同的考场；4、使每个监考老师的监考日程比较平均，且确保不发生某一时段监考老师 不足的现象。本文采用图论中的逆着色算法解决问题 1，并设计程序根据已知的各种教室规模给出分配考场的最优方案以解决问题 3。为了满足 2 和 4，我们将讨论几种考试时间分配方案并从中得到令学生、老师以及学校都满意的最优者。为了检验模型的科
2、学性与可行性，我们设计了一个选课程序，使得可以利用计算机对大批量学生的选课情况进行模拟，以得到一个较为接近实际的选课总表。根据这份数据样本，我们检验了上述所有算法的实现情况，证明了模型的合理性。并且基于利用这份样本所做的学生和老师对考试安排的满意度分析，我们最终确定了一个考试时间分配方案，从而完整地解决了提出的问题。关键字：考试安排 逆着色算法 满意度第九届华东地区大学生数学建模邀请赛论文高校大规模考试的安排方案优化 - 1 -一. 问题重述由于高校的在校学生的增多，学校在安排期终考试时总会碰到各种难题，如不能错开学生的各门课的考试时间，监考教师不足，或学生参加考试时间过于集中。这些问题在大面
3、积课程, 如高等数学和线性代数的考试，和一些全校性的选修课的考试时非常明显。通常的做法是选修课程和必修课程分开，各有一周考试时间，选修课随堂考；大面积课程另行安排-通常这样使得大面积课程的考试和其他必修课程考试同时进行，增加安排的难度。我们希望针对这些问题设计一个学生、教师和学校都满意的方案。归纳起来欲解决的问题有：1. 必须保证不会出现同一学生有两门考试时间冲突；2. 合理利用容量不同的考场；3. 安排应尽量合理，使学生、教师和学校都满意。考虑到实际的高校规模，这个建模问题只有在做到用计算机进行大样本仿真处理的情况下才算得到真正意义上的解决：手工安排显然是难以完成的。对问题 3 的处理情况的
4、评估也建立在对大样本的统计分析基础上。二. 基本假设1. 选同一门课程所有学生一起参加该课程考试，不考虑上课时的逻辑班级。2. 一个学校的学生选课情况足够交错复杂以致能排在同一时间的考试科目不会过多，且用作考场的教室在大面积课程错开的前提下数量充足。3. 教室有大、中、小三种规模。4. 每天至多可以安排五个时间段的考试。5. 学生选课情况已知。三. 符号说明：第 门课程iC：监考教师的数量tN：大型教室可容纳的考生人数a：中型教室可容纳的考生人数b：小型教室可容纳的考生人数c：第 个考试时间段jS：考试总天数D：学生满意度sp：教师满意度t四. 问题分析及模型建立第九届华东地区大学生数学建模邀
5、请赛论文高校大规模考试的安排方案优化 - 2 -（一）问题分析容易看出错开各个学生的考试时间是安排方案的前提要求：存在学生考试时间冲突的考试安排方案无疑是失败的。本文通过运用图论中的着色算法确保考试无冲突，并遵循时间尽量短的原则。再通过进一步调整各场考试，满足题目的其余要求。在实际情况中，考试往往是合卷进行的，即选同一门课的学生考卷是相同的，必须在同一时间进行考试。这样一来，考试安排时可以以考试科目作为其区分的唯一标识。学校考试中存在全年级大部分学生都修读的大面积课程例如大学英语、微积分等。这些课程，一个学生往往会同时选择，而且选择人数众多，造成安排考试过程中的种种困难：比如，教室的安排。教室
6、是考试安排中的一种重要资源，即使没有任何冲突，一门考试课程也可能会因为没有足够的教室而无法安排在某一指定时间。这里为了简化而不考虑上述情况，即，我们认为只要大面积考试不同时出现，就有足够的教室用于安排同一时间的所有考试。这是基于假设2“一个学校的学生选课情况足够交错复杂以致能排在同一时间的考试科目不会过多”的。并且考虑到现在许多大学大规模的校区教学楼总有足够的备用教室和自习教室，我们认为这样简化是合乎情理的。在计算机仿真检验中，我们发现对于大面积课程，程序必然安排给它较多的大型教室，故我们给大型教室数目加了上限20，这对整个模型没有太大影响。按通常情况，每场考试持续两个小时，我们假设每天至多可
7、以安排五场考试，即，上午两场，下午两场以及晚上一场。为使问题明确，我们对几个要求的理解如下： 对教师充足的理解：即，在同一时间进行的考试每个考场必须有两名教师监考且任何教师不能同时监考两个考场。在此基础上，每个老师尽量监考他所教授的科目。 对教室分配合理的理解：在安排每门考试时，以占用教室数最少为原则；在此基础上，使对于每间考场，空置的位置最少。 对方案使学生满意的定义：1、对每个学生，相邻考试考试间隔尽量均匀。2、学生一般是希望能尽快结束考试的。为了做到这一点，我们在决定考试日程方案时总是考虑把考生更多的时间段放在前面。 对方案使教师满意的定义：1、对于每个老师，监考的场次需大致相同；2、因
8、为老师需要休息，对于每个老师，尽量不出现连续监考的情况，监考安排也需尽量均匀。 对方案使学校满意的定义：1、使考试持续的总时间尽量短；2、设计的安排方案应该简便易行，不致过于繁复，难以实现。综合考虑，最终对于监考方案的确定分四个过程：1. 将所有参加考试的科目分在不同时间段，保证每个学生不会遇到在同一时第九届华东地区大学生数学建模邀请赛论文高校大规模考试的安排方案优化 - 3 -间段考两门的情况，并且尽量使总持续时间最少。2. 为各门考试安排教室。保证在同一时间段的各个考场都能有两名监考老师，同时考虑教室的合理利用。3. 分配各门考试的时间。根据每天至多可以安排五场考试的假设将所有科目分配到天
9、，并遵循尽量使学生满意的原则。4. 为各个教师分配监考场次。每个老师尽量监考他所教授的科目，并满足使老师满意的条件。（二）模型设计1. 分配各门考试的时间。1) 步骤 1首先，为了保证考试的总持续时间最少，我们将第一个步骤归化为如下问题：某学校有 门课程 需要进行期末考试安排，同一个学生在同一时间n1,nC只能参加一门考试，求该校期末考试最少需要安排多少场次的考试。 （问题 1） 我们将看到这与下面的问题是等价的。下面（1）（3）引自参考资料1。（1）图节点着色问题1 图节点着色问题定义图的着色问题 图 G 的一个图节点着色是指 k 种颜色 1，2，.，k 对于 G的各节点的 一个分配，使得任
10、意两个相邻的节点分配以不同的颜色。而 G的色数 是指图 G 节点的着色数 k 的最小值。()2 图节点着色问题的变换定义互补图 ：图G (V，E1)，E为边的全集（任意两个属于V的节点之间都有对应边所构成的边的全体） ，则称图H(V，EE1) 为图G(V，E1)的互补图。定义图的逆着色 ：图G的一个逆着色是指 k种颜色 1，2，.，k对于G 节点的一个分配，使得一种颜色的任意两个节点都相邻。而G 的逆色数 是指G 逆()着色数k的最小值。定理：图G的互补图H的逆色数 等于图G的色数 。()H()证明：假设图G的色数 ，用k种颜色对图G进行一次实例着色，然后把图G转换为互补图H，根据定义可知这个
11、实例着色也是图G互补图H 的逆着色的一个实例，所以 ，同理可证明 ，()()HG所以 。()根据定理，图节点的着色问题可以变换为求互补图的逆着色问题从而得到解决。（2）问题 1 转化为图节点着色问题问题 1 可转化为一个图节点着色问题：G = (V，E)，其中 V(G) = C1，C2. ， Cn，每一条边 CiCj(CiCjE) 的两个端点 Ci 和 Cj 表示某一位同学的两门考试课程。于是考试能够安排的最少场次等于图 G 的色数 。由于相()第九届华东地区大学生数学建模邀请赛论文高校大规模考试的安排方案优化 - 4 -邻节点着不同色，保证了不会出现考试时间冲突。构建简单无向图 H = (V
12、，E)，其中 H(V) = D1，D2. ，Dn，每一条边DiDj(DiDjE)的两个端点 Di 和 Dj 表示这两门课程可以安排在同一场次考试。于是考试最少需要安排的场次等于图 H 的逆色数 。()显然图 H 是上述图 G 的互补图，根据定理，对求解图 G 色数和求解图 H逆色数的结果是一样的。（3）逆着色问题的解决算法由考试安排问题按节点逆着色构建的简单无向图，其节点的度数反映了对应科目和其它科目组合到一起的难易程度。不同的考试科目对应节点的度数是不均匀分布的。根据这个特点我们采用如下算法步骤。1 遍历图，找出度数大于零且度数最小的节点X。2 图是否有边存在，没有则算法结束。3 节点X是否
13、与其它节点相邻，没有则转。4 找出和节点X相邻的度数最小的节点Y。5 合并节点X和Y。6 刷新图后转。图 1：假设有 A、B、C、D、E、F 六门课，相连的两门（如 A 和 E）表示至少一位同学这两门考试课程都要考。图 2. 图 1 的补图图 3：图 2 的逆着色。解为：AB 可同时考，DE 可同时考，CF 可同时考第九届华东地区大学生数学建模邀请赛论文高校大规模考试的安排方案优化 - 5 -算法结束后图中的节点数就是图的逆着色数。需要说明的是，该算法不能保证得到最优解：我们得到的逆着色数不一定是最少的，但该算法较为简洁有效。算法的有效性见第五部分模型检验。（4）针对其他要求及程序实现的一些问
14、题的说明1 用程序实现算法（3）时必须注意的是合并节点 X 和 Y 的过程。我们注意到，该算法中的“节点”不一定是一个点；它可能是一个 K 阶完全图，K 1（经过合并后认为是一个点了） 。节点在这里定义为完全图和单一的点的并集。步骤、中的“相邻”实际指的是节点 X 与节点 Y 中任意两个单一点之间都有边相连。这时，X 与 Y 一起构成一个更高阶的完全图，从而可以合并为一个新节点。这时该算法的正确性不难加以说明：以上过程可以保证每个节点中任意两个单一点间都有边相连，因此可以着同色。最后的节点数就是图的逆着色数。2 由于我们只是假设用作考场的教室在大面积课程错开的前提下数量充足，故图 G 中任意两
15、门大面积课程间必须人为地以边相连，否则如果出现同时举办大面积考试则教室可能会不够用。3 实现算法的程序中，我们用零一矩阵（对称阵）表示图。有边连接的两点在矩阵中对应位置为 1，否则为 0。4 在输入一组学生选课表（包括总课程数和每个学生选择的课程表列）时，根据该算法可以将所有科目不相交地分划在若干个时间段内。对于确定的输入这种分划是唯一的。这样，我们就确定了需要多少个时间段完成考试，以及每一个时间段包括哪些考试。2) 步骤 2我们还需要考虑的是：对于安排在一个时间段内的所有考试，是否有足够的教师来进行监考。如果上一步给出的某时间段内同时开考的科目占用教室过多以致监考教师人数不足，则须对将这一时
16、间段的考试拆分在两个时间段中。因为教室安排时遵循的原则是使每门考试占用的教室数目尽量少，所以，第 门课程考试需要教室的数量可以由第 门课程的选修学生数除以大型教室可i i容纳的考生人数后向上取整直接求得，即，（1）iixna每个教室安排两名监考教师，则同一时间 的考试科目（假设为 ）jS1,mjjC必须满足以下不等式：（2）tjjiiNnm12其中 为监考教师总人数。tN对每一组考试，用不等式（2）进行检验，若不满足，则将其拆分为总参加考试人数近似相等的两组。 （在后面的检验中发现，这种情况很少出现） 。这样，考试全部进行完所需时间段的数目 也就确定了。sN第九届华东地区大学生数学建模邀请赛论
17、文高校大规模考试的安排方案优化 - 6 -2. 为各门考试安排教室下面我们针对一个考试时间段内一门考试 科目进行教室安排方案的说明，iC其他的每个考试科目安排方法是相同的。算法的目标是实现对于课程 ，安排最少的教室，并且在此前提下使考场i中空置的位置最少，即合理利用。由前述，假定教室有大、中、小三种规模；对于每门考试，所需教室数不会太多，可行分配方案的总数是有限的。这里采用在初步估算上限后枚举的方法，求得最佳教室组合。具体描述如下：、分别估算大、中、小教室需求的上限。如对于大教室， + 1。大 教 室 容 量本 时 间 段 考 生 总 数需 求 上 限 、对大、中、小教室数量组合在上限内进行枚
18、举。、如果某一种组合产生的教室容量超过参加考试总人数，并比上次产生的最优结果教室总容量少，那么就用这个组合更新最优解。3. 分配各门考试时间因为假设每天五个考试时间段，易得考试持续天数：（3）5sND将各个时间段考试组 分配到 天当中去。1,sNS分配时应该遵循的原则有：1、 每天安排 5 个时间段，每一个时间段都应安排考试，不留空白。这是为了使总持续时间最短。 （学校满意.2）2、 在安排考试时间段先后顺序时，应考虑该时间段内参加考试的考生总数；在一定条件下使考生多的时间段提前考。这是为了使更多的学生先结束所有考试。 （学生满意.1）3、 说明：近似认为一天当中的 5 个时间段间隔均匀，而第
19、一天的最后一次与第二天的第一次考试时间间隔是一天之内两次考试间隔的 4倍。这是因为，从早 8：00 进行第一门到晚 20：00 一天考试结束，中间经历 12 小时；从 20：00 到第二天早 8：00 又是 12 小时，相当于一天内 5 次考试的总间隔。用时间点描述：如果第一天 5 门考试安排的时间点为 1、2、3、4、5，则根据以上说明，第二天 5 门考试的时间点为 9、10、11、12、13。这些约定将在评估教师和学生的满意度中得到应用。我们设计了如下几种方案，并将在第五部分“模型检验”中确定最佳者。（1） 、先考大面积课程，再考其余课程这是题目原文中提出的一种安排方案，即在前几天中集中考
20、完所有大面积第九届华东地区大学生数学建模邀请赛论文高校大规模考试的安排方案优化 - 7 -课程，剩下课程按规模从大到小往后排。在我们的假设中，大面积课程都是单独占用一个时间段的。其余的时间段可能包含多门课程，按上述原则 1、2 安排。（2） 、先考大容量时间段，再考小容量时间段即将所有时间段 按其包含的考生总数由多到少排序，再按此顺序1,sNS排满整个日程表。（3） 、大小容量时间段交替安排即将所有时间段 按其包含的考生总数由多到少排序成1,sNS，sNiiS,.1然后按 ,., 121 sNsNiiiiS顺序排列，达到交替安排。这样做是考虑可能会使学生的考试间隔较为均衡。（学生满意.2）（4
21、） 、先考大面积课程，再考其余课程，横向分配这里解释横向分配的概念如下：1 9 17 25 332 10 18 26 343 11 19 27 354 12 20 28 365 13 21 29 37上表所示数字为 5 天的考试日程中所有安排考试的时间点。那么，顺序分配是将考试时间段依次安排到时间点 1、2、3、4、5、9、10上；横向分配则是将考试时间段依次安排到时间点 1、9、17、25、33、2上。本分配方案即先将大面积课程按容量自多至少进行横向分配，然后将其余时间段按容量多少横向分配。进行横向分配，是为了使大容量时间段和小容量时间段分配较为均衡。（ 5） 、先考大容量课程，再考小容量课
22、程，横向分配即，将即将所有时间段 按其包含的考生总数由多到少排序后进行1,sNS横向分配，排满整个日程表。至此，各门考试科目的教室安排和时间安排都已经确定。4. 为各个教师分配监考场次第九届华东地区大学生数学建模邀请赛论文高校大规模考试的安排方案优化 - 8 -前面已经保证每个时间段上监考老师数是足够的。分配时依据的算法描述如下：、每个老师的已监考次数初始化为 0。、对每一个老师 ，考察他所教授的课程是否还有考场需要监考。如果iT有，就将他分配在此考场，并将其已监考次数加 1。如果没有，则转入下一位老师 ，做同样处理，直至所有老师考察过一遍。1iT、将所有老师按已监考次数自少至多排序。、按上述
23、顺序将老师依次分配入考试日程中仍需监考的考场，以保证每个老师监考场次接近（老师满意.1）至此安排考试的全过程叙述完毕。五. 模型求解及模型检验（一）模型使用的案例的获得为了更好地检验模型是否有效、可行，首先需要一个接近实际的待安排案例。真实的学生选课情况难以获得，但可以使用计算机模拟生成。我们考虑生成一份 4800 个学生的选课情况样本。为简化问题，做出如下约定： 1 4800 个学生分布在 15 个学院中。每个学院人数各不相同，构成一个以250 为首项，10 为公差的等差数列。2 所有学生必须从 10 门大面积课程中选修 1-5 门，且同一学院的学生所修大面积课程是相同的。3 每个学院的学生
24、都有专业必修课程 2 门，且不同学院的专业必修课各不相同。4 每个学生从 8 门院系选修课程中选修 1-2 门，且不同学院具有的院选课各不相同5 每个学生从 140 门公共选修课程中选修 1-2 门。6 根据上述说明，可选课程总数是 300 门，它们都将在期末进行考试。另外的约定包括：1 大型教室可容纳的考生人数为 110。 2 中型教室可容纳的考生人数为 70。3 小型教室可容纳的考生人数为 50。运行程序，所得的案例如下所示（部分）：程序生成的学生的选课情况（部分）3 10 2 9 11 12 13 265 290 3 10 2 9 11 12 14 13 210 177 1 3 2 10
25、 21 22 25 178 244 1 3 2 10 21 22 27 25 214 271 1 3 2 10 21 22 29 30 217 186 第九届华东地区大学生数学建模邀请赛论文高校大规模考试的安排方案优化 - 9 -数字代表所选课程编号。按照上述约定，110 表示大面积课程，161300表示公共选修课，其余的是院系选修和院系必修课，每个学院的各不相同。（二）考试分段及教室分配后的结果运行图逆着色算法程序和教室分配程序之后，将 300 门待考科目分入 40 个时间段，并对每一门考试按最合理的方案分配考场。分入 40 个时间段说明 8 天时间就可以安排完所有考试，这与现实情况中许多高
26、校安排“考试周”的事实是一致的。程序运行后给出的部分结果如下：考试的时间段组合及教室分配（部分）（注：第 28 和第 29 时间段的部分考试。每行依次为：课程编号、总需教室数、大、中、小教室数）对于这个样本得到的完整的考试分段情况见下页表。Group 表示分段序号，其顺序没有意义。表格内所列各数字表示安排在这一时间段内进行考试的所有科目编号。按照我们的约定，编号的范围是 1300。 131 4 large: 3 middle: 0 small: 171 3 large: 3 middle: 0 small: 031 3 large: 2 middle: 0 small: 121 3 large: 2 middle: 0 small: 129152 4 large: 3 middle: 1 small: 0112 4 large: 2 middle: 2 small: 0
