一种解决排考资源冲突的优化方法

邵景峰，厉 谦，畅朝霞

（1.西安工程大学 管理学院，陕西 西安710048；2.西安工程大学 艺术工程学院，陕西 西安710048；3.西安工程大学 图书馆，陕西 西安710048）

面对我国高校因扩招而带来的教育资源配置不足与培养方式多样化之间，以及教学资源短缺与考试方式多元化之间日益严重的矛盾，如何在各高校开展教育国际化和协同创新体系下，为适应新时代的要求，实现学生考试管理方式的智能化就显得十分必要［1］.借助Web of Science数据库，以“arrangement examination”为主题词进行文献检索，发现国外学者对排考问题的研究相对较早，是始于1964年.当然，在此期间也对排考资源冲突问题进行了深入探讨，如Brocklesby J［2］构建的排考系统模型，Hamazaki Hironori等人［3］提出的基于改进遗传算法的排考方法，以及Carter M W在1986年研究的基于时间段优化的排考算法等，目的是使各类排考资源（如教室、监考教师、座次等）在考试时间段的选择上达到最优匹配.在考试编排方法不断改进的过程中，也有学者对排考资源冲突问题进行了算法优化，如Acharyya Arnav等人［4］提出的搜索算法以及Abramson D等人［5］研究的考场编排算法等.在我国，对排考资源冲突问题的研究可追踪到1998年，如徐尚进［6］研究的普通高校课务管理排考系统的算法设计，朱书尚和曹世勇等人［7］研究的关于排考问题的数学模型及其算法等.在此期间，一些国内学者针对不同应用环境下的排考问题给出不同的解决方案，如田岭［8］提出的大学自动排考算法；蔡木生［9］研究的高校自动排考算法；刘艳等人［10］研究的学院专业课自动排考算法的设计与实现等，都从数学的角度证明了其算法的可行性.当然，也有人从图论模型的角度给出了一些优化方法，如王卿等人 提出的高等学校排考染色－匹配算法；董健兴等人［12］提出的基于图论的高校排考算法等，期待解决排考资源冲突问题和排考过程优化问题.

通过文献回顾，发现国内外学者对排考资源冲突问题的研究主要针对排考算法的设计和优化，并没有对排考过程中所涉及到的诸如时间段问题、考场资源问题、座位资源等问题进行较深入研究，也没有从整体上加以考虑.本文首先从排考实际存在的问题作为切入点，深入分析排考资源间的逻辑关系；然后，从考场的编排、监考的编排，以及座次的编排过程入手，对各类排考资源在最优考试时间选择上的冲突问题进行逐步算法描述和流程设计，并实现整体优化；其次，通过智能排考系统的构建，来验证算法的可行性和合理性，以期解决排考资源在时间段选择上的冲突问题.

1 排考问题分析

排考过程所设涉及的对象主要有：学生（参加考试的对象）、课程（被选择的对象）、选课记录（排考的对象）、教室（场所对象）、教师（监考对象）、考试时间（包括：每场考试的时间和考试分布的时间段，即考期）等，这些对象在数据结构上具有数据重用性，而且，每个对象之间在时间上还具有一定的相关性，使得一个对象的变换往往涉及到多个对象数据内容的变换，往往牵一发而动全身，要真正实现排考过程的最优化，则需要在多约束条件下，通过多种优化规则，使现有的对象在编排过程中最大程度地达到最优化.当然，要使现有的对象得到优化，其首要解决的问题是进行选课体系的优化，尽可能避免课程冲突问题［13］.尤其是在高校内部相近专业的排考过程中，更要解决好如下问题：（1）课程名称相同，但课时、学分不同的情况；（2）不同专业学生，选修同一门课程的情况；（3）不同校区、选修同一门课程的情况；（4）在教室教师资源有限、安排同一门课程考试的情况.

2 排考问题描述

要解决好排考问题，首先应理顺与排考工作相关的数据流和业务流.其中，数据流来源于学生对象、课程对象、选课对象.现令集合S＝ ｛s1，s2，…，sm｝、C＝ ｛c1，c2，…，cn｝、SC ＝ ｛sc1，sc2，…，sck｝分别表示学生、课程、选课对象集合，其中：m、n、k分别表示学生数、课程数、选课记录数.由于sci（i＝1，2，…）的取值范围源于si和ci，使得S中的一条记录可对应C中的多条记录，而C中的一条记录也可对应S中的多条记录.显然，S与C之间是一种多对多关系，学生、选课、课程三者间的关系图如图1所示.

