科技信息 高校讲坛 ○ ○ SCIENCE & TECHNOLOGY INFORMATION 2009 年 第 期 7 基于回溯算法的高校排课系统 宋晓飞 王 鹏 贺敏佳 燕山大学里仁学院教务部 河北 秦皇岛 （ 066004） 题 。 】 应用回溯算法设计自动排课系统 摘 要 【 有助教务人员管理排课相关的各种信息 关键词 自动排课系统 ， 数据库 回溯算法 ， ； ； 【 】 约束条件 ； ； ， 冲突 能简化程序的复杂度和减少生成最佳课表的时间 解决排课系统中的资源冲突 课表优化问 进行自动排课 从而减轻排课的工作量 提高排课的效率和科学性 、 ， 、 提高教学管理水平 , 。 班级 数据库实体 实体及各个实体之间的关系 教师 教室 ： ， ， ， 教学任务 ， 设计的 ， E-R 排课结果 图如图 。 所示 1 ： 根据上述数据库 、 还 ， 图 1 数据库实体 图 E-R 算法设计 2.3 2.3.1 , , , , 。 DFS ( 以达到目标 回溯算法 回溯算法 也 叫 试 探 法 它按优先条件向前搜索 可以被认为是一个有过剪枝的 题的解的方法 过程 现原先的选择并不优或达不到目标 , 溯条件的某个状态点称之为回溯点 。 选优条件即为排课数学模型中的约束条件群 资源集中的元素特征相互作用形成的数学关系 群 足约束条件群 该选择即为不优或达不到目标 就退回一步重新选择 但当搜索到某一步时 它 是 一 种 系 统 地 搜 索 问 深度优先搜 索 ) 发 而满足回 具体到计算机智能排课系统中 , 需求集中的元素特征与 若不满足约束条件 当遍历该步骤的所有可能仍未满 则该状态满足了回溯条件 回溯算法的应用 在本系统中 该状态点即为回溯点 自动排课使用的算法是简 能够在一门课程安排不下的情况下返回上一个安排了 具体的算法设 让上一门课程重新安排后再重新安排这门课 2.3.2 ) 。 , ， 。 。 ， 。 ( , , , 。 单的回溯算法 的课程 计如下 ， ： 将所有符合学年学期和年级的课程按照一定的顺序排列得到 按顺序选择一门课程 开始周次 ⑵ 班级名称 学时 并得到这个课程的相关信息 就算每周上的课次 截至周次 如教师 ， Ki， 、 。 ID、 、 、 按照一周的时段顺序选一时段 判断时段 不冲突则跳转到 ⑶ ⑷ 是否和教师的时段冲突 ， Sj。 Sj ⑸。 ， 如果冲突则跳回 下转第 （ 如果 页 ） ⑶， 588 565 引言 0. 在高校教学管理中 ， 每学期管理人员都要整理教学计划 ， 然后根据教学任务书编排课程表 常重要的工作 达教学任务书 件多 的管理手段完成这些繁琐的工作 进行合理配置 的维护和教学效果的提高有重要的作用 课程的安排和管理是每个学校教务活动中非 根据教学计划下 限制条 人们希望用先进 从而对有限的师资力量和教学资源 这对正常教学秩序 使排课成为教务管理工作中的一个难点 在最短期内排出高效 它涉及面广 科学的课表 ， 为此 、 ， ， ， ， 。 ， ， 、 ， 本文正是基于此点对排课工作进行信息化构建 。 能根据教学计划的内容以及一些限制条件自动生成课程表 自动排课的智能化 性 从而减轻排课的工作量 提高教学管理水平 ， 、 ， 以达到排课系统 充分体现 提高排课的效率和科学 ， , 。 系统实现的目标 1. 本设计要符合学校的实际情况 ， ， 为避免各种冲突 紧张的特点 系或各授课部门的课程申请汇总 务书来实现自动排课 进行各种课表的查询 进行输出 ， ， ， 先设定教师不能上课的时间段 也就是教师和教室资源相对比较 并把各 然后根据录入的教学计划和开课任 排课后生成课表以便 班级的上课情况等相关数据 排课结果可以进行微调 能够将教师 教室 ， ， 。 、 、 并且系统应具有方便灵活的修改 串课等调整功能 、 。 自动排课系统的设计要符合学院实际的情况 ， 对比较紧张的特点 课部门的课程申请汇总 自动排课制定课表 进 行 各 种 课 表 的 查 询 出 编排准确 功能如下 合理 快速 ， 。 、 、 、 应该能够避免各种冲突 ， 。 ： 教师和教室资源相 系统能够把各系或各授 然后根据录入的教学计划和开课任务书实现 排课后能生成课表以便 。 班 级 的 上 课 情 况大 量 地 输 、 为了使课表的 调课等功能 本系统要完成的主要 充分利用学校资源 、 。 排课结果可以进行微调 高效 ， 教 室 并且系统应具有方便灵活的课表修改 能 够 将 教 师 ， 、 。 ： 教室 班级信息进行一些基本的操作 能够对教师 能够进行教学任务的录入 能够在自动排课之前进行手动的提前安排 、 、 ， 比如实验 指定每个课程上课周次大概区间 。 体育等 。 ， ， 可以进行一些老师特殊要求上课时段的课程提前安排 能根据教学任务自动进行排课 一教室同一时段不能安排两门课程 ， 。 教室不冲突 。① 避免各种冲突 同 ： 人数不能超过教室的最大容量 。 同一班级学生不能在同一时段上两门或两门以上课 同一班级统一课程不能在同一时段在不同地点上 同一教师不能在同一时段在不同地点上课 ； ： 学生不冲突 ② 程 课 。 ③ 。 ④ ： 课程不冲突 教师不冲突 ： 能够对已经安排的课程进行细微的调整 在班级和教师都允许的 情况下改变上课时段和教室 。 教室 能够查询每个教师 能够统计三者的上课情况并大量地输出三者的上课情况的表格 班级的课表 并且将课表输出 系统还 、 、 ， 系统设计 总体模块设计 通过对自动排课管理系统的功能分析 2. 2.1 可以 ， 大致定义出系统主要功能模块包括以下几个 。 。 。 ， ： 基本信息模块 包含教师信息模块 ： 、 教室信息模块 班级信息模块 、 三个子模块 。 。 ： ： ： 任务处理模块 这个主模块是系统中最为重要的模块 任务录入模块 自动排课模块 手动排课模块三个子模块 、 、 结果处理模块 包含课程调整模块 课表查询模块 、 、 。 课表输出模块 包含教学 ， ⑴ 课程集合 K。 三个子模块 2.2 数据操作模块 包含重新安排模块和数据初始模块 数据库设计 在本系统的数据库设计当中 一共涉及到五个 。 ， 

科技信息 职校论坛 ○ ○ SCIENCE & TECHNOLOGY INFORMATION 2009 年 第 期 7 ， ， 。 ， 。 行为规范 在护理教学中 通过教师自身素质美激发护生学习的兴趣 举止得当 让护生联想到白衣天使 教学设计新颖 的行为是学生模仿的直接对象 移默化的教育效果 到仪表端庄 盈 实 时 业美感 。 护生专业知识的同时 敏捷 课堂组织严密 对病人需求的关照 笔者注重自身的素质美 ：（1） 教态自如 ， 知识美 教师 教师良好的素质修养对学生能起到潜 每次上课做 示教护理操作时步履轻 教学中做到专业知识扎 如在示教静脉输液 一针见血穿刺成功给学生一种赏心悦目的职 在教给 ， 。 （2） 渗透人文知识 ， 笔者自身热爱专业 ， 也给护生美的感受和美的欣赏 开展主题教育活动 实施德育的其他手段 严以律己 尊重学生 仪表美 品德美 。 （3） ， ， ， ， ， ， 。 ， 。 。 ， ， ， 。 、 。 围绕主题 组织 文娱活动等使护生在文化生活气氛中受到教 使护生从中逐步实现道德自 文明宿舍 文明班级 文 发展护生的道 ”、“ 自立能力的提高 校内外劳动 创建 开展榜样教育 ， 促进护生自主 ”、“ ， ， 、 ， “ 、 ， 组织学雷锋活动 2.2.2 、 故事会 。 、 团队活动 班会 育和感染 我完善与知行统一 明学生 德评价 。 的评比活动 ， 道德思维能力 因材施教 ” 。 ：“ 、 2.3 俗话说 生为出发点 为手段 ， 个别因素 现代化教学手段 ， ， 开展成才素质教育 ， 教学有法 以既传授知识又培养能力为目标 教无定法 贵在得法 ， ， 教师主导作用贯彻始终的教学原则 经常开设小组教学 个别教学 力求促进教学质量的提高 ， 新世纪是一个竞争的时代 既是科技的竞争 导护生认识当今社会是一个优胜劣汰的市场 ， ， ”。 [2]笔者坚持以教材和学 以发挥学生主体作用 。 [3]针对护生的专业特点及 运用 角色扮演等教学活动 ， ， ， 。 ， 又是人才的竞争 引 使他们进一步强化学习 。 ， 。 ， 增进学习动力 树立良好的学风 、 促进其具有 激发他们奋发向上 计算机的培训及其他学习兴趣班 ， 引导护生正确认识自己的能力 目的 实 ， 英语 质 就业竞争激烈的问题 生确立起按社会主义发展需要来选择适合发挥自己能力的岗位思想 进行双向选择定位 针对中专生就业难的客观现 在校期间参加 从而提高护生自身的文化素 针对当前双向选择 使护 为今后就业打好基础 对高年级护生开展 就业与创业 一专多能 的教育 ”， ， ， ， ， “ 。 ， “ ” ， ， ， 培养敬业奉献精神 护生的德育工作唱老调 ， 才能收到预期效果 所带护理班级连年被本校评为 。 。 。 ， 走老路是不行的 只有顺应形 笔者对护生采取上述的德育措施 ， 先进团支 本校老师对护生的评价好 ， 吃苦耐劳的精神受到实习 受到用人单位的一 文明班级 ”、“ “ 、 部分护生被评选为学校学生会干部 ； 护生的艰苦朴素 ； 肯定 护生毕业就业率高 、 ； ， ， 实践证明 锐意改革 势 ， 取得较好效果 部 表扬护生的综合素质高 单位领导和老师的表扬 致好评 ”； ： 科 。 ● 梁琼芳主编 邓 小 平 教 育 思 想 与 广 东 教 育 改 革 第 一 版 ， ， 广 东 人 民 出 版 社 ， 参考文献 【 】 ， ［1］ 1998，12：341. ［2］ ［3］ 王道俊 王道俊 . . 王汉澜主编 王汉澜主编 教育学 教育学 ， ， ， ， 第二版 第二版 ， ， 人民教育出社 人民教育出社 ，1999，3：244. ，1999，3：230-231. 作者简介 郭雪媚 ： ， 广东省潮州卫生学校护理讲师 。 责任编辑 田瑞鑫 ： ］ ［ ● 上接第 果冲突则跳回 （ 565 ⑶， 判断时段 页 如果不冲突则跳转到 ） ⑸ Sj ⑹。 是否和所有的班级时段冲突 如 ， 将所有符合课程 要求的教室按照一定的顺序排列得到教室 时段的冲突 如某些教师的可以上课的时段比较少 高 这样能减少教师的时间冲突 ， ， 上课人数相同的课程再按照教师的优先级别来安排 比 那么他的优先级就应该比较 。 能力不是一件容易的事 ） 页 542 上接第 （ 螺旋上升的一个漫长而细致工程 汉语阅读技巧 、 写 能力的培养 读心理辅导者 。 交流伙伴与评价者 在这过程中 ” ， 。 ， 需要经过培养汉语阅读兴趣 、 听 而是需要有一个循序渐进 、 掌握 说 、 阅 同时要与大力加强 、 管理引导者 “ ， 教师应是学生的帮促者 、 、 养成汉语阅读习惯等过程 、 科 。 【 北京文化大学 参考文献 北京 】 年 ,2007 , ● 月 . 9 责任编辑 翟成梁 ： ］ ［ 大学汉语阅读 》, ［1］《 588 Ki 集合 ⑹ J。 ⑺ ⑻ 按顺序选择一个教室 判 断 时 段 与 教 室 不冲突则跳转到 Jn。 Jn Sj ⑼。 与教室 是 否 冲 突 如 果 冲 突 则 跳 转 道 ， 如 果 ⑿， 到 ⑵， 中 ， ⑿ 跳转到 到 ⒀ ⒂。 ⒁ 教室 师 ⑼ ⑽ Sj Jn 分别保存到数组 将时段 判断本课程是否安排到了一周的最后一节课 否则跳转到 将数组 ⑾。 和 A() 和 B()。 ， 一一对应时段和教室更新到排课结果信息表 如果不是则跳转 ⑾ 更新教师 A() 教室 B() 判断教室 、 班级的上课时段 、 是否是教室集合 Jn 否则跳回 ⒀， 选择是否进行课程 ⑺。 。 J 中的最后一个教室 如果是则 ， 回溯处理 ， Ki 选择是跳转到 ⒁， 选择否跳转 删除上一门安排了的课程的排课结果信息表 班级的上课时段进行修改 、 、 将这门课程暂时放一边 教学任务信息表中的排课标志 ⒂ 。 等待以后手动安排 ， 选择下一门课程 ， 跳转到 ， 选择上一门课程 并把相关的教 跳转到 ⑵。 修改这门课程的 ， ， ⑵。 在排课的过程中 上课班级多的课程先安排 课程安排的优先是按照上课的班级多少来排列 这样很大程度上避免了班级之间上课 ， ， ， 的 ， ， 结论 3. 本文详细论述了自动排课系统的开发过程 中的应用 教学任务里的课程要求安排 。 该系统基本实现了教务管理人员对自动排课要求 ， 以及回溯算法在系统 能够将 ， 。 科 。 ● 令锋 ， 崔振兵 ， 参考文献 】 【 黄春艳 ． 高校自动排课系统核心算法的设计与实 ，2007；28（2）：34－37． 张佳 ， ． 计算机排课系统的设计与实现 福建电脑 ． ，2005；7：P118－ 徐远纯 方 义 高校智能排课系统 ． 高 校 智 能 排 课 系 统 的 设 计 与 实 现 福建电脑 ． ，2006；4：149－150． 计 算 机 与 现 代 化 ． ， ， ． ， ， 陈建平 李坚 ， 肇庆学院学报 姚茂群 陈麟 ［1］ 现 ． ［2］ 124． ［3］ ［4］ 2004；l1．102－105． 卢荣华 ， 熊 璋 李娟 赵 晓 庆 ， ， 作者简介 宋晓飞 ： 月毕业于燕山大学计算机科学与技术专业 燕山大学信息科学与工程学院在读硕 士 研 究 主要 获工学学士学位 （1982—）， ， ， 年 生 研究方向为编码理论 ，2004 7 信息安全 、 、 软件工程 。 责任编辑 张新雷 ： ］ ［ ,2001 年 月 . 7 乌鲁木齐 北京 ,2000. ● 汉语教学教法 大学英语阅读 》, 》, ［2］《 ［3］《 新疆教育出版社 人民教育出版社 , , 作者简介 研室汉语教师 究工作 。 ： ， 呼马尔别克 博潘 毕业于新疆大学中语系 · ， 哈萨克族 女 系伊犁师范学院基础部语言教 主要从事大学预科汉语阅读教学与研 ， ， ，