高校智能排考系统的构建
王志刚     
西安工程大学 科技处, 陕西 西安 710048
摘要: 为实现高校排考工作的信息化、智能化,依据排考问题的各项约束条件,分析排考过程中存在的各种问题.基于高校现有的教学资源,提出一种各类排考资源在可用时间段上的最优组合方案和具体算法的设计思路,并在网络环境下进行智能排考系统模型的构建和功能的开发.测试结果表明,提出的最优组合方案在满足排考约束条件的前提下能有效解决传统手工排考过程中的资源冲突问题,所构建的智能排考系统功能简洁、操作方便,提高了排考工作的效率.
关键词: 智能排考     高校教育     遗传算法    
Design of intelligent exam-arrangement system in universities
WANG Zhigang     
Science and Technology Administration Department, Xi'an Polytechnic University, Xi'an 710048, China
Abstract: To realize the intelligence and informationization of the exam arrangement in universities, the various problems existed were analyzed. Then, relying on the teaching resources, an optimal combination scheme on the available time slots was proposed for various exam-arrangement resources, and the specific algorithm was also designed. Finally, in the network environment, an intelligent exam-arrangement system model was constructed and the corresponding system functions were developed.The test results show that under the premise to meet the constraints of the exam-arrangement, the scheme has solved the problem of resource conflict in the traditional manual exam-arrangement process. Furthermore, the developed intelligent exam-arrangement system has greatly improved the efficiency of the exam-arrangement work.
Key words: intelligent exam-arrangement    universities education    genetic algorithm    
0 引言

随着我国高校卓越工程计划的日益推进和系统创新体系的不断发展[1], 学生的培养方式趋于国际化, 学生选课方式的自主化和考试方式的多样化成为高校教务部门的日常教学管理模式.但是, 随着高校学生人数的不断扩大, 人数与现有的教学资源之间凸显出明显的比例失调, 这种比例的失调, 不但严重影响了高校的教学质量, 而且不利于高层次人才的培养, 更重要的是对高校教务部门的日常教学管理, 尤其是给教务部门的日常考试管理工作带来了较大压力.如何合理地利用现有的教育资源, 实现排考过程的智能化, 从而有效防止排考过程中的冲突问题是教育工作者急需解决的一大难题[2].

排考过程智能化是国际教育学者们研究的热点问题[3].而对于排考过程资源冲突的问题, 诸多学者提出了不同层次的解决方案, 如文献[4]研究的基于构造课程表的排考模型; Hurlburt M等[5]证明了排考问题是一个NP完全问题.随后, 一些学者将整数规划、分枝定界、线性规划等方法应用于排考过程优化, 并将其归结为一个线性优化问题[6-9].在我国, 也有大量学者对排考过程智能化进行了研究, 如徐尚进[10]研究的普通高校课务管理排考系统; 袁利永等[11]提出的基于PBIL算法的高校自动排考系统; 以及陈艮生等[13]研究的基于UML的高校排考信息系统等.针对排考过程资源冲突问题的研究, 也有学者提出了相应的优化方案、算法和模型, 他们都从数学的角度证明了其算法的可行性和优化结果的有效性, 达到了相对均匀编排的效果, 但其算法的灵活性不够[14-18].所以, 在排考算法的设计过程中, 在保证各类排考资源(如课程、学生、考场、监考教师等)无冲突的情况下, 还应充分考虑排考过程的合理性和灵活性.为此, 本文以构建网络化环境下的高校智能排考系统为切入点, 结合教学计划和各种特殊要求为约束的组合规划问题, 构建各类排考资源在可用时间段上的最优组合方案, 并进行系统建模, 以待解决排考过程中各类资源冲突的问题.

1 系统设计

高校智能排考系统的主要目标是在充分分析现有资源(如教师空余时间, 学生课程安排, 教室资源, 学生复习间隔时间, 特殊考场安排等)的前提下, 按照资源利用率在时间空间最大化原则, 系统自动为高校教务部门制定最优化的排考方案.同时, 系统还应具备如下功能:

(1) 系统管理人员能够根据学生和老师提交的信息进行“个人信息管理”, 其中包括个人信息增加、删除、修改、查询等功能.