在保证基础数据正确的前提下，对于同一门课程的考试编排，通常规定必须安排在同一时间段进行考试，尤其是面对高校多校区的情况时，更应注重同一门课程安排在同一时间段进行.当然，在智能排考过程中，要保证这种管理规定得以顺利进行，前提条件就是确保每门考试课程在考试资源的分配上无冲突，而检验有无冲突的基本判断方法是在同一时间段内，一个考生只能在一个考场参与一门课程的考试.

为了更加直观地检验排考过程是否存在冲突问题，在图1的基础上，特选取五门课程作为一学期学生的选修课，结果见表1.由此构建的学生、课程、选课三者间关系所对应的带权的无向图，如图2所示，其中，图的顶点表示五门课程，而边表示同时选修了相关课程的学生人数.

表1 五门课程的学生选课结果表

图1 学生、选课、课程三者间的关系图

通过图2，借助无向图的顶点个数和边所对应的权，可以构建一个邻接矩阵M，使M ＝（mij）n＊n，其中，i，j≤n且mij＝mji，即矩阵M存在对称关系，并且主对角线元素全为0.这样，矩阵M的元素存在如下关系：

图2 带权的选课信息无向图

通过邻接矩阵M的构建，可见在同一时间段，为节约教室资源，对同一考场而言，考试课程间的关系仅有两种表示方式，即相容（不存在一个学生同时选修两门课程的情况）；相斥（存在至少有一个学生同时选修两门课程的情况）［14］.为此，用0表示相容，则两门课程同时安排在同一考场的条件完全满足；而用1表示相斥，则两门课程同时安排在同一考场会引起课程冲突.

这样，为了尽可能避免同场次考试课程间的冲突问题，还需对邻接矩阵M＝（mij）n＊n进一步简化，可得到矩阵M对应的一个课程关系矩阵C＝（cij）n＊n，其中，cij＝cji，即矩阵C也存在对称关系，其主对角线全为0，则

由课程关系矩阵C，则可得到如下两类数据：

（2）与第i门课程相容的课程数N，其由满足cij＝0（0≤j＜n且j≠i）条件的所有课程组成.

由关系矩阵C得出的两类数据可见，在整个智能排考过程中，为使整个排考结果得以合理优化，其首要条件是必须保证“考试课程之间在资源分配上无冲突”.当然，在这个前提下，要实现教育资源利用率的最大化，整个排考过程还应遵循如下原则：

（1）要使课程关系矩阵C存在近似解或可行解，必须使考试资源（教师、教室、学生、课程）在空闲时间的分配上达到最优；

（2）当存在大型考试、集中考试或连考情形时，参加考试的学生人均场次数的间隔应尽可能大，让学生有尽可能多的时间进行复习，并使考试资源（教师、教室、学生、课程）在空闲时间上得到合理分配和利用.

3 相关算法的构建

3.1 考场安排算法

考场安排是考试管理环节中的一项重要工作，其科学合理的考场编排方法既可以提高教务工作者的工作效率，又可以在一定程度上促进高等教育信息化的发展.为此，在编排考场时，首先需解决的问题是如何将选修同一门课程的学生或同一个教学班的学生在同一考场中选课顺序进行随机编排，并让排考系统随机分配座位，以体现考试过程的公平性和公正性，从根本上杜绝考试舞弊现象的发生.

考场编排算法设计的基本思想是：首先在教室信息表ClassRoom中选择“空闲”教室信息资源，并将“空闲”教室资源信息按教室类型（多媒体教室、画室、普通教室等）、座位数n（n≤40，40＜n≤80，80＜n）大小进行排序并分类；然后，将其排序分类结果依次存入预先设计好的教室临时时间队列数据表Temproom1，Temproom2，Temproom3中；其次，选取待排考的课程信息ci，每门课程对应的选课人数kij（第i门课程的学生人数有j位），以及教室座位数n.若该选课任务所对应的课程还没有安排考场，则该教学班的课程将满足排考条件，并将选课任务按照属性“考试时间段”进行降序排列，依次存入课程临时队列数据表Tempcourse中.对每门课程而言，在排考过程中，需进行选课人数及考生数kij与座位数n之间的除操作，整个过程以占用教室资源数最少，且kij能整除n为最佳.

