高校大规模考试的安排专项方案优化.doc

高校大规模考试安排方案优化摘要本文对高校大规模考试合理安排问题进行了研究和探讨。由于高校在校学生增多，学校在安排期终考试等大型考试时总会遇到各种难题，如，1、必要保证不会浮现同一学生有两门考试时间冲突状况；2、尽量使一种学生各门考试间隔较为均衡；3、合理运用容量不同考场；4、使每个监考教师监考日程比较平均，且保证不发生某一时段监考教师 局限性现象。本文采用图论中逆着色算法解决问题1，并设计程序依照已知各种教室规模给出分派考场最优方案以解决问题3。为了满足2和4，咱们将讨论几种考试时间分派方案并从中得到令学生、教师以及学校都满意最优者。为了检查模型科学性与可行性，咱们设计了一种选课程序，使得可以运用计算机对大批量学生选课状况进行模仿，以得到一种较为接近实际选课总表。依照这份数据样本，咱们检查了上述所有算法实现状况，证明了模型合理性。并且基于运用这份样本所做学生和教师对考试安排满意度分析，咱们最后拟定了一种考试时间分派方案，从而完整地解决了提出问题。核心字：考试安排 逆着色算法 满意度一. 问题重述由于高校在校学生增多，学校在安排期终考试时总会遇到各种难题，如不能错开学生各门课考试时间，监考教师局限性，或学生参加考试时间过于集中。这些问题在大面积课程， 如高等数学和线性代数考试，和某些全校性选修课考试时非常明显。普通做法是选修课程和必修课程分开，各有一周考试时间，选修课随堂考；大面积课程另行安排-普通这样使得大面积课程考试和其她必修课程考试同步进行，增长安排难度。咱们但愿针对这些问题设计一种学生、教师和学校都满意方案。归纳起来欲解决问题有：1. 必要保证不会浮现同一学生有两门考试时间冲突；2. 合理运用容量不同考场；3. 安排应尽量合理，使学生、教师和学校都满意。考虑到实际高校规模，这个建模问题只有在做到用计算机进行大样本仿真解决状况下才算得到真正意义上解决：手工安排显然是难以完毕。对问题3解决状况评估也建立在对大样本记录分析基本上。二. 基本假设1. 选同一门课程所有学生一起参加该课程考试，不考虑上学时逻辑班级。2. 一种学校学生选课状况足够交错复杂以致能排在同一时间考试科目不会过多，且用作考场教室在大面积课程错开前提下数量充分。3. 教室有大、中、小三种规模。4. 每天至多可以安排五个时间段考试。5. 学生选课状况已知。三. 符号阐明：第门课程：监考教师数量：大型教室可容纳考生人数：中型教室可容纳考生人数：小型教室可容纳考生人数：第个考试时间段：考试总天数：学生满意度：教师满意度四. 问题分析及模型建立（一）问题分析容易看出错开各个学生考试时间是安排方案前提规定：存在学生考试时间冲突考试安排方案无疑是失败。本文通过运用图论中着色算法保证考试无冲突，并遵循时间尽量短原则。再通过进一步调节各场考试，满足题目别的规定。在实际状况中，考试往往是合卷进行，即选同一门课学生考卷是相似，必要在同一时间进行考试。这样一来，考试安排时可以以考试科目作为其区别唯一标记。学校考试中存在全年级大某些学生都修读大面积课程例如大学英语、微积分等。这些课程，一种学生往往会同步选取，并且选取人数众多，导致安排考试过程中种种困难：例如，教室安排。教室是考试安排中一种重要资源，虽然没有任何冲突，一门考试课程也也许会由于没有足够教室而无法安排在某一指定期间。这里为了简化而不考虑上述状况，即，咱们以为只要大面积考试不同步浮现，就有足够教室用于安排同一时间所有考试。这是基于假设2“一种学校学生选课状况足够交错复杂以致能排在同一时间考试科目不会过多”。并且考虑到当前许多大学大规模校区教学楼总有足够备用教室和自习教室，咱们以为这样简化是合乎情理。在计算机仿真检查中，咱们发现对于大面积课程，程序必然安排给它较多大型教室，故咱们给大型教室数目加了上限20，这对整个模型没有太大影响。按普通状况，每场考试持续两个小时，咱们假设每天至多可以安排五场考试，即，上午两场，下午两场以及晚上一场。为使问题明确，咱们对几种规定理解如下： 对教师充分理解：即，在同一时间进行考试每个考场必要有两名教师监考且任何教师不能同步监考两个考场。在此基本上，每个教师尽量监考她所专家科目。 对教室分派合理理解：在安排每门考试时，以占用教室数至少为原则；在此基本上，使对于每间考场，空置位置至少。 对方案使学生满意定义：1、 对每个学生，相邻考试考试间隔尽量均匀。2、 学生普通是但愿能尽快结束考试。为了做到这一点，咱们在决定考试日程方案时总是考虑把考生更多时间段放在前面。 对方案使教师满意定义：1、 对于每个教师，监考场次需大体相似；2、 由于教师需要休息，对于每个教师，尽量不浮现持续监考状况，监考安排也需尽量均匀。 对方案使学校满意定义：1、 使考试持续总时间尽量短；2、设计安排方案应当简便易行，不致过于繁复，难以实现。综合考虑，最后对于监考方案拟定分四个过程：1. 将所有参加考试科目分在不同步间段，保证每个学生不会遇到在同一时间段考两门状况，并且尽量使总持续时间至少。2. 为各门考试安排教室。保证在同一时间段各个考场都能有两名监考教师，同步考虑教室合理运用。3. 分派各门考试时间。依照每天至多可以安排五场考试假设将所有科目分派到天，并遵循尽量使学生满意原则。4. 为各个教师分派监考场次。每个教师尽量监考她所专家科目，并满足使教师满意条件。（二）模型设计1. 分派各门考试时间。1) 环节1一方面，为了保证考试总持续时间至少，咱们将第一种环节归化为如下问题：某学校有门课程需要进行期末考试安排，同一种学生在同一时间只能参加一门考试，求该校期末考试至少需要安排多少场次考试。（问题1） 咱们将看到这与下面问题是等价。下面（1）（3）引自参照资料1。（1）图节点着色问题 图节点着色问题定义图着色问题图G一种图节点着色是指k种颜色1，2，.，k对于G各节点一种分派，使得任意两个相邻节点分派以不同颜色。而G色数是指图G节点着色数k最小值。 图节点着色问题变换定义互补图：图G (V，E1)，E为边全集（任意两个属于V节点之间均有相应边所构成边全体），则称图H(V，EE1)为图G(V，E1)互补图。定义图逆着色：图G一种逆着色是指k种颜色1，2，.，k对于G节点一个分派，使得一种颜色任意两个节点都相邻。而G逆色数是指G逆着色数k最小值。定理：图G互补图H逆色数等于图G色数。证明：假设图G色数 ，用k种颜色对图G进行一次实例着色，然后把图G转换为互补图H，依照定义可知这个实例着色也是图G互补图H 逆着色一种实例，因此，同理可证明，因此。依照定理，图节点着色问题可以变换为求互补图逆着色问题从而得到解决。（2）问题1转化为图节点着色问题问题1可转化为一种图节点着色问题：G = (V，E)，其中V(G) = C1，C2.，Cn，每一条边CiCj(CiCjE)两个端点Ci和Cj表达某一位同窗两门考试课程。于是考试可以安排至少场次等于图G色数。由于相邻节点着不同色，保证了不会浮现考试时间冲突。构建简朴无向图H = (V，E)，其中H(V) = D1，D2.，Dn，每一条边DiDj(DiDjE)两个端点Di和Dj表达这两门课程可以安排在同一场次考试。于是考试至少需要安排场次等于图H逆色数。显然图H是上述图G互补图，依照定理，对求解图G色数和求解图H逆色数成果是同样。图1：假设有A、B、C、D、E、F六门课，相连两门（如A和E）表达至少一位同窗这两门考试课程都要考。图3：图2逆着色。解为：AB可同步考，DE可同步考，CF可同步考图2. 图1补图（3）逆着色问题解决算法由考试安排问题按节点逆着色构建简朴无向图，其节点度数反映了相应科目和其他科目组合到一起难易限度。不同考试科目相应节点度数是不均匀分布。依照这个特点咱们采用如下算法环节。 遍历图，找出度数不不大于零且度数最小节点X。 图与否有边存在，没有则算法结束。 节点X与否与其他节点相邻，没有则转。 找出和节点X相邻度数最小节点Y。 合并节点X和Y。 刷新图后转。算法结束后图中节点数就是图逆着色数。需要阐明是，该算法不能保证得到最优解：咱们得到逆着色数不一定是至少，但该算法较为简洁有效。算法有效性见第五某些模型检查。（4）针对其她规定及程序实现某些问题阐明 用程序实现算法（3）时必要注意是合并节点X和Y过程。咱们注意到，该算法中“节点”不一定是一种点；它也许是一种K阶完全图，K 1（通过合并后以为是一种点了）。节点在这里定义为完全图和单一点并集。环节、中“相邻”实际指是节点X与节点Y中任意两个单一点之间均有边相连。这时，X与Y一起构成一种更高阶完全图，从而可以合并为一种新节点。这时该算法对的性不难加以阐明：以上过程可以保证每个节点中任意两个单一点间均有边相连，因而可以着同色。最后节点数就是图逆着色数。 由于咱们只是假设用作考场教室在大面积课程错开前提下数量充分，故图G中任意两门大面积课程间必要人为地以边相连，否则如果浮现同步举办大面积考试则教室也许会不够用。 实现算法程序中，咱们用零一矩阵（对称阵）表达图。有边连接两点在矩阵中相应位置为1，否则为0。 在输入一组学生选课表（涉及总课程数和每个学生选取课程表列）时，依照该算法可以将所有科目不相交地分划在若干个时间段内。对于拟定输入这种分划是唯一。这样，咱们就拟定了需要多少个时间段完毕考试，以及每一种时间段涉及哪些考试。2) 环节2咱们还需要考虑是：对于安排在一种时间段内所有考试，与否有足够教师来进行监考。如果上一步给出某时间段内同步开考科目占用教室过多以致监考教师人数局限性，则须对将这一时间段考试拆分在两个时间段中。由于教室安排时遵循原则是使每门考试占用教室数目尽量少，因此，第门课程考试需要教室数量可以由第门课程选修学生数除以大型教室可容纳考生人数后向上取整直接求得，即， （1）每个教室安排两名监考教师，则同一时间考试科目（假设为）必要满足如下不等式： （2）其中为监考教师总人数。对每一组考试，用不等式（2）进行检查，若不满足，则将其拆分为总参加考试人数近似相等两组。（在背面检查中发现，这种状况很少浮现）。这样，考试所有进行完所需时间段数目也就拟定了。2. 为各门考试安排教室下面咱们针对一种考试时间段内一门考试科目进行教室安排方案阐明，其她每个考试科目安排办法是相似。算法目的是实现对于课程，安排至少教室，并且在此前提下使考场中空置位置至少，即合理运用。由前述，假定教室有大、中、小三种规模；对于每门考试，所需教室数不会太多，可行分派方案总数是有限。这里采用在初步估算上限后枚举办法，求得最佳教室组合。详细描述如下：、分别估算大、中、小教室需求上限。如对于大教室， + 1。、对大、中、小教室数量组合在上限内进行枚举。、如果某一种组合产生教室容量超过参加考试总人数，并比上次产生最优成果教室总容量少，那么就用这个组合更新最优解。3. 分派各门考试时间由于假设每天五个考试时间段，易得考试持续天数： （3）将各个时间段考试组分派到天当中去。分派时应当遵循原则有：1、 每天安排5个时间段，每一种时间段都应安排考试，不留空白。这是为了使总持续时间最短。（学校满意.2）2、 在安排考试时间段先后顺序时，应考虑该时间段内参加考试考生总数；在一定条件下使考生多时间段提前考。这是为了使更多学生先结束所有考试。（学生满意.1）3、 阐明：近似以为一天当中5个时间段间隔均匀，而第一天最后一次与第二天第一次考试时间间隔是一天之内两次考试间隔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）、先考大面积课程，再考别的课程这是题目原文中提出一种安排方案，即在前几天中集中考完所有大面积课程，剩余课程按规模从大到小往后排。在咱们假设中，大面积课程都是单独占用一种时间段。别的时间段也许包括多门课程，按上述原则1、2安排。（2）、先考大容量时间段，再考小容量时间段即将所有时间段按其包括考生总数由多到少排序，再按此顺序排满整个日程表。（3）、大小容量时间段交替安排即将所有时间段按其包括考生总数由多到少排序成，然后按顺序排列，达到交替安排。这样做是考虑也许会使学生考试间隔较为均衡。（学生满意.2）（4）、先考大面积课程，再考别的课程，横向分派这里解释横向分派概念如下：19172533210182634311192735412202836513212937上表所示数字为5天考试日程中所有安排考试时间点。那么，顺序分派是将考试时间段依次安排届时间点1、2、3、4、5、9、10上；横向分派则是将考试时间段依次安排届时间点1、9、17、25、33、2上。本分派方案即先将大面积课程按容量自多至少进行横向分派，然后将别的时间段按容量多少横向分派。进行横向分派，是为了使大容量时间段和小容量时间段分派较为均衡。（5）、先考大容量课程，再考小容量课程，横向分派即，将即将所有时间段按其包括考生总数由多到少排序后进行横向分派，排满整个日程表。至此，各门考试科目教室安排和时间安排都已经拟定。4. 为各个教师分派监考场次前面已经保证每个时间段上监考教师数是足够。分派时根据算法描述如下：、每个教师已监考次数初始化为0。、对每一种教师，考察她所专家课程与否尚有考场需要监考。如果有，就将她分派在此考场，并将其已监考次数加1。如果没有，则转入下一位教师，做同样解决，直至所有教师考察过一遍。、将所有教师按已监考次数自少至多排序。、按上述顺序将教师依次分派入考试日程中仍需监考考场，以保证每个教师监考场次接近（教师满意.1）至此安排考试全过程论述完毕。五. 模型求解及模型检查（一）模型使用案例获得为了更好地检查模型与否有效、可行，一方面需要一种接近实际待安排案例。真实学生选课状况难以获得，但可以使用计算机模仿生成。咱们考虑生成一份4800个学生选课状况样本。为简化问题，做出如下商定： 4800个学生分布在15个学院中。每个学院人数各不相似，构成一种以250为首项，10为公差等差数列。 所有学生必要从10门大面积课程中选修1-5门，且同一学院学生所修大面积课程是相似。 每个学院学生均有专业必修课程2门，且不同窗院专业必修课各不相似。 每个学生从8门院系选修课程中选修1-2门，且不同窗院具备院选课各不相似 每个学生从140门公共选修课程中选修1-2门。 依照上述阐明，可选课程总数是300门，它们都将在期末进行考试。此外商定涉及： 大型教室可容纳考生人数为110。 中型教室可容纳考生人数为70。 小型教室可容纳考生人数为50。运营程序，所得案例如下所示（某些）：程序生成学生选课状况（某些）3 10 2 9 11 12 13 265 290 3 10 2 9 11 12 14 13 210 177 1 3 2 10 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 数字代表所选课程编号。按照上述商定，110表达大面积课程，161300表达公共选修课，别的是院系选修和院系必修课，每个学院各不相似。（二）考试分段及教室分派后成果运营图逆着色算法程序和教室分派程序之后，将300门待考科目分入40个时间段，并对每一门考试按最合理方案分派考场。分入40个时间段阐明8天时间就可以安排完所有考试，这与现状中许多高校安排“考试周”事实是一致。程序运营后给出某些成果如下：考试时间段组合及教室分派（某些） 1314large：3middle：0small：1713large：3middle：0small：0313large：2middle：0small：1213large：2middle：0small：1291524large：3middle：1small：01124large：2middle：2small：0 （注：第28和第29时间段某些考试。每行依次为：课程编号、总需教室数、大、中、小教室数）对于这个样本得到完整考试分段状况见下页表。Group 表达分段序号，其顺序没故意义。表格内所列各数字表达安排在这一时间段内进行考试所有科目编号。按照咱们商定，编号范畴是1300。Group1Group2Group3Group4Group5Group6Group7Group8Group9Group10199 264254 6756 140128 8319 3323 4529029619220525928922721728227617523228829921420119527527426628618325829222526819126721124116729419718626219818425624027824229126118220614948388030257168178252293279263298170238188181277243213287234237173224244228247250Group11Group12Group13Group14Group15Group16Group17Group18Group19Group20233 160119 10599 144129 7060 14139 7837 2950231209265189176246281223187222185235226271219190285221216270273236171248284251220180280249163196215179283260203253297245212255177165904313429516916616120419320223921026974174200272207229300Group21Group22Group23Group24Group25Group26Group27Group28Group29Group3016223016417221820819415912011010015013089695920138794028491581181099814812788685818137773927471571171089714712687665717136763626461561161079614612586655516135753525441551151069514512485645415133733424421541141049414312384635313132723222411531131039314212282625212131713121152112102921411218161511115111110191Group31Group32Group33Group34Group35Group36Group37Group38Group39Group4010987654321（三）考试安排各方案实现在模型建立某些咱们给出了五种将各个考试时间段安排到天方案。下面图表描述了按照不同方案考试人数随时间变化规律。 图中横轴表达准时间先后安排考试场次（共计40场），纵轴表达在本时间段内参加考试考生总数。（1）、先考大面积课程，再考别的课程前10个时间段安排是10门大面积课程；背面自多至少安排别的时间段考试。（2）、先考大容量时间段，再考小容量时间段（3）、大小容量时间段交替安排（4）、先考大面积课程，再考别的课程，横向分派（5）、先考大容量课程，再考小容量课程，横向分派 （四）监考教师安排在模型中，咱们假设每门课监考教师人数与该课总选修学生数正有关。为了使监考教师数尽量少以检查模型有效性，还做出如下假设：参加监考教师中，一某些是专家大面积课程，另一某些是专家院系选修或必修课程；若一门大面积课程总学生数是，则该科教师参加监考人数是。若一门院系课程总学生数是，则该科教师参加监考人数是。依照以上两条假定拟定监考教师总人数及其构成，并按模型中指明算法为每个教师分派监考场次。运营程序得到教师监考安排如下所示 (某些)： 175135193552185135193552195551935522055519355221555193452 （注：其中每行第一种数为教师编号；第二个数为其监考次数；背面数是有她参加监考时间点。详细是什么科目并未显示）（五）最后安排方案拟定为了对以上五种安排方案给出评估，需要对每种方案下学生和教师满意限度进行定量计算和分析。对于学生，参照对“学生满意”定义，第一条已保证满足，只需考虑考试安排均匀限度这一种因素影响。假设满意度与均匀限度线性有关。考试安排均匀限度由相邻考试间隔方差表达，其数值越大，均匀限度越低。进而，学生满意度可以由方差倒数表达，其数值越大，满意度越高。例如某个学生共有顺序排列n门考试，则可计算每持续两门考试之间间隔（指时间段，用考试相应时间点差值表达，为一非负整数）为。则对于这个学生，她考试安排均匀限度 该学生满意度为依照咱们样本进行计算发现这个值太小（量级），因而采用作为满意度计算成果。 咱们用所有学生满意度均值作为评价每种方案优劣指标之一。对于教师，状况是完全类似。参照对“教师满意”定义，咱们用教师监考持续两场考试之间时间间隔方差倒数十倍表征这个教师满意限度，用所有教师满意度均值作为评价每种方案优劣指标之一。基于以上讨论咱们可以对五种安排考试方案进行评估了。计算得对于每种方案，学生与教师满意度如下表所示：教师满意度学生满意度方案10.15860.3306方案20.08590.2857方案30.25220.3764方案40.06590.4593方案50.1670.529为更直观地阐明状况，以直方图表达如下： 可以看出不同安排方案导致了满意度明显差别。综合看来，方案5（先考大容量课程，再考小容量课程，横向分派）是使学生和教师最满意安排方案：学生满意度居各种方案之首，教师满意度居第二。六. 模型评价与改进安排考试方案是一种较为复杂问题。咱们建立模型将这个问题进行拆分并各个击破，使用计算机模仿验证了模型有效性，并通过实验提出了较为合理方案。关于这个模型改进：1、考察咱们使用4800名学生选课样本，从规模和选课构造上看，它更接近于高校某一种年级选课状况，而不是高校所有学生。由于高校不同年级选课构造，如大面积课程选修数、院系必修和选修课程数等都存在一定差别，如果考虑进来将协助咱们得到更加精准模型，为咱们设计选课方案提供更为可信资料。2、通过观测几种考试安排方案时间-容量曲线，比照其优劣排名，发现一种规律：曲线震荡限度影响学生和教师满意度；震荡频率增大时教师满意度提高，振幅接近稳定期学生满意度提高。这为提出更好方案提供了思路：如果将这种震荡细化到每天，也许会提出令教师和学生更为满意方案。但依照对“学校满意”定义第二条，过度追求满意度也许会使方案过于繁复而难以实现。既有方案操作原则是较为简要，易于实现。3、咱们采用图逆着色算法解决考试能否安排在同一时间点问题，事实上有更为优越算法可以用在这里，如“蚁群算法”等，但是要复杂得多。如果尝试使用这些算法，也许会得到更好成果。参照书目参照文献：1 常蓬浩，王晓兰，艾莉，康艳萍，图节点着色问题变换及算法，甘肃科技，第22巷第l1期：143-144，1 张华，王秀坤，孙焘，蚁群算法在考试安排中应用，计算机工程与设计，第24卷第12期：62-64，2 陈越，一种通用型学分制系统考试自动编排系统设计，苏州大学学报，第19卷第2期：66-69，3 Mark Allen Weiss，数据构造与算法分析，北京：机械工业出版社，.1附录： 附1：随机生成学生选课样本程序int main() srand(unsigned)time(NULL); for(i = 0；i college；i+) col_sel(i); choose(1，foundamental，num_gonggong); for(j = 0；j num_gonggong；j+) if(tempj != 0) stu_courj = tempj;/*公共课*/ else stu_courj = 0; for(j = 0；j num_bixiu；j+) stu_courj + num_gonggong = college_selectj;/*院必修课*/ for(k = 0；k col_numi；k+) first = college_selectnum_bixiu; last = college_selectcollege_course - 1; choose(first，last，num_yuanxuan); for(j = num_gonggong + num_bixiu；j num_gonggong + num_bixiu + num_yuanxuan；j+) if(tempj - num_gonggong - num_bixiu != 0) stu_courj = tempj - num_gonggong - num_bixiu;/*院选修课*/ else stu_courj = 0; first = foundamental + college * college_course + 1; last = courses； choose(first，last，num_gongxuan); for(j = num_gonggong + num_bixiu + num_yuanxuan；j course_max；j +) if(tempj - (num_gonggong + num_bixiu + num_yuanxuan) != 0) stu_courj = tempj - (num_gonggong + num_bixiu + num_yuanxuan)； else stu_courj = 0； /*公选课*/ for(j = 0；j capacity = head-large = head-mid = head-small = 0;head-cla_num = 0;cla * p = 0;int cap_now = 0;int l_max = 0，m_max = 0，s_max = 0;int l = 0，m = 0，s = -1;l_max = stu_num / l_cap + 1;m_max = stu_num / m_cap + 1;s_max = stu_num / s_cap + 1;while (s s_max) m = -1;s+;while (m m_max) l = -1;m+;while (l l_max & l capacity !=0) if (cap_now head-capacity | head-cla_num cla_num = (l + m + s) & head -capacity capacity = cap_now;head -large = l;head -mid = m;head -small = s;head -cla_num = l + m + s;else if(cap_now = stu_num) head -capacity = cap_now;head -large = l;head -mid = m;head -small = s;head -cla_num = l + m + s;return head;附3：逆着色算法函数clas* get_painted (int relationclas_numclas_num，int student_sumclas_num) clas *head = new clas;int k = 0;for(int i = 0；i clas_num；i+)for(int j = 0；j bro = head -next = NULL;head -stu = 0;head -nam = -1;head -in_degree =