(2) 学生在系统中只能查询“考试安排信息”、“选课信息”, 以及对“个人信息”的增加、修改、查询等, 修改后的信息必须提交给管理人员处理才能生效.

(3) 教师在系统中只能查询“监考安排信息”、“考试信息”, 以及对“个人信息”的增加、修改、查询等功能, 但是修改后的信息必须提交给管理人员处理才能生效.

(4) 具体的系统排考结果, 需要实现“考试科目顺序最优”、“考场安排及考次最优”、“考生座次最优”.

1.1 约束条件分析

采用智能排考系统的目的是提高教务部门的工作效率, 减少排考过程中的人为干预, 提升教务管理者水平.将课程、行政班、教室和教师等信息在时间和空间上, 根据不同的约束条件进行排列组合, 充分发挥各资源的优势, 尽可能避免各资源间的冲突, 实现教育资源利用率的最大化和排列组合的最优化, 从而保证整个考试的顺利进行.在排考过程中, 其约束条件可分为基本硬约束、硬约束和软约束3类[19].其中:

(1) 基本硬约束表示教师、行政班和教室等信息在时间的安排上发生冲突.在同一时间段, 同一班级不能参加两门不同课程的考试; 同一监考教师在同一时间不能安排两个考场.

(2) 硬约束表示排考过程中必须遵守的基本原则.选修同一门课程的各班级, 必须在同一时间参加考试; 针对合班上同一门课程的各个班级, 必须在同一时间参加考试; 按照考试方式, 必须安排指定的考试场地; 上课教师在排考时, 必须作为主监考.

(3) 软约束表示在排考过程中应尽可能满足的一些约束条件.每位学生在同一时刻下, 只能在一个教室进行一科考试; 每一个教室在同一时刻下, 只能有一科考试; 参加考试的学生数应不大于教室的最大容量; 教师的监考次数应均衡.

在上述3类约束条件中, 满足基本硬约束和硬约束是衡量智能排考方案是否可行的一个标准.同时, 在满足基本硬约束和硬约束的条件下, 尽可能满足软约束是衡量排考方案优劣的一个标准.

1.2 组合方案分析

排考问题就是把一周内要考的各门课程自动安排在这周的各个时间段上.现考虑一种及其简单排考情况:在不考虑班级、教师和场地的约束和冲突情况, 只需把不同的课程排在一周的不同时间段上.

假设学校的工作日为周一~周五, 并且每天安排4个时间段考试(上午两场, 下午两场), 每个时间段为两个课时, 则可安排考试的时间段为20个, 对应的表格数也为20个.现假设考试安排表中的表格数为n, 并有m门课程需要安排考试, 则可形成的考试编排组合方案为Cnm.若取m∈[1, 3], n∈[1, 20], 且m, n均为整数, 则形成的考试编排组合方案如图 1(a), (b)所示.

图 1 排考组合方案 Figure 1 Combination scheme of examination

图 1(a)可见, 当m不变, n增加时, 排考组合规划方案数量增加; 当n不变, m增加时, 排考组合规划方案数量增加; 当mn都增加时, 排考组合规划方案将急剧增加.相应地将这种mn之间的变换关系进行组合, 形成如图 1(b)所示的组合方案.这样, 当对一门课程进行排考时, 其算法形成的排列组合结果趋于平稳; 当对两门课程进行排考时, 其组合结果变化较大, 说明排考组合方案多于一门课程的排考结果; 而当对三门课程或三门以上课程进行排考时, 其排考组合方案存在多种可行性, 并且这种方案数量的急剧增加, 将产生“组合爆炸”现象[20].对于此类问题的求解, 国内外学者们进行了较为深入的研究, 提出了一些可行解, 并证明在理论研究方面是完全可行的.如乔明等[21]利用分层规划的思想, 模拟手工排考过程, 把排考问题分成若干阶段, 通过缩小求解问题空间的方法来预防“组合爆炸”; 骆绍烨等[22]研究的基于分治法的高校考试安排算法, 以及傅宇然等[23]研究的粗粒度与细粒度相结合的访问控制方法等.但在实际排考过程中, 要彻底解决这种“组合爆炸”现象, 还存在一定的难度.因为排考过程中的很多约束条件是由人为因素来支配, 而且很多约束条件很难用明确的数学公式表达.

