算法设计——自动排考算法

自动排考算法设计:

需要为考试科目分配考场以及监考教师

当前为初版,因为需求还不足够明确,也缺乏真实数据判断资源紧缺情况,待需求和数据明确后,完善算法并补上部分代码。

排考要求:

  1. 考试周期时间限制在一个时间段:1周或两周,周末不排考
    当考试周为两周时:第一周考-专业自排课程; 第二周考-教务处排考课程
    只能排第二周的时间。第一周留给学院自排。
  2. 同一班不能在同一时间安排两次考试
  3. 设置为同时考试的课程,必须安排在同一时间考试
  4. 同一个教室在同一时间只安排一门课程,优先安排多个同课程或同时考试的考试课程在同考场考试
  5. 同一门课程尽量安排在同一栋教学楼考试
  6. 各个班级的考试课程尽可能安排的均匀
  7. 各班级的最后一门课程尽可能的安排在最后1到2天,使每个班的考试周期平等
  8. 考试类型分为笔考和机考,为机考的科目要安排在机考教室
  9. 考试课程为同个课程时,即使没有设置同步考试,也按同步考试来排考
  10. 优先把和考试人数最接近的考场分配,考场只接受容纳人数38以上的可使用教室,机考除外。
  11. 只排公共课,和课时大于32的专业课

早期算法设计:

我的思路是:
首先应该考虑资源的紧张程度,首先考场资源一般是固定的,那么为了保证如同步考试要同时间考试、班级的分布均匀等排考要求,降低排考难度,可以增加考试场次从而变相的扩充资源,不过最终效果需要不断的测试调整,来获取一个比较合适的资源安排方案。
所以假定考场资源是充沛的,就可以优先考虑排考的均匀性了。
首先是取几个对象的数据:考试课程、考场、考试场次。

  • 1.考试场次:根据教务员设置的考试周数、考场数和本学期需要排考的考试课程数目,
    计算出每天的考试场次。

  • 2.考场:根据楼栋,容纳量降序排序取出所有的可用考场。

  • 3.考试课程:先依据同步考试字段分组,每个组保证原子性,按课程类型排序,然后根据班级均匀分布,即批次性,首先每个组一个班级至多出现一次,那么就保证每隔一个批次一个班级出现一次,对于批次内的考试课程,首先按每组的最大考试课程的考试人数降序排序,组内按考试人数降序排序。

  • 4.取出已排考的考试,用一个二维数组存储资源排考情况,横纵轴分布表示:[场次,考场],将已排考的考试放入资源数组。

  • 5.当考试周为两周,将考试场次从后一周截取。

  • 6.最外层循环条件:考试课程数组大小大于0,保证所有课程排考,记录失败次数,超过设定值则认为资源不足,排考失败,避免死循环。

  • 6.1循环遍历场次和考场,为考试课程分配合适的考场资源。

  • 6.1.1分配考场时,首先要分别记录同步考试是否排考完毕,当前考场是否分配出去,当前考场分配失败次数,并存储可能因为同步考试无法在该场次全部分配而需要回滚的数据数组,因为该班级当前场次已经排考所以回滚的数据,以及当前场次已排考的班级数组。

  • 6.1.2循环遍历考场时,首先判断上个考场是否分配出去,未分配出去则游标左移,继续分配上个考场,直到达到考场分配失败次数。

  • 6.1.3然后判断当前考场已分配?以及考试课程数组为空?若都不满足则分配考场。

  • 6.1.4然后依次从课程表取同步考试的所有考试人数(需要课程数组中同步考试的课程是连续的),判断当前考场容纳数是否能满足前者,若不能则拆班直到考场能坐下,直到只剩一个班也无法拆够,则搁置该考场。

  • 6.1.5考场合格,还需要查找当前场次已排考的班级数组,判断当前班级是不是在该场次已排考?若未排考则新建考试,将此满足要求的考场分给此考试课程,并写入之前的缓存数组,移除该课程,并存入因为同步考试无法在该场次全部分配而需要回滚的数据数组,更新资源数组,新建完所有考试后判断此同步考试是否已排考完毕,若排完则更新同步考试是否排考完毕。

  • 6.1.6如果当前考场未分配出,就记录当前考场分配失败次数

  • 6.2如果当前同步考试是否排考完毕为非,则回滚因为同步考试无法在该场次全部分配而需要回滚的数据数组的数据。回滚因为该班级当前场次已经排考所以回滚的数据。

  • 7.上传所有考试数据到数据库。

监考老师排考要求:

  1. 请假阶段不能安排监考
  2. 尽量公平的安排监考
  3. 根据考场的监考人数安排监考老师
  4. 主考教师在其主考时间不安排监考

算法设计:

  1. 从数据库取出监考教师,按照监考次数升序,部门编号升序排序,以便未排考的先安排。
  2. 从数据库取出系部自排后每个教师的监考次数,以便控制每个教师监考次数平等。
  3. 遍历考试数组,取每个考试分配的考场,为考场分配足够的教师。
  4. 为考场分配教师时,设定一个游标指向当前下标,首先要考虑此教师此时是否需要担任同场次进行的其他考试的主考教师,若需要则不能分配其作监考教师。
  5. 为考场分配教师时,其次要考虑此时间段该教师是否请假,若请假则不分配该教师。
  6. 不分配的教师从教师数组拿出放入尾部,避免重复拿出,上述都未过滤的教师分配其作监考教师,游标右移,考场需要教师数减一。

