数学建模排课系统

监制监制 数学建模协会数学建模协会 计算机上机课安排计算机上机课安排 摘要摘要 本模型用于较为方便的排课 其步骤主要分三个部分 第一部分主要解决那些学生空课特别少的特殊班级 由于此种班级可供选 择的空课时间不多 故而最为优先的进行考虑 这一部主要靠人工完成 第二部分也就是本模型的核心部分 用于初步解决余下班级的排课问题 首先将老师和学生的课表转化成相应的 0 1 分布的形式 然后利用所确定的优 先级别 对课表中学生空课状态 记为 X1 老师在原任课天内空课情况 记 为 X2 根据不同时段的空课情况赋予不同的值 以及实验室每个时段的上机占 有情况 X3 即可通过参数的大小反应各个空课处优先被安排的程度 然后将 老师的课表矩阵与其所教班级的课表矩阵相加 使得学生上午优先 教师指导 自己班学生最大化及实验室占有情况同时考虑 找出 Y Y X1 X2 X3 e 最大值处的坐标 即为该班级上机实践应该安排在课表中的位置 而将 0 1 分布的矩阵转化为带有优先级别的矩阵通过 Matlab 很容易的实现 两个矩阵 的相加也可以通过 Matlab 实现 这一模块将在智能化排课的过程中用到两次 第一次 把老师任课天内可 以指导自己所教班级最大限度的排满 然后通过 C 程序选出需要加天的老师 及具体哪天 使得被选择的那天为所有可选天中 最大化指导学生的那天 关 键代码将在附录二中给出 而后再对于还没有排课的班级进行下一轮的排课 这时只需可虑老师所附加来校的那一天 这样就保证老师尽可能多的指导自己 所教班级 教师来学校的意义最大化 以上的两轮排序 较为简便并且智能的实现了课表的基本确定 第三部分主要依靠人工完成 此部分主要考虑因第二部分机械排序以后还 存在没有排到课的班级 这些班级是那些在老师加天后还无法在这几天中被自 己老师指导到的班级 对于这样的班级 只能交给管理员指导 由于这只是极 少的一部分 不会给人工排课人员带来很大的工作量 我们优先级别的确定原则 1 通过首次全部用人工进行课表的实际抄做安排所出现的现象 发现学生 的空课时间主要集中在下午 见附录一 表 1 若不考虑上午优先的话 则所 有班级很难安排下去并且会出现下午一定面积的溢出 2 教师优先 如果老师可以带自己所教的班级 那么这种情况也是应该优 先考虑的 这来源于问题中提出的硬性要求和实际的教学效果的统计 3 此模型须要人工的地方 虽有两处 但所做工作量都不大 通过此模型 建立的课表与全部人工安排的课表在相互检验的时候发现相差不大 故而此模 型具有一定的可行性 关键词关键词 智能化排课 优先级别 矩阵转化 人工调整 对照检验 创新意识 团队精神 重在参与 公平竞争 2 目录目录 1 1 问题重述问题重述 4 2 2 问题假设问题假设 4 3 3 分析及流程图分析及流程图 4 3 1 问题的分析 5 3 2有关构建假设的分析 6 3 3 按优先级排序流程图 6 4 4 模型的建立及求解模型的建立及求解 8 4 1符号设定 8 4 2优先级别的确定 8 4 3模型的建立及求解 8 4 3 1 模型建立的准备 8 4 3 2模型的组成及构建 10 4 3 3 实际情况的模型求解 14 5 5 模型的检验模型的检验 15 6 6 模型的评价模型的评价 16 6 1 模型的优缺点 16 6 2 模型的不足及可以改进之处 16 创新意识 团队精神 重在参与 公平竞争 3 7 7 参考文献 无 参考文献 无 16 16 8 8 附录附录 17 17 一 问题重述 排课是教务运作中的一项重要工作 同时排课问题也是一个复杂的组合优 化问题 对此问题的建模和求解 难度都非常大 多数情况下我们只是满足于 求解问题的一个可行解 而对此可行解的进一步优化往往通过手工完成 效率 很低 在此我们给出一个规模相对较少 约束相对较少的较为简单的排课问题 请同学们加以解决 目前我校的计算机上机课大都安排在计算机学院 计算机学院有 5 个机房 用于学生上机 每个机房大约容纳 90 人 安排上机的课程共有 4 门 指导上机 的教师共有 24 人 其中 20 人为课程的授课教师 其他四人为机房的管理人员 依次为陆老师 章老师 张老师和彭老师 其中 陆老师负责 2 个机房 教师和学生的上机时间不能和他们的授课课程时间冲突 为此我们给出了各位 教师和各个班级学生的课程表 见附录二 四名管理人员可全天进行上机指导 但只能在自己负责的机房进行 共有 123 个班级需要上机 本题需要用数学建模方法研究解决排课是教务问题 1 根据你提出的要求 可以是上述要求的某个或多个 也可以是你自己 合理设定的 确定约束条件 给出目标函数 建立数学模型 2 设法求出满足约束条件的一个可行解 详细给出你的求解步骤 3 根据你的目标 设计算法 求解问题的一个最优解或近似最优解 二 问题假设 创新意识 团队精神 重在参与 公平竞争 4 1 假设机房管理员一周内均可全天参与指导 2 假设每个班级一周只安排一次上机且必须安排一次上机 3 假设每个机房可以容纳至少两个班级同时上机 4 假设每个老师在同一时段只指导一个班级 5 假设在同一个机房老师和管理员共同指导自己所教的两个班级 6 假设任课老师一定不指导非自己教学的班级 7 假设周末和晚上不安排上机 8 假设除周末外其他的假期均不考虑 三 分析及流程图 3 13 1 问题的分析问题的分析 排课问题 由于其影响因子较多 并且基于现在的排课制度更多的是在一 个可行解 并非比较优化 的基础上 通过手工进行优化 加大手工上调课带 来的工作量 而且 由于提供可行解时的一些不合理性 使得人工优化时并没 有最大化我们所期望的要求 为了实现优化或者增加可行性 在手工优化的过 程中 甚至要去改动大量前面已经安排好的课程 每个课程的调动和优化时出现了连 锁反应 最终甚至出现死循环 使得人工优化无法继续操作 为了完成排课 也许会出现优化变恶化的小概率现象 并且人毕竟不比机器 当大量需要优化 的问题出现且相互影响的出现在他 她 面前时 总会有一些细节 有可能是 重要细节 被忽略 这就是人工优化的瓶颈 因此 对于排课问题的研究就是要减小可行解和人工优化之间的差异性 让人工优化是驾驭在可行解之上的优化 而且最好是一次性排好 避免出现回 头调课的现象 而对于避免回头调课这样的问题 有如下要求 就是要求系统有前瞻性 把一些特殊时段预先的保留 在最优化其他条 1 件的情况下 对不同班级 不同时段进行分级处理 把一些其他课程更加复杂 的班级进行优先占有 从而实现 预留 和 先占 以上是在排课这一纵项上的大致串行次序 而对于每次排课 即每排一 2 个班 还需要考虑到教师 管理员 实验室等横向维度的并行次序 为此 以上两个较为重要的部分的实现 必须基于一定的 系统优先级别 以下是基于前几次的手工完整模拟以及统计对优先级别的给定做出相关分 析 由于存在课程安排特别紧张的班级 在本研究中 定义为一周空课数小 1 于5的班级 对于这样少数几个班级 因在最前面给予安排 对于他们来说 可以安排到上机就可以了 而若可以遇上自己老师指导那则更好 对于上午排课和教师指导自身班级的优先级的分析 例如 在未加天情 2 况下 老师只有下午7 8节有空 学生上午1 2节 下午7 8节有空 若是 先考虑老师尽可能的能指导到自己的班级 那么就是一切以老师空为主 班级 实验室的情况尽可能去靠向老师这一侧 而通过建模前的样本实排 出现了大 面积的溢出 情况远远超出附录一 表1中的现象 因此 从全盘考虑 我们更 创新意识 团队精神 重在参与 公平竞争 5 希望看到的是每个班每周都可以在周一到周五的白天进行上机 这就要求我们 必须把上机向上午压缩 空下下午使得一些选择余地较小的班级可以完成每周 一次的上机 也就是让那些上午较空的班级做出一定程度上的让步 以此保证 了整体教学上理论与实践的结合 用理论指导实践 实践巩固理论 这也是工 科类课程的教学核心所在 那么上午下午的优先级别就不言而喻了 显然是上午优先 3 以上部分将在以下的2 3中通过流程图具体展现 3 23 2 有关构建假设的分析有关构建假设的分析 1 假设一中实验员可全天指导只是一个很宽泛的假设 目的是便于课程的 安排 而实际中我们可以考虑让每个实验员一星期内至少有一到两个上午的时 间是没有指导任务的 因为上午的课程并没有排满 我们可以通过选择不同的 机房 让不同的管理员都有休息的时间 2 假设二中主要考虑的是上机课时能否满足的问题 因为最多的课时为 32 而如果每周可以上机一次的话 18周内完全可以满足教学要求 我们可以 考虑让上机晚于课堂教学一到两周开始 这样教学效果会更好 3 假设三是可以满足的 经我们分析以后 发现单个班级人数平均在40左 右 而一个机房可容纳大约90人 完全可以满足要求 4 假设五为我们自行分析构建 由于结合实际 虽然看似老师只指导了一 个自己任教的班级 另外一个由管理员负责 但是毕竟是在一个机房 两个班 学生还是可以有机会向自己老师提问 这样其实也是从另外一个方面增大了教 师指导自己班级的数目 这种间接的指导形式还是普遍存在于我们的教学当中 的 并且不失为一个好的安排手法 5 假设六由于考虑到每个老师教学模式 进度 风格不尽相同 而且让其 他老师带非自己教学的班级还不如让管理员来带 更有一些特殊情况 学生会 因为自己感觉自己老师的教学模式不如其他老师 在学习上产生了负面情绪 这我们也有所体会 所以利用假设六 来解决这一问题 6 其余假设显然符合实际要求 再此 不作过多说明 3 33 3 按优先级排序流程图按优先级排序流程图 符号说明 C1 课表中只在下午出现空课或于一周内出现空课数小于五的班级 C2 课表中上午出现空课的班级 C3 课表中既在上午又在下午有空课的班级 总流程总流程 创新意识 团队精神 重在参与 公平竞争 6 人工微调 排课完成 各种课 表的准 备 第一部分人工选 择 第二部分程序化 排课 创新意识 团队精神 重在参与 公平竞争 7 N Y 省略号表示对 C2 C3 执 行与 C1 相同的操作 Y N 对 C1 进行安排 搜索 C1 是否 已安排完 对 C2 进行安排 上午优先教师最大化 C1 C2 C3 均匀已安排完 毕 检查课表 排课完成 手动调 整 开始 创新意识 团队精神 重在参与 公平竞争 8 四 模型的建立及求解四 模型的建立及求解 4 14 1 符号设定符号设定 A 管理员陆老师 B 管理员章老师 C 管理员张老师 D 管理员彭老师 T01 T20 对二十位老师的编号 与原题附件二中所给的顺序一致 MTI 教师课表矩阵 I表示教师编号 MSIJ 学生课表矩阵 其中I J分别表示教师编号和教师所教班级编号 4 24 2 优先级别的确定优先级别的确定 C1 C2 C3 A B C D平级 4 34 3 模型的建立及求解模型的建立及求解 4 3 14 3 1 模型建立的准备模型建立的准备 模块的形成模块的形成 利用数据库语言将每个班的课表和老师的课表分别导出 并转为以0 1分布形式 的矩阵 通过咨询数据库老师 得知这一点可以实现 其中0表示有课 1表 示可以排课 班级矩阵 MSIJ 1 星期一 星期二 星期三 星期四 星期五 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 1 1 0 0 1 1 0 0 注 每行的第一个数为标记数 0表示未排 1表示已排 总数为123 21的矩阵 教师矩阵 MTI 此时I 01 2 流程要求流程要求 1 1 当每有一个班排了课 系统或是人工应 在学生的矩阵相应位置赋值为P 表示此天此时上机 并在行首状态区标 1 创新意识 团队精神 重在参与 公平竞争 9 记为1 表示已排 在教师矩阵相应坐标处赋值机房号 即 a b c d e 2 在机房矩阵处赋值MSIJ 3 2 2 班级信息只使用一次 即若状态处为1 即上机课已排 不再参与之后任何 的参数计算和衡量 教师表和机房表将实时更新 用于后续班级排序的参数 依据 3 3 在每个班级进行程序化排序时 系统会提供一幅相对应的数字地图 在参数 最大的坐标处 即为最佳排课处 约束条件的设置约束条件的设置 依照我们的优先级别 学生空课 教师空余 机房占有情况 分别设置参 数 X1 X2 X3 分别表示 X1 学生空课情况 1 由实际课表上课密集度设置参数值 学生1 2节空 X1 10 学生3 4节空 X1 8 学生5 6节空 X1 4 学生7 8节空 X1 1 X2 教师空课情况 在教师所来天内 2 教师 1 2 节空 X2 9 教师 3 4 节空 X2 7 教师 5 6 节空 X2 3 教师 7 8 节空 X2 2 X3 机房空余情况 同一时段机房空余数为e 0 e 10 即还有几个班可 3 以插入上机 机房 1 2 节空 X3 e 0 01 9 机房 3 4 节空 X3 e 0 01 8 机房 5 6 节空 X3 e 0 01 3 机房 7 8 节空 X3 e 0 01 2 目标函数 Y X1 X2 X3 e 设置依据 设置依据 由于 X1X2 为必备优先级别 但在实际检验操作以及特殊边缘情况的模拟发 现会出现一些相同 Y 值的区域 这使得系统无法自动做出判断 基于这个原因 我们找出了相同的几个特例及相应 Y 值相同的区域 寻找不同点 从人的角度 去安排课 最终给 Y 函数再加上一些附加约束使得这些相同值的区域得以区分 保证整个程序化排课的完整性 则对于附加约束 X3 必须是小于 X1X2 的优先级别 即当 XX 一样时 X3 才 起作用 而 X1X2 不同时 X3 就被覆盖 因此 选择设置 X3 的参数至少小于 X1X2 一位 即 X1X2 为个位 X3 要小于分位 而对于目标函数中的 e 这是为了保证当机房没有空位时 直接致 0 再此不影响前面的大小比较 只是整体放大 作为使能 防止程序化排课中 创新意识 团队精神 重在参与 公平竞争 10 出现溢出的情况 4 3 24 3 2模型的组成及构建模型的组成及构建 第一阶段 人工排序第一阶段 人工排序 人工排序处也并非纯手工进行 首先利用matlab语言把矩阵中所有行分别 相加 即可得到每个班每周的可排课数 对于总排课数小于且等于3的班级 输 出其行坐标 把这些班级交给人工排序 再在每行的第一个状态处赋值1 排入 课的位置赋值为P 表示此班在这个时候上机 在相应老师矩阵上的对应坐标处 标赋相应的机房号 第二阶段 系统排序第二阶段 系统排序 程序化操作流程概述 程序化操作流程概述 1 各矩阵对应参数值的生成 2 对于教师任课天内上机指导的充分安排 3 对于所需加天教师的具体加天安排并在需要加天教师所加天内的充分安排 方法同上 具体操作 具体操作 一 对应参数的设置及生成一 对应参数的设置及生成 先设定e矩阵 矩阵中的值通过安排一个递减一个来表示机房课表矩阵中还可容纳的空余量 起始时个空余量均为10 再设定一个矩阵 X3 1 e 1 0 9 X3 2 e 2 0 8 X3 3 e 3 0 3 X3 4 e 4 0 2 经以上处理我们将得到 创新意识 团队精神 重在参与 公平竞争 11 下面先对教师的0 1矩阵进行处理 MT01 1 9 MT01 1 MT01 2 7 MT01 2 通过该步骤课的如下矩阵 MT01 9 7 1 0 9 0 1 1 9 7 1 1 9 0 0 1 9 7 1 1 即将老师上午一 二节有空的级别赋值为9和7 然后再通过语句 MT01 3 3 MT01 3 MT01 4 2 MT 4 执行后可得到矩阵 即将教师下午一 二有空的优先级别赋值为3和2 此矩阵即为目标函数中的 X2 同样的道理 我们可以得到每个班级的课表矩阵 如陈英老师所教班级物理 1101班所对应的课表矩阵为 材控1103班的所对应的课表矩阵为 创新意识 团队精神 重在参与 公平竞争 12 这也是经过相同的赋值语句得到的 只是我们根据优先级别的不同 对学生上 午一 二有空赋值为10和8 下午一 二有空赋值为4和1 这样赋值即可将优先 级别的不同通过数值的大小反映出来 此矩阵即为目标函数中的X1 下一步我们来做两个矩阵的相加 通过如下语句 B0101 MT01 MS0101 X3 和 B0103 MT01 MS0103 X3 得到老师与学生的课表矩阵以及X3的加和 B0101 1818 15 6 3 1818 8 6 5 1818 15 10 5 1818 8 3 5 1818 15 6 5 和 B0103 18 15 10 2 18 8 10 5 18 2323 6 5 18 16 3 5 18 15 6 5 上面两个矩阵中用黑体字标出的部分即为可安排上机的最优时间 如B0103中的 23所在的位置 同时还应该让23对应于e矩阵中的位置中的元素递减一 即e变 为 在这两个矩阵中我们还没有看见矩阵X3发挥出的作用 但在e矩阵逐渐递减以后 X3在确定优先级上将起到重要作用 事实上我们还可以用matlab语句直接输出最大值所在部分的下标 m v 参 数m表示优先级别最大的数值表示 i表示上机实践应该安排在课表中的位置 如B0103中 m v 15 8 即表示该班级的上机实验可以安排在周三的第二节 创新意识 团队精神 重在参与 公平竞争 13 课 计算方式为以矩阵的列开始数 一直数到8 所在的位置即为应该安排的 位置 但如B0101矩阵中的最大值有五个的情况 我们总是选取第一个来安排 同 时在安排一个班级以后 该教师对应的位置就不应该再参与安排 所以需要实 时更新教师的课表矩阵 可以通过以下的代码实现 for i 1 1 length MS B MT MS i m v max B a i v MT i 0 end 设定X3矩阵和对教师矩阵进行更新就避免了每次在相同情况下总选择第一个而 造成的溢出 对于极小概率的溢出 第三部分还会处理 而程序中的MS元胞 矩阵可以也是可以通过程序实现的 以上的详细代码和解释参见附录二 代码 1 以上对于排课的操作我们只是举了一例 对于一个老师教有多个班级的情 况 我们是可以一次性通过循环语句来完成对矩阵中优先级的赋值和实现老师 与学生课表矩阵以及X3的相加的 即一次给出老师所教所有班级的 m v 下面我们解决的问题是关于老师在任课天数内无法安排下所教所有班级的 上机实践而需要老师另外单独来一次 专门指导学生上机的情况 二 确定加天教师和具体所加天并在所加天中排课二 确定加天教师和具体所加天并在所加天中排课 完成了教师所来天内的充分上机安排 则保证了已排课的班级必为任课老 师指导 接下来 便是选出所要加天的教师 依据所带上机班级数是否大于所 任教班级的一半进行加天老师的选择 而后进行的则是具体加哪天 这一部分所要保证老师所加的那天 尽可能的指 导到最多的班级 这样才能让老师来的意义最大化 算法则应保证在所选天内 未排班级之间的空课是相互错开的 这一部分的算法 将在C代码中体现 详细 见附录二 代码2 在教师指定加天内 若加课 也只为一天 进行最优化排课 再按照上面 方法进行进一步排课 第二阶段 人工调整第二阶段 人工调整 主要通过人工解决一些问题 一种情况 对于还有未排的班级 由于先前已经最大化教师 即剩下的班 级在教师所来天内 包括之后的附加天 都无法被自己教师指导到 那么都交 给管理员指导 这是很少的一部分 另一种情况是两个班级可以合并在一个机房的情况 如下表 周一 A 物理1101 01 B 物理1102 第一节 创新意识 团队精神 重在参与 公平竞争 14 注 里面的是安排去指导的老师的代号 01即表示陈英 同样 此例也是便于说明而作的假设 实际 中不一定存在 如上表中在A机房中知道物理1101班的陈英老师就不可能再去B机房指导物理 1102班 题目中有这样的要求 而A B机房各有一个管理员 完全可以安排 物理1102班也去A管理员的机房上机 这样就可把B管理员解放出来 使其有一 定的休息时间 4 3 34 3 3 实际情况的模型求解实际情况的模型求解 第一阶段 第一阶段 由matlab矩阵统计得出一周内空课数小于等于3的班级有如下五个班 机工1107 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 建艺1101 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 建筑1102 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 工业1101 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 冶金英才1101 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 对于以上五个班 我们的小组人员给予以下安排 第二阶段 第二阶段 系统给出的各班排课坐标 通过程序化给出每个班级应该排课的位置 如图中的v所示 m代表最高优先级 创新意识 团队精神 重在参与 公平竞争 15 第三阶段 第三阶段 人工优化整合 最终给出的上机安排 见附录一 表2 五 模型的检验 对于本模型的检验我们给出如下两个标准 机房课表的离散度离散度 1 离散度数据评价 见附录一 表 3 离散度图形对比 第一次人工排课离散情况 柱形高度表示相应时段空课数 2 0 2 4 6 8 10 周一 周二 周三 周四 周五 7 8节 5 6节 3 4节 1 2节 7 8节 5 6节 3 4节 1 2节 创新意识 团队精神 重在参与 公平竞争 16 本实验提供最优排课的离散情况 柱形高度表示相应时段空课数 0 2 4 6 8 10 周一周三周五 7 8节 3 4节 7 8节 5 6节 3 4节 1 2节 由图可知离散度整体有很大的改善 教师所指导班级占其任教班级总数的比例 见附录一 表 4 2 六 模型的评价 6 1 模型的优缺点 1 本模型实现了程序化排课 并扩大了程序排课的部分 大大减少了人工 排课的工作量 并且丝毫未减其合理性及其人性化排课的初衷 2 本模型在现有的条件下 综合分析 利用合理的加天化模式 最大化地 实