因此, 在智能排考算法的构建过程中, 为有效防止“组合爆炸”现象的发生, 根据排考工作的业务流程和数据流程, 结合排考的基本硬约束、硬约束和软约束, 首先对排考科目进行优化, 以有效防止排考科目在考试时间段上的冲突; 然后, 尽可能地使各类排考资源(如学生、老师、教室、课程等)在考试时间段的选择上达到最优匹配, 并借助构建的智能排考系统, 对排考组合方案进行验证, 从而产生最优排考方案.

1.3 遗传算法在排考问题上的应用

排考工作实质上是一个资源交叉分配的问题, 其涉及的主要基础数据有课程、学生、教师、考场、班级以及学生选课信息等.排考工作最终的目的是使各类排考资源在有限的考试时间段最匹配, 并使考试过程得以顺利进行.为了实现排考资源在可用时间段上的最优匹配, 提出的总体设计方案为:(1) 在满足考试科目约束条件下, 进行求解满足考生时间需求的最优解A; (2) 在求得最优解A后, 进行求解满足教室时间需求的最优解B; (3) 基于最优解AB, 进行求解满足监考教师时间需求的最优解C.最后将最优解ABC进行合并, 形成可用时间段上的最优解.

最优匹配算法的设计思路为:以考试课程的结课时间为依据, 顺序查找学生选课任务表, 当某一课程需要排考时, 选取当前可用时间段, 进行已排考试科目的时间冲突检验, 若不冲突, 则选择当前时间段对应的可用教室.当该教室已安排考生且满额后, 选取当前时间段的下一可用教室.此时, 当可用时间段已排考试后, 则选取下一时间段.当某一个考试课程对应的考生较多时, 根据课程对应的参考人数, 选择当前可用时间段对应的多个教室, 并根据教室座位数之和与参考人数进行对比, 以座次人数比最小值为依据选取最优匹配方案.当选课任务表查完以后, 若当前可用时间段没有满额, 说明存在课程冲突问题, 则需进行下一时间段的排考, 依次进行所有考生考试安排.

对于排考结果正确性的检验, 一般是以排考组合方案中是否存在考生冲突为主, 即一名考生不能在同一时间参加多场考试.为了检验这个问题, 在以学年制培养方式下, 以班级为单位进行考生冲突问题的检验; 在学分制培养方式下, 面对自选课的情况则以学生为单位进行考生冲突问题的检验; 在学年制和学分制并存的培养方式下, 则先以班级为单位进行冲突检验, 然后, 再以学生为单位进行检验.检验的标准是排考结果不存在课程冲突、考试时间冲突、教室冲突、监考冲突、考生冲突, 而且考试课程分布均匀.

为达到充分利用现有教学资源, 使考试课程安排无冲突、密度均匀、缩短考期的目的, 结合排考过程所需资源, 利用遗传算法[24], 首先进行排考科目的优化, 具体过程如下.

1.3.1 变量定义

(1) 设有m门考试课程, 则对应的考试科目集合为I={1, 2, …, m}; (2) 设有n个学生选修了m门课程, 则形成的考生集合为S={S1, S2, …, Sn}; (3) 根据学生选课任务信息, 构建“考试-选课”无向图G={V, E}, 其中, V为课程集合, 且V={v1, v2, …, vm}, E为边集合, 且E={eij|i=1, 2, …, m; j=1, 2, …, m}, eij表示连接两端点vivj的同考课程; (4) 构建G的邻接矩阵A=(aij)m*m, 其为0-1对称阵, 当ij且相互之间有连通关系时, 令aij=1;否则aij=0;(5) 引入异色集C={c1, c2, …, cm}:cicj(ij; i, jI); (6) 考期为t天, 每天考l次.则总考次为q=l*t; (7) 染色种类数为P.

1.3.2 算法优化流程

