关于高路途成本下监考安排算法优化的若干思考

王妍 吕震宇

摘 要：排考问题是对考生、考场、时间、考试科目和监考人员等因素进行配置的决策性问题。考试编排直接决定着教师能否更为有效地完成监考工作，且编排过程中需尽可能降低监考路途成本，这就要求考试编排在满足众多约束条件的同时要尽可能确保均衡。文章对优化高路途成本下监考安排算法的意义、国内外相关研究及本问题的研究前景进行了分析。

关键词：高路途成本；监考安排；算法；优化

中图分类号：TP301.6文献标识码：A收稿日期：2017-12-22

一、优化高路途成本下监考安排算法的意义

（1）减轻繁重工作，提高监考编排效率。人工考试安排的工作量非常繁重，容易产生各种问题且不容易排查和修改，存在工作效率低、容易出错等问题。通过计算机智能计算法完成考试编排可以大幅减轻人工工作压力。

（2）优化监考安排，让监考教师在一次往返过程中完成更多监考任务，降低学校班车派送成本及教师路途成本。

（3）有效利用资源，提升教学管理水平。综合协调学生、教师、课程和教室资源配置，提高尽可能多的人员的满意度，进而提升整体教学管理水平。

二、国内外关于排考安排的相关研究

由于排考问题的普遍性和复杂性，国外研究者已投入研究力量寻找解决方案。Carter 等（1996） 最早提出了监考编排问题，并设计了一个EXAMINE 系统，采用序列建构方法寻找最优解。Casey 和 Thompson（2003）将约束分为硬约束与软约束，采用两阶段方法寻找解决方案，即第一阶段对教师资源进行排序，按硬约束分配教师资源，第二阶段采用退火算法安排教师资源，以满足软约束。根据这一算法，Casey 和Thompson 设计了一个系统，即 GRASP。Banerjee S等（2004）提出了一种改进的模拟退火算法，在代价函数和解空间方面都有所改进，但模拟退火算法解的初始化比较耗时，对大任务集来说，收敛速度依旧缓慢。Ulker 等（2007）使用遗传算法对该问题进行了分析，但结果并不比以前的方法好。Caramia 等（2008）采用三阶段法来解决监考安排问题，即先使用贪婪算法依照优先级分配教师资源，然后使用惩罚递减因子（Penalty decreaser）减少软约束成本，最后使用惩罚交易因子（Penalty trader）对监考安排进行必要的修正。

国内的学者也对此类问题进行了相关研究。张华、王秀坤和孙焘（2003）利用蚁群算法，结合图论中的着色和运筹学背包问题，对考试安排这一问题进行了求解[1]。王亚敏、冀俊忠（2009）利用基于时间序列的粒子编码方式和更新算子，建立了考试安排的粒子群求解模型，并结合简化邻域算法给出了改进策略。仿真实验结果表明，其算法及策略有效。上述研究尽管应用了信息技术或智能搜索算法实现自动排考，但仅考虑了约束条件的满足，而没有考虑目标的优化。徐欣等（2010）构建的“期末考试监考安排的数学模型”具有优化目标，即监考次数最多的教师与监考次数最少的教师的监考总次数相差最小[2]。但实际中监考次数往往是教学秘书在平均化的基础上根据各教师的实际情况进行调整，如某教师在学期初参加了补考的监考，则其在期末考试时可以少参加监考，因此，徐欣模型的优化目标与实际情况有所出入。

总之，目前国内外相应的考试安排软约束的优化较为缺乏，尤其是节省路途成本这一因素，这是本研究力求解决之处。

三、优化高路途成本下监考安排算法的前景展望

从应用领域看，是对考试安排的智能优化，各高校都面临考试安排的工作量大、数据关系复杂的问题，该项目具有很好的应用价值；从问题本质看，考试安排是时间表问题，时间表问题属于多目标优化问题，多目标优化对于高校合理利用教学资源等方面有很好的应用价值。对算法的优化可广泛应用于多目标优化问题的解决中，研究不仅满足高校考试合理化安排的需要，并对其进行优化，从而达到节省路途成本的目的，是新时代高校解决分校区、校区偏远等问题的有利解决方案，同时引入排考结果评价体系，真正将排考结果应用于高校考试工作中，通过多方打分反馈结果，从而调整编排方式方法，使结果达到最优化，该研究具有广泛的应用前景。

参考文献：

[1]张 华，王秀坤，孙 焘.蚁群算法在考试安排中的应用[J].计算机工程与设计，2003（12）：62-64.

[2]徐 欣，翟金剛，刘晓华.期末考试监考安排的数学模型[J].数学的实践与认识，2010（23）.