补充需求:

客户的教学数据非常杂乱,比如英语类课程,开设课程后,每学期开设教学班可以随意和行政班关联,导致同一课程开设教学班时出现了多种普遍存在的类型:

  • 类型1:教学班A=行政班a,教学班B=行政班b
  • 类型2:教学班A=行政班a+行政班b
  • 类型3:教学班A=行政班a,教学班B=行政班b,教学班C = 行政班a+行政班b
  • 类型4:教学班A=行政班a+行政班b+……,教学班B=行政班a+行政班b+……,……
  • 类型5:教学班A=行政班a+行政班b+行政班c,教学班B=行政班c+行政班d+行政班e,教学班C = 行政班e+行政班f+行政班g,……

类型1是正常按行政班上课

类型2则是正常合班上课

类型3是合班上理论,分班上实验

类型4则是行政班打乱任意选课

类型5则是因为教学班人数上限所以客户分班时将中间的班级如c班拆成两部分放入A和B班。

比较困难的是客户并没有计算机思维,所以这些抽象出的类型并没有加入到数据库设计中,人为的发散性使用方式导致最终开班出现多类型情况。

所以根据这种情况在排考时有些类型不能考虑行政班时间冲突的问题。

类似的情况还有:明明有考核方式属性,却不维护。明明有课程分类,也不维护。所以拿到的数据只是最基础的课程,教学班等信息。如何判断参与排考的考试科目需要大量的数据检索,初步认定参与自动排考的课程为理论学时大于32,非英语类科目平均每班选课人数大于10,不是体育类课程,任课教师不是校外教师,且不在过滤集合中的所有科目。

新增需求:

  1. 政治类和英语类分别在第一天上午和下午考完,测试发现教室资源并不够用,所以将半天限制扩大为一天。
  2. 行政班拆在不同考场考试时,主考教师不安排监考

初版编程实现的算法设计:

一.数据准备

  1. 从数据库分别读入:考试科目,考场(>=30,按容纳量降序排序),考试场次,教学班关联行政班,已分配考试数据。
  2. 抽离出英语集合,政治集合,其他集合。取英语大类时《英语》最后取出分配小教室。
  3. 分别整理三个集合放入存储结构[有序哈希Map<String,List>-key是同步考试代码]中,该结构把同步考试的课程班隔离。

二.循环排考

  1. 开始排考政治集合,从场次0开始,即周一上午,需要检查行政班是否该场次已排考ifCheckClass。
  2. 遍历Map中的所有同步课程班集合Map<String,List>,直到所有科目排考完毕,声明场次游标等于开始场次。
  3. 遍历List之前,若同步考试代码被禁止在当前场次排考,则循环后移场次游标,记录圈循环次数。
  4. 若未被禁止在该场次排考,则预估一下本时间段剩余可用考场是否可以放下当前List所有学生。
  5. 若不够坐下就循环后移场次游标,记录圈循环次数。
  6. 若够坐,则开始遍历当前同步课程班集合List,直到所有同步考试科目排考完毕,若循环次数超过上限都无法排下当前集合,则抛出异常-排考失败。
  7. 循环遍历考场,若考场此场次未被占用,判断CourseClass考试人数是否可全部坐下,若可以即顺利排考,若不可以则进行拆班,依次取出一个行政班,直到剩余人数可以放入考场。记录取出的行政班为CourseClass剩余需排考,在后续的考场中放置。
  8. 若循环结束也未找到合适考场就直接跳出遍历,若找到了合适考场,则根据ifCheckClass为真则要先检查CourseClass行政班是否已在该场次排考,若已排考则禁止所有同步考试代码集合在此场次排考。
  9. 判断是否可以合班,若下个CourseClass同课程且能一起放下,就一起放入当前考场。
  10. 生成考试数据,记录当前场次考场已被占用,若List

三.循环结束

  1. 开始排考英语集合,从场次1开始,即周一下午,不需要检查行政班是否该场次已排考ifCheckClass。
  2. 循环排考。
  3. 开始排考其它集合,从场次2开始,即周二下午,需要检查行政班是否该场次已排考ifCheckClass。
  4. 循环排考。
  5. 将排好的考试数据写入数据库中。

四.安排教师监考

  1. 获取已排好的所有考试数据集合,获取所有监考教师,游标指向教师集合下标0。
  2. 遍历考试集合。
  3. 判断是否已安排监考教师,若未安排则获取考场还需监考教师数目,循环直到还需监考教师数目为0。
  4. 取出游标所指教师,查询此教师是否在此时间段是某门考试科目的主考教师:
  • 若是则将其后移到教师集合中本轮未处理中间位置;
  • 若不是主考教师,则继续查询此教师是否在此时间段已担任监考教师:
  • 若已担任则将其后移到教师集合中本轮未处理中间位置;
  • 若未担任则判断其请假信息,判断是否有空监考:
  • 若没空监考则将其后移到教师集合中本轮未处理中间位置;
  • 若有空则安排此教师监考,生成监考数据,还需监考教师数目减一,游标右移。
  1. 考试集合循环结束,将排好的监考安排数据写入数据库,更新本学期考试参数为已自动排考,排考结束。