针对排考问题中的考试科目优化问题, 结合上述变量的定义, 利用遗传算法进行考试-科目匹配, 即通过遗传算法对学生的考试科目进行安排, 使得在同一时间下, 选多门课程的同学只有一门课程需要考试.具体算法流程如图 2所示.

图 2 基于遗传算法的科目优化流程 Figure 2 Flow chart of subject optimization based on genetic algorithm
2 系统建模 2.1 用例图构建

智能排考系统的构建, 是基于高校现有的教学资源, 结合学生的选课情况, 利用适当的算法得出优化后的考试编排方案.在系统角色的分配上, 主要分为系统管理员、教师、学生3种, 所构建的用例图如图 3所示, 其中, 系统管理员拥有“教务信息管理”和“排考安排管理”两大权限.在“教务信息管理”中, 管理员以对教室、课程、老师、学生以及个人信息进行维护.在“排考安排管理”中, 系统管理员可对教室、课程、老师、学生四种资源进行动态分配, 并根据学生选课任务信息进行课程的考试安排.教师角色拥有“个人信息管理”和“监考信息”两种权限, 登录系统后, 可对个人信息进行维护, 也可以查询相关的监考信息.以“学生”角色登录系统后, 一方面可对个人信息、选课信息进行维护, 另一方面, 可查看个人的考试安排情况.

图 3 用例图 Figure 3 Case figure
2.2 时序图构建

智能排考系统的时序图如图 4所示.对系统管理员而言, 一方面可向学生发布每学期开设的课程, 基于学生的选课情况, 进行课程考试的安排;另一方面对老师、学生、教室、课程以及个人的信息进行增加、删除、修改、查询等操作; 学生在进入“学生信息管理”模块后, 可以查询课程信息并进行选课,当有结课考试时, 还可以查询自己的考试安排信息; 老师可以查询个人的监考安排情况.

图 4 时序图 Figure 4 Sequence diagram
2.3 类图构建

类图的构建是整个系统模型构建的核心, 其充分说明了各实体间的数据依存关系.这样, 在智能排考系统分析设计阶段中, 根据系统实体的划分, 可形成系统管理员、教师、学生、课程、教室5个静态说明性的模型元素, 其分别对应“admin”、“teacher”、“student”、“course”和“classroom”5个类图, 如图 5所示.

图 5 类图 Figure 5 Class diagram
3 系统实现

根据排考问题的各类约束条件, 对排考工作的业务管理流程和数据流程进行分析, 并针对各类排考资源在可用时间段上的最优匹配问题, 构建了排考组合方案, 同时进行了算法描述和系统建模.智能排考系统的主要管理功能包括系统管理、用户管理、课程管理、考务管理、排考管理等.各模块的主要功能如下:

(1) 系统管理:对系统用户的角色、权限进行分配和管理, 并对系统数据库进行恢复和还原, 以及为外部数据提供API接口, 方便系统数据的导入导出.

(2) 用户管理:对系统用户信息进行维护, 并进行系统功能的授权.

(3) 课程管理:从教务管理系统或通过该模块实现学生选课任务信息的导入, 使其形成考试科目信息, 从而为后期的排考提供基础数据. (4) 考务管理:进行各类排考资源信息的维护, 包括考试科目信息、教室信息、监考信息等的安排与维护.其中, “监考安排”子功能的作用是将排考结果中的每位老师需要监考的考试科目、考试地点(教室编号)、考试时间等信息显示出来.

(5) 排考管理:实现排考任务信息的生成、预处理, 以及考试时间段的选取、监考教师的调整、考场信息的维护, 同时, 可实现排考任务的开放控制, 以及排考结果有效性的控制等.一旦系统管理员将考试结果预处理完, 还需排考结果正确性的检验, 若整个过程无冲突发生, 则将排考任务开放, 使不同角色的用户登录系统后, 可实时在线查看相关课程的考试安排(包括考试科目、考试时间考场(教室编号)以及监考老师等).

4 结束语

