监考安排的研究11

监考安排的研究监考安排的研究 华东师范大学 章皓 王天浩 王鹏 监考安排的研究1 摘要摘要 排考问题因有限资源的限制和学校 讲师 学生间多对多的复杂关系 一 直都没有找到非常完美的模型 本文通过对学校 讲师 学生三方面满意度的 量化处理 确定了一个粗略的数学模型 在对该模型的算法复杂度进行分析的 基础上 提出了一个优化模型的方法 并完成了一个易于在计算机上实现的算 法的设计 在论文中 我们详细地阐明了该算法的原理 首先 我们用多目标 指数模糊矩阵来刻化每门课程的规模 并按规模从大到小分别对每门课程进行 安排 在时间的安排上 我们引入了冲突数 并按照学生不冲突 不连堂 一 天考试科目适中 考试日程分布均匀的顺序使用贪婪算法 greedy method 选 出能达到最大满意度的时间元 在 大面积课程 的处理上 通过隔天排考 显著地降低了学生的负担 然后 在对应课程考场的选择上 我们仍然通过先 排序的方法来降低循环次数 在提高教室利用率的问题上 我们使用了同一课 程不同讲师的学生合并的方法 有效提高了教室的使用率 由于讲师安排的灵 活度高 且已按讲师对修读同一课程的学生进行了分类 这些都降低了监考教 师安排的难度 通过以上方法的处理 本文较好地处理了学校 讲师 学生之 间的矛盾 创造性地提出了问题的解决方案 关键词关键词 排考问题 贪婪算法 greedy method 多目标指数模糊矩阵 多阶段规划 监考安排的研究2 1 问题重述 由于高校的在校学生的增多 学校在安排期终考试时总会碰到各种难题 如不能错开学生的各门课的考试时间 监考教师不足 或学生参加考试时间过 于集中 这些问题在大面积课程 如高等数学和线性代数的考试 和一些全校 性的选修课的考试时非常明显 通常的做法是选修课程和必修课程分开 各有 一周考试时间 选修课随堂考 大面积课程另行安排 通常这样使得大面积课 程的考试和其他必修课程考试同时进行 增加安排的难度 考试安排的困难还 包括 教室的容量要比考室的容量多得多 上同一门课的学生分在不同的考室 每个考室又必须有两名教师监考 这使得教师数量不足 每个学生相邻两门课 考试时间间隔时长时短 容量不同的考室如何合理使用 等等 就选修课监考 大面积考试监考安排 或者你认为的监考安排中其它重要的 问题讨论什么方案 才是学生 教师和学校都满意的方案 2 模型假设 1 为了考试公平 同一科目的考试应在同一时间进行 2 每个考室需要监考老师两名 3 每个考试日进行四场考试 上 下午各两场 4 教师数目大于等于教室数目的两倍 即教师数足以满足任意场次的监考需求 5 同一教室一个场次只进行一个科目的考试 6 教室容量足以满足任意一次大面积课程的考试 7 每一考场所安排的考生数不能大于该考场预定的考试容量 3 符号说明 考试时间 m 表示第 m 个考试日 n 表示当天的第 n 场考试 t m n 课程与当前场次上已排课程的学生冲突数 v i m n i C t m n 第 d 个教室的使用情况矩阵 Y d 第 h 个学生的考试日程表 Z h 一幢教学楼的所有教室的编号矩阵 D i j 某特定时间元 t 上教室的编号矩阵 D i j t 4 问题分析 4 1 监考安排的原则监考安排的原则 4 1 1 有利于充分利用时间 空间和人力资源的原则 排考问题具有一定的复杂性 涉及时间 教室 教师 班级 课程等数 据对象 安排监考的模型目标是为满足学校 教师和学生三方面的需求 进 监考安排的研究3 行合理的资源分配 核心问题是避免资源冲突 4 1 2 兼顾利益的原则 在监考的安排中 我们要综合考虑学校 教师和学生三方面的需求 比 如尽量避免学生出现连堂考的情况 协调彼此的关系 避免厚此薄彼 但 是由于排考问题的复杂性 要想做到面面俱到十分困难 如果初始条件过于 苛刻 则很有可能导致一个可行解也找不到 为此我们引入 贪婪算法 Greedy method 先在较低要求下获得多个可行解 再逐步地增强约束条 件来优化运算结果 力求满足更高的要求 4 2 学校 教师 学生需求的分析学校 教师 学生需求的分析 4 2 1 学校的需求 基本需求 考试持续时间不能超过预先安排的时间 较高需求 教师的总监考次数尽可能少 等价地 即教室的使用次数尽 可能少 因为需要为老师的监考支付劳动报酬 减少监考次 数可以降低学校的开支 4 2 2 教师的需求 基本需求 1 监考次数适中 每个老师的监考次数平均分配 2 年龄大的老师不宜安排在上午第一堂考试 较高需求 1 自己所教的学生在考试时安排在一起 如果学生较多不能 放在同一考室时 则安排在距离较近的几个考室 2 不要连堂监考 4 2 3 学生的需求 基本需求 各堂考试不能冲突 较高需求 1 不要连堂考试 2 每天的考试场数不要太多 3 各科考试在考试日程中均匀分布 总之 一个合理的安排方案应该是在最大程度地满足各级基本需求的基础 上 追求满足更多更高的要求 这样才能使学校 教师 学生都达到相当的满 意程度 5 模型的建立 5 1 数据的组织数据的组织 5 1 1 课程及相关信息数据表 可将与课程相关的信息组织成下表 课程编号 Course No 修读人数 Stu number 讲师人数 Teacher number 学 生 ID Stu ID 教师 ID Teacher ID 000011002STU1TID1 监考安排的研究4 00002 120 2 STU2 TID2 为修读该门课程的所有学生的学号 ID 的集合 为教授该门课程的所有讲师的工号 ID 的集合 表 1 5 1 2 教室资源使用情况表 由于在排考程序的运行中要实时地调用教室资源的使用情况 所以将它 们组织成下表 记录教室的基本信息 并实时地对其使用情况进行修改 由 于在不同的场次教室资源可以重复地使用 所以我们加入时间维度 t t 一 i一 p q 一 一 一 一 一 一 一 一 D i j t 一 i 1一 i j 100 t 4 m 1 n一 一 m n 一 一 m一 一 一 n一 一 一 一 一 t 一 一 一 t 1 1 一 一 一 一 一 一 一 一 一 一 一 D i j i j 100一 一 一 i一 一 一 j一 一 一 一 一 一 100 i j 1 146 i 1 j 40 i 1 j 1 50 t 1 一 t 1 1 t 5 一 t 2 1 图 1 5 1 3 学生及所修课程信息表 为方便检索同一时段考试中同时考多门课程 即考试冲突了 的学生的 数目 我们用一个修读信息表来记录每个学生该学期修读的课程 学生姓名学生 ID修读课程一修读课程二 张三05001001高等代数数学分析 李四 05001002 高等代数 解析几何 表 2 5 2 一个粗略的模型一个粗略的模型 5 2 1 学校 教师 学生三方面需求的量化 假设已得到某个安排考试的方法 Mthd 即我们已经得到两组信息矩阵 任意第 d 个教室的使用矩阵 000 11121 21222 12 01 m n m n ij KKKm n ydydyd ydydyd Y dyd ydydyd 或 监考安排的研究5 其中表示第 d 个教室在第 j 个时间元进行第 i 门课程的考试 否 1 ij yd 则 0 ij yd 任意第 h 个学生的考试日程表 000 11121 21222 12 01 m n m n ij KKKm n zhzhzh zhzhzh Z hzh zhzhzh 或 其中表示第 h 个学生在第 j 个时间元进行第 i 门课程的考试 否 1 ij zh 则 0 ij zh 这些矩阵中应该满足一些量化的关系 1 学校的教室资源总数一定 设为 0 M 2 学校的教师数目一定 设为 0 N 根据假设 我们有 00 2NM 3 课程数目一定 设为 0 K 4 某间考室某一时间只能考一个科目 0 0 1 1 1 1 K ij i ydjm ndM 5 某学生某时间元应只能在一间考室考试 0 0 1 1 1 1 K ij i zhjm nhZ 6 考室的使用次数 00 111 MK m n mthdij dji Uyd 7 教师的总监考次数 00 111 22 MK m n mthdmthdij dji UUyd 5 2 2 初步的模型 一般说来 如果严格遵循 5 1 4 中 6 的条件 很可能没有可行解 所以 我们在这里引入所有学生总的冲突数这个概念 即允许有小部分学生发生冲突 监考安排的研究6 00 111 1 ZK m n mthdij hji Vzh 模型的目标就是使得冲突数和教室的使用次数最小 根据上面的量化指标 我们可以得到一个排考问题的粗略的数学模型 Min 12mthdmthd fcVc U s t 0 0 1 1 1 1 K ij i ydjm ndM 6 模型的优化与求解模型的优化与求解 虽然上面给出的模型思想明确 结构简单 但我们发现上述模型运算次数 过多 很难通过计算机编程来实现 假设某所高校有 400 间教室 5000 名学生 并开设了 400 门课程 按照上面的模型 经过估算 我们将需要得到超过 10600 张表 包括教室使用表和学生考试日程表 从如此庞大的数据中来搜索最优解 是不可能实现的 因此 我们需要优化上述模型 寻找一个可行的排考方案 为此我们引入 了程序编辑中著名的贪婪算法 Greedy method 在贪婪算法 greedy method 中采用逐步构造最优解的方法 在每个阶段 都作出一个看上去最优的决策 在一定的标准下 在计算过程中不断剔除相对 劣等的可行解 减小了数据搜索的范围 进而减少了计算次数 作出贪婪决策 的依据称为贪婪准则 greedy criterion 本模型中的贪婪准则就是不断满足更 高的需求 6 1 考试日程的安排考试日程的安排 6 1 1 课程的重排 由于规模大的课程 即所谓的 大面积课程 涉及面广 便容易与其 他课程的考试发生冲突 并且修读这类课程的学生人数也较多 占用的考 场资源也相对较大 所以我们在排考的过程中 应该优先考虑 大面积课 程 从教务处档案中调出的课程数据表往往按系别排序 每门课程的覆盖面 积 即修读该门课程的学生所涉及的院系数目 和修读人数都比较杂乱无 章 这就要求我们按照能反映课程规模的规则对课程进行重新排列 在此我们引入模糊综合指数对课程的规模进行评价 设关系矩阵为 R 权重向量为 W 多指标综合评价矩阵为 B 其中 为第 j 个院系学生中修读第 i 门课程的人数 111 ij 1 R m nnm rr r rr ij r 为第 i 个院系对应的权值 满足为院系总数 ii W 1 1 m m i i 于是我们就得到一个多指标综合评价矩阵 1 T n BWRbb 监考安排的研究7 其中 bi表征了第 i 个课程的规模大小 由于大院系人数众多 往往有 牵一发而动全身 的影响 所以我们在 权重函数的构造上应该给大院系以较大的权值 为此我们设权重函数 1 i im i i n n 其中为第 i 个院系的人数 i n 根据 bi的相对大小可以得到课程的新的按规模从大到小的排序 而且 显然上文提到的所谓 大面积课程 将获得较大的评价指标值 从而排 在靠前的位置 6 1 2 考试日程安排的具体方法 设 5 2 1 中得到的课程重排序列为 按照 i 从小到 1 i CCim 大的顺序为 Ci选择合适的考试时间 假设当前需排的课程为 计算与当前场次 m 表示第 m i C i C t m n 个考试日 n 表示当天的第 n 场考试 已排课程的学生冲突数 v i m n 1 j k ii j v i m nf C C 其中为已安排在时间段进行考试的科目 的值等于需 j i C v i m n j ii f C C 要同时参加与两个科目考试的学生数目 i C j i C 这里需要定义一个可以接受的冲突数 只要通过计算所得的不高 v i m n 于且中剩余考场的总容量大于修读的总人数 我们就认为可以在 t m n i C 上为安排考室 对于可安排考试的时间集合 按冲突数 t m n i C i C i T 从小到大对中的元素进行排列 冲突越小的时间元越先考虑 如果 v i m n i T 有多个时间元的相等 则分别考虑该课程与上 下两场考试中已 v i m n 安排课程的冲突数和 其中 即每天 1 v i m n 1 v i m n 114n 第一场考试不考虑与其上一场考试的冲突数 最后一场不考虑与其下一 场考试的冲突数 如此计算得到的冲突数实际上是有连堂考的考生人数 在此基础上选择出有连堂考试的考生最少的时间元集合 如 11 iii T TT 监考安排的研究8 果这个集合的元素仍不唯一 则计算此门课程与当天已安排的所有课程 的冲突数 这里的冲突数就是同一天内参加多场考试的考 v i m v i m 生人数 选择出此数值最小的时间元集合 如果中的时间 221 iii T TT 2 i T 元还不唯一 则考虑参加该堂考试的考生的考试日程均衡性 避免单个 考生考试出现时紧时松的情况 特别地 如果过于苛刻 这里介绍的筛选方法可能出现一个极端 情况 这时我们把放入集合 F 中 认为排考失败 留作后续 i T i C 处理 见 6 2 4 6 1 3 特殊情况的处理方法 1 大面积课程的处理 大面积课程由于排在靠前的位置 安排大面积课程时大部份教室未被 占用 选择面广 而且这类课程涉及面宽 修读人数多 如果安排连天考试 会 造成学生负担过重 也增加了冲突的可能性 所以 我们采用隔天选择考试 时间的方法来安排大面积课程 从而有效地避免了以上问题 例如 对于 时间矩阵 先剔除 m 为偶数的时间段 然后安排大面积考试 T t m n 计算冲突数的方法与 5 2 2 相同 若奇数天中某门大面积课程找不到满 足条件的场次 再考虑在偶数天中安排 例如 t m n 第一天第二天第三天第四天第五天第六天第七天第八天 注 数字表示安排考试时间时的优先顺序 表 3 2 C 中排序较后的课程的处理 当排到后面的课程时 由于资源大部分已被占用并且很少有后排课程C 会受其影响 所以我们可以放宽各约束条件 只要在时间元上有 t m n 合适的教室 我们就为安排考室 放宽对冲突数的限制 i C 6 1 4 流程图 见最后 流程图 见最后 6 2 考场的安排考场的安排 现在我们来探讨怎样为某个找到合适考试时间的课程安排最恰当的 i C 考室 假设我们已经为找到了合适的时间元 选择考场的方法分成以下 i C t m n 几个步骤 6 2 1 讲师的排序 监考安排的研究9 调用每个教授课程的讲师的 ID 以及他们分别所带的学生数 同一个 i C 讲师所带的学生放入同一集合 按照各个讲师所带的学生数目从大到小对 讲师进行排序 得到序列 i JJ 6 2 2 考场的具体安排方法 按照中元素顺序为每个讲师所带的学生安排考场 考虑到考场管理和J 试卷相关信息的答疑和修改 原则上我们需要把同一讲师的学生安排在相 邻的考场 这就要求我们定义相邻考场的概念 为此 我们引入邻接矩阵 我们把一幢教学楼的所有教室都进行如下的编号 ij Aa 同一幢楼每层编号方向应该一致 即同一垂 11121 21222 12 q q pppq ddd ddd D i j ddd 直面上的各教室 j 应该一致 ij d 我们认为不同楼层的教室不相邻 并定义同一楼层的两个教室和 1 ij d 的相邻度为 这样就得到了一个邻接矩阵 它可以 2 ij d 12 12 ijij ddjj A 表征所有考室的相邻关系 当时 我们称和相临 例如 12 2 ijij dd 1 ij d 2 ij d 有一幢的教学楼即只有两层楼 每层楼两间教室 则它的编号图2 2pq 为 2122 1112 它的邻接矩阵为 11 122122 1101infinf 1210infinf 21infinf01 22infinf10 所有教学楼的邻接矩阵可拼成一个大矩阵 同一校区不同教学楼间 A 的教室距离视情况而定 不同校区教学楼间的教室距离可认为是无穷大 inf 若要将任意一个导师所带学生的集合安排到相邻的考场 首先对时 i J 监考安排的研究10 间元当前可用的考场生成其对应的邻接矩阵 将每个考场 t m n i A m n 和与它相邻的考场划到一个相邻集里面 与一一对应 i kh d kh Ei kh Ei kh d 表示第 i 个导师 为了给学生集合找到合适的考室 我们只需要按照 i J k h 从小到大的顺序 逐个搜索中是否有合适的考室 kh Ei 具体搜索方法如下 设已经安排到了第 i 个讲师 设中共有学生名 对于一个已经确 i J i n 定的相邻集 若中所有考室的总容量 即考试时所能容纳的考 kh Ei kh Ei 生数 小于 则搜寻下一个 若大于 首先在中寻找是否 i n kh Ei i n kh Ei 有一个容量大于的考室 若存在 则可将中的学生全部放入此考室中 i n i J 当满足条件的考室不止一个时则选择容量最小的一个来安排中的学生 i J 减少教室资源的浪费 若不存在这样的考室 则将中的学生从 2 开始 i J 平均分为 k 份 可能出现每份不是整数的情况 则将多余的部分 数目小 于 k 平均分配到前几份 然后在中搜索容量大于的教室 如果 kh Ei i n k 找到这样的教室 d 设它的容量为 r 则将中的 r 个学生安排到 d 中 因 i J 为中剩余考室的总容量大于 而考室的容量规格只有有限种 所以 kh Ei i n 这个搜索一定有限步终止 对剩余的个学生按照相同的办法递归地进 i nr 行分配 依此类推 总可得到在所有的中的一个安排方案集合 i J kh Ei i M 对于中的元素 为了区分它们的优劣 我们引入了离差和相对离差 i M 的概念 设为中某方案中所占考室能够容纳的总容量 kh RLi i M kh mi i J 则 离差 khi LCRLin 相对离差 kh LC RC RLi 从中选出离差最小的方案 如果有多个离差相等 则考察这些方案 i M 监考安排的研究11 的相对离差 如果筛选出的方案仍不唯一 则选择下标较小的一个方案 如果任意一个讲师的考室安排失败 则撤销该门课程的已做的所有安 排 该门课程不能安排在这个时间段 考虑下一个 t m n 6 2 3 考场安排的一个优化 如果每个讲师都自顾自的安排 必然会导致相当数目的空闲位置 从 而降低考室资源的利用率 为此我们建议在某个讲师安排自己学生的考室 时 首先