第 1 章 绪论
1.1 研究背景
随着诸多高校搬迁至较远新校区，教师往返路途成本越来越高，传统的考试编排过程中并没有考虑到这一因素，安排结果对于同一天每一学院的考试场次并不均衡，导致教师监考往返次数较多，班车派送次数增多，产生较高路途费用，未能达到节省路途成本的目的。过去采取人工排考的方式进行期末考试安排工作，工作量大消耗了较多的时间和人力。并且因像教师资源、考试任务、监考老师、学生等多重因素影响，管理人员排考要付出极大的心力。如今学校搬迁，各校区合并排考任务越发繁重，过去的研究虽然可以适应教师往返市区和校区时间成本大的新情况，但是在资源公平性分配、评价指标、对约束及手工编辑的部分存在空缺或者不足，传统的排考体系无法适应新环境下高校考试体系相关问题。
考试编排过程一类为一级监考安排，即具体安排到监考教师；另一类为二级监考，即完成学校教务处对考试的编排，具体指派监考教师的任务由学院自行安排。二级监考中的一级监考安排及优化问题成为本研究的着眼点。本论文充分考虑教师监考路途成本因素，通过满足考试编排时间不冲突性、参考班级不重复性等硬性约束条件，尽可能优化考试场次的均衡性、学生考试时间间隔合理性等约束条件，达到考试安排的相对最优化。
........................
1.2 研究目标及意义
本研究的目标旨在有机结合包括考试时间、课程、教室资源、班级、学生等在内的各排考资源，在满足各硬性条件的基础上，实现均衡优化学生同一天考试场次，考生的每门考试课程之间有一定的时间间隔、同一门课程考试占用的考场距离较近等软约束，在前人研究的研究模型上，提出一种改进的基于贪心退火算法的划分方法，从而得到优化的考试安排结果下达至具体学院，实现考试的二级安排，便于各学院合理调派监考教师进行监考。同时引入编排效果评价体系以实现资源分配结果的优化，提高教师及学生对考试安排的满意度，提高教务处工作人员的工作效率，将考试管理人员从繁重的工作中解脱出来，通过同一天同一学院考试场次均衡等软约束的优化降低教师监考往返次数从而节省高校监考路途成本。
研究的实施意义在于可以解决新校区启用后教师关注的核心监考问题，综合提升教师对教学管理的整体满意度。同时考试编排算法还可以监考集中时段充分有效的调度班车资源，避免不必要的班车派送过程，节省路途成本。该研究还可以减轻考试科人员工作负担，提升信息化教学管理水平。研究对促进教学工作，提高教学质量的作用主要体现在：
1）减轻繁重工作，提高监考编排效率。人工考试安排的工作量非常繁重，容易产生各种问题且不容易排查和修改，存在工作效率低，容易出错等问题。通过计算机智能计算法完成考试编排可以大幅减轻人工工作压力。
2）优化监考安排，让监考教师在一次往返过程中完成更多监考任务，降低学校班车派送成本及教师路途成本。
3）有效利用资源，提升教学管理水平。综合协调学生、教师、课程和教室资源配置，提高尽可能多的人员满意度，进而提升整体教学管理水平。
本研究充分遵循研究需求，在提高公平性的基础上，极大地解放了研究的劳动力，又能充分利用教室、教师资源，减少时间成本，满足个性化需求，实现智能排考的目标，并且支持多维度的排考结果评价，是实现考试安排信息化的重要举措。
本研究对算法的优化可广泛应用于多目标优化问题的解决中，研究不仅满足高校考试合理化安排，并对其进行优化，从而达到节省路途成本的目的，是新时代高校解决分校区、校区偏远等问题的有利解决方案[1]。同时引入排考结果评价体系，真正将排考结果应用于高校考试工作中，通过多方打分反馈结果，从而调整编排方式方法，使结果达到最优化，该设计具有广泛的应用价值。
...........................
第 2 章 算法概述
2.1 贪心算法
本设计体系将贪心算法与模拟退火算法结合使用，弥补单一算法存在的不足之处，旨在达到算法的最优化，更优化的解决考试编排问题。
贪心算法，是指未从整体最优的层面考虑，仅着眼于是否是现阶段最好的选择求解问题。此种算法可理解为基于某种意义的局部最优解[23]。采用此算法关键在于选择贪心策略，应选择符合无后效性的贪心决策，即以后的状态不会受以前状态的影响，仅关于当前的问题，并不是所有问题都能够通过该策略法获得整体最优解。
贪心选择的实现是采用该算法获得进步的主要因素，同时这也是本算法区别于动态规划算法的主要体现。贪心选择在选择时需要基于迭代、从上而下进行选择，进行一次贪心选择相当于对问题进行简化处理，使之成为规模更小的子问题。任何问题都应明确问题本身的性质是否符合贪心选择，应确保所有贪心选择能够最优解问题[25]。一般可证明贪心选择是最优解问题的开始，同时进行贪心选择后让具有简化原问题，使之成为类似的子问题的作用[26]。在此基础上利用数学归纳法进行总结分析，针对问题每次都进行贪心选择，最终确定整体最优解。假设一个问题的最优解同时含有其它问题的最优解，则说明该问题的性质符合最优子结构的特点，每一次转化贪心策略都能够实现最优解。利用动态规则算法、贪心算法可获得问题最优子结构性质。每一次采用该算法均会直接影响结果，而动态规则一般不会产生影响。贪心算法是不可回退的，是需要逐一选择所有子问题，而如果采用动态规则进行当前选择，则一般需要结合以往的选择，有回退功能。动态规划主要运用于二维或三维问题，贪心算法通常为一维问题[27]。
一般认为可采用贪婪算法解决的问题具有下述特点：
1）在采用该算法解决问题时，将逐渐形成两个集合：其中一个候选对象是已经被考虑并包含其中了；另一个候选对象虽然被考虑过，但是当前已经被丢弃了。
2）利用一个函数检查集合另一个候选对象，分析其中是否解答了问题。该寒湿不考虑当下已经形成了最优的解决方案[28]。
3）检查集合一个候选对象时利用了另一个函数检查。简而言之可理解为添加更多的候选对象至集合中以获得解。同上述函数一样，此时可忽视最优解决方法。
4）通过函数的选择可针对问题说明剩余候选函数的解。
5）最后，结合目标函数确定解值。
.........................
2.2 模拟退火算法
模拟退火算法是基于概率而形成的算法，即固体退火。充分加温固体温度之后，在使其温度逐渐冷却下来，固体内部粒子随着温度的增加，其逐渐变为无序的状态，增大内能，而随着温度的冷却则逐渐降低温度。当所有的温度均处于平衡状态时，常温下即可达到基态，同时此时的内能是最小的[30]。
1953 年 N. Metropolis 等人率先提出该算法。30 年后，S. Kirkpatrick 成功的在组合优化领域中引入该算法。该随机寻优算法，是基于 Monte-Carlo 迭代求解策略而形成的。算法是基于一般优化问题与固体物质退火过程两者间具有相似性而提出的。在实际运用该算法中通常是基于某一初温（有一定温度）下形成的。在解究竟中概率突跳特性随着不断下降的温度参数而基于目标函数形成全局最优解，即局部最优解可实现概率性跳出并趋于全局最优[31]。该算法作为通用算法，具有诸多优势。从理论层面分析该算法具有概率全局优化的性能特点。当前在信号处理、生产调度、机器学习以及 VISI 等各类工程中均普遍应用到模拟退火算法。该算法赋予了搜索过程一个概率突跳性。同时该突变性具有时变性，最终趋于零。此法不仅能够有效预防出现局部极小的情况，同时最终形成的优化串行结构的算法，可实现全局最优。
正如上文所述该算法是基于固体退火原理而形成的，即在充分加温固体后让其自然冷却。固体内部粒子在加温的过程随着温度的变化而处于无序的状态之中，从而进一步扩大内能；而随着固体温度重新下降后，其粒子又重新变得有序，温度重新回到平衡状态。常温下固体到达基态，此时内能最小化[32]。结合 Metropolis 进行分析，在温度为 T 时，粒子将概率趋于平衡。上式中 E 用于表示温度为 T 时，粒子的内能。ΔE 用于表示改变量，k 用于表示 Boltzmann 常数。针对问题采用固体退火模拟法进行模拟，通过模拟用目标函数 f 表示 E，同时演化温度 T，并用参数t 表示，通过该算法即可获得最优问题。该算法的基本步骤是结合 i、t 分别用于表示初始解、控制参数初值。并对当前的解进行重复迭代。其具体步骤是形成新解——对目标函数进行计算——决定舍弃或者接受，t 值在这一个过程中处于逐渐衰减的状态之中，终止算法后所形成的当前解，可理解为所得近似最优解。该搜索过程中基于启发式随机的蒙特卡罗迭算法而求解的[33]。冷却进度控制着整个退火过程。具体而言主要控制如下参数：其一是停止条件 S；其二是 t 值的迭代次数，一般用L 表示；其三是衰减因子 Δt；其四是初值 t。
...............................
第 3 章 方案设计 ........................................ 15
3.1 整体方案设计 ....................................... 153.2 核心概念界定 ............................... 15
第 4 章 方案实施 .................................... 28
4.1 整体数据描述 ........................................ 28
4.2 基于排考均匀度的算法实现 ................................. 28
第 5 章 优缺点分析与展望 ...................................... 35
5.1 优缺点分析 ............................................ 35
5.1.1 优点分析 ......................................... 35
5.1.2 不足分析 ................................. 35
第 4 章 方案实施
4.1 整体数据描述
本论文的研究数据来自 H 大学 C 校区教务系统 2017-2018 秋季学期第 18 周的监考任务安排，涉及 24 个学院，175 个课程组、544 门课程、3155 个课程班排考，具体安排的考试时间为第 18 周周一至周五的考试，可用时间段为第 18 周周一至周五每天 4 个考试时间段。
18 周具体考试计划已由各学院上报汇总完毕，基础数据信息包括课程名称、课程号，课序号、参考班级、涉及学院等基础信息。所用教室为 H 学校 C 校区核心教学楼内可用于监考的教室，编号为 A101、B201、C205、D305 等共计 167 间教室，教室可容纳的考生人数不尽相同，分别为 30-160 人不等。
按照学校相关规定，学生人数在 75 人以内需要安排两名监考教师，以后每增加 30 学生需增加一名监考教师。由于监考数据量非常庞大，传统手工排考尽管能够完成排考任务，但由于未能充分考虑路途成本因素，导致某学院某天不同场次监考人数极度不均衡。
........................
第 5 章 优缺点分析与展望
5.1 优缺点分析
5.1.1 优点分析
参考文献（略）