排考问题是一个有约束的、非线性的、模糊多目标优化的、难解的、时空组合的数学问题.根据排考问题的各类约束条件, 分析高校排考过程中的实际问题, 并基于高校现有的教学资源, 对各类排考资源(如教学班、课程、教师、教室等)之间在空闲时间段选取上的冲突问题, 提出相应的解决方案, 形成最优排考组合方案, 给出一些关键算法的设计步骤.最后, 基于校园网构建开发了智能排考系统模型.系统功能测试结果表明, 所构建的智能排考系统功能简洁、操作方便, 有效地解决了传统手工排考过程中的资源冲突问题, 提高了排考工作的效率.而且, 提出的排考组合方案, 在保证排考过程最优化的基础上实现了高校现有教学资源的最大化.

参考文献
[1] 欧阳勇, 李涛. 高校自动排考系统设计与实现[J]. 湖北工业大学学报, 2009, 24(4): 69-72.
OUYANG Yong, LI Tao. Design and realization of college automatic testing arrangement system[J]. Journal of Hubei University of Technology, 2009, 24(4): 69-72.
[2] ABRAMSON D. Constructing school timetables using simulated annealing:Sequential and parallel algorithms[J]. Management Science, 1991, 37(1): 98-113.
[3] 董传良, 仝月荣, 洪奕茜. 高校选课制下自动排考系统的设计和实现[J]. 实验技术与管理, 2011, 49(6): 13-15.
DONG Chuanliang, TONG Yuerong, HONG Yixi. Design and implementation of university's automatic scheduling examination system under elective system[J]. Experimental Technology and Management, 2011, 49(6): 13-15.
[4] WIWATWISAWAKORN K, LADAVICHITKUL P. A preliminary study of distance between examination seats for preventing cheat with speed-accuracy tradeoff[J]. Lecture Notes in Engineering & Computer Science, 2011, 2189(1): 1340-1342.
[5] HURLBURT M, OTTENBACHER K J. An examination of direct selection typing rate and accuracy for persons with high-level spinal cord injury using QWERTY and default on-screen keyboards[J]. Journal of Rehabilitation Research and Development, 1992, 29(4): 54-63. DOI:10.1682/JRRD.1992.10.0054
[6] 齐萍. 基于蚁群算法的高校排课系统优化策略[J]. 湖北工业大学学报, 2010, 25(2): 68-69.
QI Ping. A study of course arrangement system's optimization strategy based on ant colony algorithm in colleges[J]. Journal of Hubei University of Technology, 2010, 25(2): 68-69.
[7] BALBIANI P.A formal examination of roles and permissions in access control[C]//The ACS/IEEE International Conference on Computer Systems and Applications.IEEE, 2005:96.
[8] KOSAKA Y, SAKUMA T. Numerical examination on scattering coefficients of architectural surfaces using the boundary element method[J]. Acoustical Science and Technology, 2005, 26(2): 136-144.
[9] SABAR N R, AYOB M, KENDALL G, et al.Roulette wheel graph coloring for solving examination timetabling problems[C]//Proceedings of the 3rd International Conference on Combinatorial Optimization and Applications.Huangshan, China 2009:463-470.
[10] 徐尚进. 普通高校课务管理排考系统的算法设计[J]. 广西科学院学报, 1998, 14(1): 40-43.
XU Shangjin. Algorithmic device for the examination arrangement system for colleges and universities[J]. Journal of Guangxi Academy of Sciences, 1998, 14(1): 40-43.
[11] 袁利永, 金炳尧, 刘日仙. 基于PBIL算法的高校自动排考系统[J]. 计算机系统应用, 2010, 19(5): 205-209.
YUAN Liyong, JIN Bingyao, LIU Rixian. University automatic examination timetabling based on the PBIL algorithm[J]. Computer Systems & Applications, 2010, 19(5): 205-209.
[12] 陈艮生, 胡荷芬. 基于UML的高校排考信息系统的设计与实现[J]. 计算机与数字工程, 2010, 38(10): 168-171.
CHEN Gensheng, HU Hefen. Design and realization of college examination arrangement information system based on UML modeling teachnology[J]. Computer and Digital Engineering, 2010, 38(10): 168-171. DOI:10.3969/j.issn.1672-9722.2010.10.048
[13] 朱书尚, 曹世勇, 邹潇湘. 排考问题的数学模型及其算法[J]. 系统工程, 1999, 17(2): 62-65.
ZHU Shushang, CAO Shiyong, ZOU Xiaoxiang. Model and algorithms for arrangement of examinations[J]. Systems Engineering, 1999, 17(2): 62-65.
[14] 王卿, 张亚文, 张伟. 高等学校排考染色匹配算法[J]. 上海理工大学学报, 2005, 27(2): 157-161.
WANG Qing, ZHANG Yawen, ZHANG Wei. Coloring-matching algorithm of the exam-arrangement for universities[J]. Journal of University of Shanghai for Science and Technology,, 2005, 27(2): 157-161.
[15] 董健兴, 栾勇, 闫君政. 基于图论的高校排考算法[J]. 计算机系统应用, 2011, 20(5): 177-179.
DONG Jianxing, LUAN Yong, YAN Junzheng. University examination timetabling algorithm[J]. Computer Systems & Applications, 2011, 20(5): 177-179.
[16] 田岭. 大学自动排考算法设计与实现[J]. 计算机工程与设计, 2007, 28(5): 2443-2445.
TIAN Ling. Design and realization of university automatic examination timetabling algorithm[J]. Computer Engineering and Design, 2007, 28(5): 2443-2445.
[17] 蔡木生. 高校自动排考算法的设计与实现[J]. 计算机工程与应用, 2010, 46(24): 73-76.
CAI Musheng. Design and realization of automatic exam-arrangement algorithm for universities[J]. Computer Engineering and Applications, 2010, 46(24): 73-76. DOI:10.3778/j.issn.1002-8331.2010.24.022
[18] 刘艳, 程国忠, 谭代伦. 学院专业课自动排考算法的设计与实现[J]. 绵阳师范学院学报, 2012, 31(2): 95-96.
LIU Yan, CHENG Guozhong, TAN Tailun. On programming auto-arrangement for examination of specialized courses[J]. Journal of Mianyang Normal University, 2012, 31(2): 95-96.
[19] OIWA K, YOSHIMATSU H, NURUKI A, et al. Examination of the influence by the stimulation coil arrangement and the shape of the stimulation object in transcranial magnetic stimulation using a model[J]. Electronics and Communications in Japan, 2016, 99(5): 20-26.
[20] HEGLER S, STATZ C, MUTZE M, et al. Simulative ultrasonic examination of pitch-catch arrangements for huge cylindrical steel hubs and gradient-based imaging[J]. Technisches Messen, 2015, 82(9): 440-450.
[21] Sun Xuecheng. A hybrid genetic algorithm for make-up examination arrangement[J]. Institute of Electrical and Electronics Engineers Inc, ICMTAM, 2015: 10-13.
[22] 骆绍烨. 基于分治法的高校考试安排算法[J]. 长春工业大学学报(自然科学版), 2012, 33(2): 193-196.
LUO Shaoye. An algorithm for university exam arrangement based on division method[J]. Journal of Changchun Univ of Technol (Natural Science Edition), 2012, 33(2): 193-196.
[23] 傅宇然. 考务系统的访问控制与排考算法研究[D]. 南京航空航天大学硕士论文, 2009.
FU Yuran.The research of access control and examination arrangement algorithm in examination system[D].Nanjing:Nanjing University of Aeronautics and Astronautics, 2009. http://cdmd.cnki.com.cn/Article/CDMD-10287-2010081788.htm
[24] 陈圣群, 董林飞. Dijkstra和A-star算法在智能导航中的应用分析[J]. 重庆科技学院学报(自然科学版), 2010, 17(6): 164-166.
CHEN Shengqun, DONG Linfei. Applied analysis of Dijkstra algorithm and A-star algorithm in the intelligent guiding[J]. Journal of Chongqing University of Science and Technology (Natural Sciences Edition), 2010, 17(6): 164-166.
西安工程大学主办。
0

文章信息

王志刚
WANG Zhigang
高校智能排考系统的构建
Design of intelligent exam-arrangement system in universities
西安工程大学学报, 2017, 31(4): 556-562
Journal of Xi′an Polytechnic University, 2017, 31(4): 556-562

文章历史

收稿日期: 2017-03-10

相关文章

工作空间