在考场编排过程中，还应根据考试数量的多少安排相应的监考教师，此时，应从表Tempcourse中选取首条记录，并根据Tempcourse中的开课学院信息，开始检索教师信息表，从中选取“是否排考”字段值为空的教师职工号，构造考试任务链表 Examin－Duty－Link（Number－Time，Number－Course，ClassRoom－Array，Number－Student，ClassRoom－Type，Number－ClassRoom）；以及考场链表 ClassRoom－Link（Number－ClassRoom，ClassRoom－Type，ClassRoom－Prior，Number－Seat），以初始化链表并将考场链表 Class－Room－Link按ClassRoom－Prior优先级的先后顺序进行排序.同时，若考试任务对考场有特殊需求，则按考场类型（ClassRoom－Type）进行排序，采用最佳拟合方案为每个考试任务安排考场，并存入教师临时空闲时间队列数据表Tempteacher中进行匹配排考.在此过程中，若匹配失败，则数据库指针下调一位，继续查询“是否排考”字段值为空的教师，直到满足条件为止；否则，删除Tempcourse表中已经匹配的考试课程，并将最终考场结果存入Course链表的教室编号节点字段.周而复始，直到Tempcourse表中的全部课程被匹配为止.

依据上述考场编排算法，将其应用到智能排考系统之中，形成“考场安排”功能模块，如图3所示.其中，主要包括单个学生的考试科目、考试时间、考试批次、考场（教室编号）以及考试备注等信息.

图3 考场安排结果

图4 监考安排结果

3.2 监考编排算法

根据3.1的考场编排算法，在监考教师编排算法的设计过程中，首先从课程表Course中选取任课教师作为主监考；然后从教室表ClassRoom中获取教室座位数n（n≤40，40＜n≤80，n＞80），并根据座位数n来设置主监考与副监考的比例（1∶1，1∶2，1∶3）；其次，从监考教师链表SuperExaminTeacher（Superexamin－ID，Superexamin－Name，Right－Superexamin，Time－Superexamin，Number－Superexamin）选 择该时间段其属性值（Time－Superexamin）为“空闲”的教师作为副监考，并使监考教师的监考场次数（Number－Superexamin）加1；最后，根据上述基础数据的设置，进行数据链表的初始化，将监考教师链表按监考场次（Right－Superexamin）顺序进行倒序排序，以构造考试任务链表 Examin－Duty－Link（Number－Time，Number－Course，ClassRoom－Array，Number－Student，ClassRoom－Type，Number－ClassRoom）.

按照监考编排算法的描述过程，借助智能排考系统获取课程信息、学生选课信息、教师信息，以及教室信息等基础数据，进行算法过程的可行性和合理性验证，其模块的界面如图4所示.

3.3 考场座次编排算法

3.3.1 算法设计 设某课程的考试涉及到m个教学班的n个考生，并将每个教学班的考生分别用集合A1，A2，…，Am表示，这样Ai可用集合Ai＝ ｛ai1，ai2，…，aik｝来表示，且k∈ ［0，n］.同时存在关系n＝A1，A2，…，Am.基于此，考场座次编排算法的设计思路为：基于混洗算法的基本思想［16］，先设n＝A1，将其看成一个其前后可插入新元素的环；然后，依次将各集合Ai（i＝2，…，n）中的元素顺序插入到环n中的相邻元素之间，插完为止，最终形成更大的环n；其次，依据考场编排算法，确定各考场的规定人数s，将全部考生n均匀分散到n／s个考场中去.

3.3.2 算法结果分析 现获取学生选课任务信息进行考场座次编排结果的功能测试，并依据3.1的考场编排算法描述过程，将各个教学班的选课学生均匀地分配到各个考场，且考场座位编排结果如图5所示.可见该算法完全可以满足多校区多门课程在同一时间段考试的编排工作，并且考场座位编排结果显示，选修同一门课程的学生其前后位置并不是同一教学班或学号相连的考生，这充分体现了考试过程的公平性和公正性，从根本上杜绝了考试舞弊现象的发生.

