自动排课算法分析

自动排课算法分析 1 绪论 1 1 课题背景与研究意义 1 2 课题的应用领域 1 3 课题的现状 1 4 解决 NP 问题的几种算法及其比较 2 目前流行的几种排课算法的介绍 2 1 自动排课算法 2 2 基于优先级的排课算法 3 基于时间片优先级排课算法描述与分析 3 1 排课中的基本原则 3 2 排课的基本要求 3 3 基于时间片优先级排课算法描述 3 4 算法分析 参考资料 1 绪论 1 课题背景与研究意义 排课问题早在 70 年代就证明是一个 NP 完全问题 即算法的计算时间是呈指数增长的 这 一论断确立了排课问题的理论深度 对于 NP 问题完全问题目前在数学上是没有一个通用 的算法能够很好地解决 然而很多 NP 完全问题目具有很重要的实际意义 例如 大家熟 悉地路由算法就是很典型的一个 NP 完全问题 路由要在从多的节点中找出最短路径完成 信息的传递 既然都是 NP 完全问题 那么很多路由算法就可以运用到解决排课问题上 如 Dijkstra 算法 节点子树剪枝构造网络最短路径法等等 目前大家对 NP 完全问题研究的主要思想是如何降低其计算复杂度 即利用一个近似算法 来代替 力争使得解决问题的时间从指数增长化简到多项式增长 结合到课表问题就是建 立一个合适的现实简约模型 利用该简约模型能够大大降低算法的复杂度 便于程序实现 这是解决排课问题一个很多的思路 在高等院校中 培养学生的主要途径是教学 在教学活动中 有一系列管理工作 其中 教学计划的实施是一个重要的教学环节 每学期管理人员都要整理教学计划 根据教学计 划下达教学任务书 然后根据教学任务书编排课程表 在这些教学调度工作中 既有大量 繁琐的数据整理工作 更有严谨思维的脑力劳动 还要填写大量的表格 因此工作非常繁 重 加之 随着教学改革的进行及 211 工程的实施 新的教育体制对课表的编排提出了更高 的要求 手工排课时 信息的上通下达是极其麻烦的 而采用计算机排课 教学中的信息 可以一目了然 对于优化学生的学习进程 评估每位教师对教学的贡献 领导合理决策等 都具有重要的意义 必将会大大推进教学的良性循环 2 课题的应用领域 本课题的研究对开发高校排课系统有指导作用 排课问题的核心为多维资源的冲突与抢占 对其研究对类似的问题 特别是与时间表有关 的问题 如考试排考场问题 电影院排座问题 航空航线问题 也是个参考 3 课题的现状 年代末 国外就有人开始研究课表编排问题 1962 年 Gotlieb 曾提出了一个课表问题的数 学模型 并利用匈牙利算法解决了三维线性运输问题 次后 人们对课表问题的算法 解 的存在性等问题做了很多深入探讨 但是大多数文献所用的数学模型都是 Gotlieb 的数学模 型的简化或补充 而至今还没有一个可行的算法来解决课表问题 近 40 年来 人们对课表问题的计算机解法做了许多尝试 其中 课表编排的整数规划模型 将问题归结为求一组 0 1 变量的解 但是其计算量非常大 解决 0 1 线性优化问题的分支 一定界技术却只适用也规模较小的课表编排 Mihoc 和 Balas 1965 将课表公式化为一个 优化问题 Krawczk 则提出一种线性编程的方法 Junginger 将课表问题简化为三维运输问 题 而 Tripathy 则把课表问题视作整数线性编程问题并提出了大学课表的数学模型 此外 有些文献试图从图论的角度来求解排课表的问题 但是图的染色问题也是 NP 完全 问题 只有在极为简单的情况下才可以将课表编排转化为二部图匹配问题 这样的数学模 型与实际相差太远 所以对于大多数学校的课表编排问题来说没有实用价值 进入九十年代以后 国外对课表问题的研究仍然十分活跃 比较有代表的有印度的 Vastapur 大学管理学院的 ArabindaTripathy 加拿大 Montreal 大学的 JeanAubin 和 JacquesFerland 等 目前 解决课表方法的问题有 模拟手工排课法 图论方法 拉格朗日 法 二次分配型法等多种方法 由于课表约束复杂 用数学方法进行描述时往往导致问题 规模剧烈增大 这已经成为应用数学编程解决课表问题的巨大障碍 国外的研究表明 解 决大规模课表编排问题单纯靠数学方法是行不通的 而利用运筹学中分层规划的思想将问 题分解 将是一个有希望得到成功的办法 在国内 对课表问题的研究开始于 80 年代初期 具有代表性的有 南京工学院的 UTSS AUniversityTimetableSchedulingSystem 系统 清华大学的 TISER TimetableSchedulER 系统 大连理工大学的智能教学组织管理与课程调度等 这 些系统大多数都是模拟手工排课过程 以 班 为单位 运用启发式函数来进行编排的 但是这些系统课表编排系统往往比较依赖于各个学校的教学体制 不宜进行大量推广 从实际使用的情况来看 国内外研制开发的这些软件系统在实用性上仍不尽如人意 一方 面原因是作为一个很复杂的系统 排课要想面面俱到是一件很困难的事 另一方面每个学 校由于其各自的特殊性 自动排课软件很难普遍实用 特别是在调度的过程中一个很小的 变动 要引起全部课程的大调整 这意味着全校课程大变动 在实际的应用中这是很难实 现的事 4 解决 NP 问题的几种算法及其比较 解决 NP 完全问题只能依靠近似算法 所以下面介绍几种常用算法的设计思想 包括动态 规划 贪心算法 回溯法等 动态规划法是将求解的问题一层一层地分解成一级一级 规模逐步缩小的子问题 直到可 以直接求出其解的子问题为止 分解成的所有子问题按层次关系构成一颗子问题树 树根 是原问题 原问题的解依赖于子问题树中所有子问题的解 动态规划算法通常用于求一个 问题在某种意义下的最优解 设计一个动态规划算法 通常可按以下几个步骤进行 1 分析最优解的性质 并刻划其结构特征 2 递归的定义最优解 3 以自底向上的方式计算出最优解 4 根据计算最优解时得到的信息 构造一个最优解 步骤 1 3 是动态规划算法的基本步骤 在只需要求出最优解的情形 步骤 4 可以省去 若 需要求出问题的一个最优解 则必须执行步骤 4 此时 在步骤 3 中计算最优解时 通常 需记录更多的信息 以便在步骤 4 中 根据所记录的信息 快速地构造出一个最优解 二 贪心算法 当一个问题具有最优子结构性质时 我们会想到用动态规划法去解它 但有时会有更简单 更有效的算法 即贪心算法 顾名思义 贪心算法总是做出在当前看来最好的选择 也就 是说贪心算法并不是整体最优上加以考虑 他所作出的选择只是在某种意义上的局部最优 的选择 虽然贪心算法不是对所有问题都能得到整体最优解 但对范围相当广的许多问题 它能产生整体最优解 如图的算法中单源最短路径问题 最小支撑树问题等 在一些情况 下 即使贪心算法不能得到整体最优解 但其最终结果却是最优解的很好的近似解 在贪心算法中较为有名的算法是 Dijkstra 算法 它作为路由算法用来寻求两个节点间的最 短路径 Dijkstra 算法的思想是 假若 G 有 n 个顶点 于是我们总共需要求出 n 1 条最短路 径 求解的方法是 初试 写出 V0 始顶点 到各顶点 终顶点 的路径长度 或有路径 则 令路径的长度为边上的权值 或无路经 则令为 再按长度的递增顺序生成每条最短路 径 事实上生成最短路径的过程就是不断地在始顶点 V 何终顶点 W 间加入中间点的过程 因为在每生成了一条最短路径后 就有一个该路径的终顶点 U 那么那些还未生成最短路 径的路径就会由于经过 U 而比原来的路径短 于是就让它经过 U 三 回溯法 回溯法有 通用的解题法 之称 用它可以求出问题的所有解或任一解 概括地说 回溯 法是一个既带有系统性又带有跳跃性的搜索法 它在包含问题所有解的一颗状态空间树上 按照深度优先的策略 从根出发进行搜索 搜索每到达状态空间树的一个节点 总是先判 断以该节点为根的子树是否肯定不包含问题的解 如果肯定不包含 则跳过对该子树的系 统搜索 一层一层地向它的祖先节点继续搜索 直到遇到一个还有未被搜索过的儿子的节 点 才转向该节点的一个未曾搜索过的儿子节点继续搜索 否则 进入子树 继续按深度 优先的策略进行搜索 回溯法在用来求问题的所有解时 要回溯到根 且根的所有儿子都 已被搜索过才结束 而在用来求问题的任一解时 只要搜索到问题的一个解就可结束 2 目前流行的几种排课算法的介绍 2 1 自动排课算法 1 问题的描述 我们讨论的自动排课问题的简化描述如下 设要安排的课程为 C1 C2 Cn 课程总数为 n 而各门课程每周安排次数 每次为连续的 2 学 时 为 N1 N2 Nn 每周教学日共 5 天 即星期一 星期五 每个教学日最多安排 4 次课程教 学 即 1 2 节 3 4 节 5 6 节和 7 8 节 以下分别称第 1 2 3 4 时间段 在这种假设 下 显然每周的教学总时间段数为 5 4 20 并存在以下约束关系 n 20 1 N 6n i 1 Ni 20 2 自动排课问题是 设计适当的数据结构和算法 以确定 C1 C2 Cn 中每个课程的教学应占据 的时间段 并且保证任何一个时间段仅由一门课程占据 2 主要数据结构 对于每一门课程 分配 2 个字节的 时间段分配字 无符号整数 T1 T2 Tn 其中任何一 个时间段分配字 假设为 Ti 都具有如下格式 Ti 的数据类型 C 语言格式定义为 unsignedint Ti 的最高位是该课程目前是否是有效的标志 0 表示有效 1 表示无效 如停课等 其它各位称为课程分配位 每个课程分配位占连续的 3 个位 bit 表示某教学日 星期一 星期五 安排该课程的时间段的值 0 表示当日未安排 1 4 表示 所安排的相应的时间段 超过 4 的值无效 在这种设计下 有效的时间段分配字的值应小于 32768 十六进制 8000 而大于等于 32768 的 时间段分配字对应于那些当前无效的课程 既使课程分配位已设置好也如此 因此很容易实 现停课 开课处理 3 排课算法 在上述假设下 自动排课算法的目标就是确定 C1 C2 Cn 所对应的 T1 T2 Tn 从安排的可能性上看 共有 20 20 N 种排法 N 的含义见 2 式 如果有 4 门课 每门课一周上 2 次 则 N 8 这 8 次课可能的安排方法就会有 20 20 8 5079110400 即 50 多亿种 如果毫无 原则地在其中选择一种方案 将会耗费巨大量的时间 所以排课的前提是必须有一个确定的排 课原则 我们采用轮转分配法作为排课原则 从星期一第 1 时间段开始按 C1 C2 Cn 中所列 顺序安排完各门课程之后 每门课安排 1 次 再按该顺序继续向后面的时间段进行安排 直到 所有课程的开课次数符合 N1 N2 Nn 中给定的值为止 在算法描述中将用 C 1 C 2 C n 表示 C1 C2 Cn 对 N1 N2 Nn 和 T1 T2 Tn 也采用同样的表示法 算法 1 排课算法 输入 C1 C2 Cn N1 N2 Nn 输出 T1 T2 Tn 初始化 星期值 week 1 时间段值 segment 1 T 1 T 2 T n 中各时间段分配字清零 新一轮扫描课程 置继续处理标志 flag 0 对课程索引值 c index 1 2 n 进行以下操作 如果 N c index 0 则做以下操作 把 segment 的值写入 T c index 的第 week 1 33 week33 1 位中 N c index 的值 减 1 如果 N c index 0 则置 flag 1 如果 week 5 并且 segment 4 则 置 flag 1 并转 否则 如果 segment 4 则 置 segment 1 且 week 增 1 否则 segment 增 1 检测是否已全部安排完毕 如果 flag 1 则 转 否则 转 检测是否成功 如果 flag 1 则 开课次数过多 否则 课程安排成功 算法结束 显然 本算法的时间复杂度为 O N N 为每周总开课次数 见 2 式 而存储时间段分配字所用 空间为 2n 个字节 n 为课程门数 4 冲突检测算法 有时在自动排课完毕后 需要人工调整某些课程的安排时间 如把第 i 门课程在人工干预下改 成星期数为 week 时间段为 segment 的位置 则根据上述数据结构需做如下运算 T i T i 表示该课程一周上两 次 分别为周一的 12 节和周四的 12 节 L 同时 为了达到较好的上课效果 也要对这些时间模 式进行分级 如下所示 时间模式分级举例 周学时优先级周一周二周三周四周五 411141 422243 其中 将周一至周五用数字 1 5 表示 上课节次 12 节 34 节 56 节 78 节 晚 12 节 晚 34 节分别用数字 1 6 表示 例如数字 42 表示周四的 34 节 这个时间单元 这样 对于每种周学时数 可以将所有合理的时间组合形式存入模式库中 以 便进行时间处理时可以用时间模式库中的各种模式进行匹配 2 时间数组 为了表示班级 教师 教室的可排课时间 分别为他们建立一维数组 L 例如 某位教师的初 始可排课时间数组为 123456 123456 123456 123456123456 其中共有五组数据 分别 表示一周中的五天 而一组数据共有 6 个字符 1 2 3 4 5 6 分别表示一天中的六个 时间单元 当为某位教师分配时间后 相应的那位字符就置为 0L 例如 某位教师的可排课时 间数组为 020456 103456 003456 120456 023456 则表示这位教师在周一的 12 节和 56 节 周二的 34 节 周三的 12 节和 34 节 周四的 56 节 周五的 12 节已经安排了课程 如果要 再安排课程的话 就应该安排在非 0 的时间单元 L 对于班级和教室也可以进行同样的处理 分别标出可排课时间 2 每一子类的排课处理 在对每个子类的排课处理中 我们结合了分治法 贪婪法 回溯法三者的思想 L 首先 根据 分治法的思想把整个排课过程分成时间分配和教室分配两个阶段 然后 依据贪婪法的算法 思想 在时间分配时 总是在尚未分配的时间单元中选择上课效果最好的 单元 而在时间分配发生死锁时 会向上回溯搜索到发生冲突的最近一个记录 然后对它进行 重排以解决冲突 具体处理过程如下 1 设定优先级 对子类中的课程计算优先级 L 设优先级函数为 D g J g C1 T g C2 P g C3 1 其中 J g 表示课程级别 选修课的课程级别设置为 1 必修课的课程级别设置为 2 T g 表示该 课程的周学时数 P g 表示该课程的参与人数 C1 C2 C3 是可以调整的参数 由式 1 可以看出课程级别越高 周学时越多 参加人数越多的课 程 其 D g 值越大 其优先级也越高 反之 D g 值越小 其优先级越低 这样 就可以根据计算 的优先级的高低对课程进行排序 优先级高的优先调度 2 查询可用时间单元 第 1 步 初始化某门课程的最大可安排时间数组 为 123456 123456 123456 123456 123456 第 2 步 找出参加该课程学习的所有班级 第 3 步 查询每个班级的时间数组 得到 班级的已排课时间 并将其与课程的最大时间数组相 与 从而得到该课程不能安排的时间 单元 第 4 步 依次处理教师时间数组和相关教室时间数组 这样 该课程最终的可安排时间 数组就是班级 教师 教室可排课时 间的交集 3 查找适当的时间模式 找到可排课时间后 就应根据课程的周学时数在时间模式库中匹配适当的时间模式 完成以 上工作后 就确定了课程的上课时间和地点 如果在处理中发生死锁 则可根据回溯法的思想 向上回溯搜索到发生冲突的最近一个记录 然后对它进行重排以解决死锁 如果仍不能解决死 锁问题 则可以将该课程信息输出到冲突列表中 3 人工干预的处理 计算机自动排课也需要进行人工干预 以便可以使得各个高校能够根据自己的具体要求对排 课算法中的一些参数进行设置和调整 并对计算机排出的课表进行调整 L 本算法所设计的人 工干预过程有 等价类划分中参数的设置 教室类型的设置 时间模式库的设置 优先级函数中参数的设置 用户可以根据自己的具体要求对这些参数和库进行设置 另外 对于计算机排出的课程表 用 户也可以通过人机交互进行适当调整 从而得到用户满意的课程表 4 性能分析 此算法对班级及教室划分等价类 对学校资源进行了合理的利用 但对一些特殊要求还是 无法具体体现出来 3 基于时间片优先级排课算法描述与分析 排课问题实质上是时间 教师 班级 教室 课程这五维关系的冲突问题 要合理的解决 这个问题首先要了解排课中的一些基本原则以及排课的一些基本要求 3 1 排课中的基本原则 在课程的编排中应遵循一定的规则 只有按照基本规则来进行课程的编排才能够减少冲突的 发生 这些基本规则主要有以下几条 1 同一班级的学生在同一时间 某些特定的选修课时间除外 不能安排两门课程 2 同一教师在同一时间不能安排两门课程 3 同一教室在同一时间不能安排两门课程 4 同一时间安排的课程总数不能大于所能提供的教室总数 5 某一课程参加学习的总人数不应大于所安排教室的座位数 6 所提供教室的属性与课程所需教室的属性一致 在时间 教师 班级 教室 课程这五维关系中 时间 教师 班级三者之间存在着紧密关 系 相对而言 教室与它们关系就不那么密切 3 2 排课的基本要求 课程的安排不是任意的 为了达到最好的教学效果应遵循一定的要求 这些要求主要有 1 要尽量为所排课程安排上该类课效果最好的时间 2 课程在一周上多次时 要有一定的间隔性 3 公共课等涉及面广 学时多的课程应优先处理 4 对同一教师 同一上课对象应尽量选择相对固定的几个教室 5 对同一个班级的课程应选择相对固定的教室 6 连着的课的教室选择不应相隔太远 7 同一天有几门课时尽量把课分散 8 优先满足一些特殊要求 比如有些教室喜欢上上午的课 可以优先满足 3 3 基于时间片优先级排课算法描述 在描述算法之前我们把一些概念先讲清楚 在这里我们把从行政角度分的班叫自然班 把 在同一个教室上课的班叫做排课班 在大学里有些公共课是几个排课班通过多媒体来一起 上的 我们把这个排课班的总和叫做公共班 班级 教室 教师 课程都维护着自己的一 张课表 对课表的每个表元 如星期一的第一节课 在这里称做时间片 基于时间片优先级排课算法以排课班为单位 围绕着各对像 自然班 教室 教室 的时间 表选择合适的时间片 1 算法流程图 2 算法的伪代码描述 输入 教师 teacher1 teacher2 teachern 教室 room1 room2 roomn 班级 class1 class2 classn 课程 course1 course2 coursen 各教师 教室 班级 课程时间片的优先级 排课班 schudel class1 schudel class2 schudel classn 输出 已经排好课表的教师 教室 班级 Procedureschudeling teacher room class course schudel class public class 初始化一张空的时间表 对该时间表的每个时间片的优 先级初始化为高级 InitTime table 对排课班进行处理 Foreveryschudel classdo If Check Have despose schudel class 假如该排课班尚未排课 Begin Time table Time table Time table Time table Course get course schudel class 假设只有两节连堂及三节连堂那种课 IntiCount2 0 那门课两节连堂的次数 IntiCount3 0 那门课三节连堂的次数 得到课程每周的课时数 Intcourse count get couse count Course 得到每周的连课情况 Parse couse count course count 根据 iCount2 iCount3 以及 Time table 为该排课班选择 N 个 N iCount2 iCount3 适当的时间片 保存在 CPoint 变量中 CPointpo LList cp Intpriority 7 0 得到每天的优先级的总和 Loop I 0untilI 6do Loop J 0untilJ 6do Begin Priority I Priority I Time table time piece I j EndBegin 得到优先级总和最大的那天 我们认为那一时间最闲 适宜安排课程 intnumber get number priority 7 BOOLfail WhileiCount2 0do Begin fail Get Time Pieces 2 if fail thendo begin iCount2 cp append list po endbegin else break EndBegin WhileiCount3 0do Begin fail Get Time Pieces 3 if fail thendo begin ICount3 Cp append list po Endbegin Else Break EndBegin 根据 cp 的数据及 schudel class 的数据对 schudel class 中的自然班 所得到的教室 老师的课表进行回写 if fail do WriteBack schudel class cp Elsethen RollBack schudel class cp 把先前选好的教室 老师给 擦除 掉 EndBegin EndSchudeling 算法里面有到的