3.3.3 算法复杂度分析 为了分析种算法的复杂度，现定义如下变量：n为所有课程的选课总人数，m为根据校区、行政班、选课课程进行分组的组数，k为参加考试的每组人数，i为每个k所需要的考场数，s为每个k所对应的考生人数，f为某个教学班的选课人数.这样，利用线性随机方法［17］，通过3.1考场编排算法为每个考生所产生的随机数进行排序，然后结合每个考场的考场号、座位号，进行数据组合形成考生的准考证号或考试号，而这个过程正好是一个线性变换的过程，其时间复杂度为O（n）.同时，假设排序的时间复杂度为O（nlgn），则再根据二重循环，系统生成考场号、座位号的过程的时间复杂度为O（m＊i＊s），故线性随机方法的复杂度为O（n）＋O（nlgn）＋O（m＊i＊s）.

图5 考场座位编排结果

根据算法的设计思路，具体的伪代码如下：

在对考生编排考场号和座位号之前，算法过程还要对选修每门课程的所有考生进行重新排序，以得到一个新的队列，使得每次插入一个新的考生，队列中的对象都要执行加1操作，所以，总的算法复杂度为O（n）＋O（nlgn）＋O（m＊（O（k2）＋O（klgk）＋O（j＊s））.

4 结束语

排考是各高校教务管理部门的一项十分重要又相当复杂的工作，其直接目的是为学校各教学部门开设的课程安排合理的考试时间、地点、监考教师，从而使高校的教学工作得顺利进行.为此，首先对如何实现智能排考，以及排考过程中存在什么样的问题进行了分析；其次，在网络环境下，借助高校教务管理系统，研制了一种智能排考系统，验证了排考算法的合理性和有效性.最后，通过系统功能测试，结果表明，所构建的最优匹配算法具有较好的灵活性和简洁性，较好地解决了传统手工排考过程中的随意性和重复性，并且避免了排考过程中的人为干预.同时，智能排考系统的实现，一方面优化了高校教务排考工作的业务流程，提高了教学资源的利用率；另一方面，实现了排考过程的自动化，降低了繁重的人工手工统计工作，很大程度上提高了教务工作效率，促进了高校教育信息化的发展.

［1］YUANG Ping.Institutional arrangements and construction safety in China：An empirical examination［J］.Construction Management and Economics，2009，27（5）：439－450.

［2］BROCKLESBY J.Using the viable systems model to examine multi－agency arrangements for combatting transnational organised crime［J］.Journal of the Operational Research Society，2012，63（3）：418－430.

［3］HAMAZAKI Y，HIRONORI J，FUJITA W，et al.Examination of the proper arrangement of damper by using the improved GA ［J］.Transactions of the Japan Society of Mechanical Engineers，Part C，2002，68（9）：2577－2584.

［4］ACHARYYA Arnav，Losalka Arpan，GUPTA Pravir Singh，et al.Development of an automated examination seating arrangement generation system using music inspired harmony search algorithm［J］.Advances in Intelligent and Soft Computing，2011，130（1）：301－309.

［5］Abramson D.Constructing school timetables using simulated annealing：Sequential and parallel algorithms［J］.Management Science，1991，37（1）：98－113.

［6］徐尚进.普通高校课务管理排考系统的算法设计［J］.广西科学院学报，1998，14（1）：40－43.

［7］朱书尚，曹世勇，邹潇湘.排考问题的数学模型及其算法［J］.系统工程，1999，17（2）：62－65.

［8］田岭.大学自动排考算法设计与实现［J］.计算机工程与设计，2007，28（5）：2443－2445.

［9］蔡木生.高校自动排考算法的设计与实现［J］.计算机工程与应用，2010，48（24）：73－76.

［10］刘艳，程国忠，谭代伦.学院专业课自动排考算法的设计与实现［J］.绵阳师范学院学报，2012，30（2）：95－99.

［11］王卿，张亚文，张伟.高等学校排考染色匹配算法［J］.上海理工大学学报，2005，27（2）：157－161.

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

［13］董传良，仝月荣，洪奕茜.高校选课制下自动排考系统的设计和实现［J］.实验技术与管理，2011，49（6）：13－15.

［14］齐萍.基于蚁群算法的高校排课系统优化策略［J］.湖北工业大学学报，2010，16（02）：35－90.

［15］刘莹.高校教学管理信息系统的设计与实现［D］.济南：山东大学，2009：15－18.

［16］HAN K H，KIM J H.On the analysis of the quantum－inspired evolutionary algorithm with a single individual［J］.Evolutionary Computation，2006，13（4）：517－546.

［17］欧阳勇，李涛.高校自动排考系统设计与实现［J］.湖北工业大学学报，2009，27（4）：69－72.