排课系统设计毕业论文

本科毕业论文 设计 题目 排课算法的研究与开发 姓 名 周林 学号 20111001954 所在院系 信工学院 专业 信息工程 指导教师 张发勇 职称 副教授 评 阅 人 职称 2015 年 06 月 学位论文原创性声明学位论文原创性声明 本人郑重声明 所呈交的论文是本人在导师的指导下独立进行研究所取得 的研究成果 除了文中特别加以标注引用的内容外 本论文不包含任何其他个 人或集体已经发表或撰写的成果作品 本人完全意识到本声明的法律后果由本 人承担 作者签名 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保障 使用学位论文的规定 同意学校 保留并向有关学位论文管理部门或机构送交论文的复印件和电子版 允许论文 被查阅和借阅 本人授权省级优秀学士学位论文评选机构将本学位论文的全部 或部分内容编入有关数据库进行检索 可以采用影印 缩印或扫描等复制手段 保存和汇编本学位论文 本学位论文属于 1 保密 在 年解密后适用本授权书 2 不保密 请在以上相应方框内打 作者签名 年 月 日 导师签名 年 月 日 精品文档 3欢迎下载 排课算法的研究与开发 本科生 周林 指导教师 张发勇 摘 要 作为一个学生 无论是在小学中学还是大学 课表都是我们在学校里接触最多的 然 而 我们很少会去关注课表是怎么排出来的 尤其是在大学以前似乎课表并不复杂 然后 到了大学里 看似简单的课表却引起了我们的注意 大学里的课程往往具有很强的随机性 和流动性 学生个人的课程有一定的共性但是却不完全相同尤其是课程往往没有固定的教 室 而是根据自己的选课情况来安排上课时间和地点 而且我们也发现大学中教室的资源 往往非常紧张 这样一来排课问题就构成了一个多类资源的优化组合问题 S Even 等人 在 1975 年将排课问题论证为 NP 完全问题 这类问题往往没有唯一解 而只能在有限的 要求范围内求得相比较而言更合理的解 那么 如何在有限的教室 老师资源以及各种硬 性软性要求给出一个最优解就是排课算法的核心要求 本课题着重与在优化现有的排课算 法 尤其是遗传算法 针对其在排课应用中的不足进行优化从而能够得出更为高效 合理 的排课算法解决高校排课问题 关键词 JSP 遗传算法 排课系统 SchedulingScheduling AlgorithmAlgorithm ResearchResearch andand DevelopmentDevelopment Bachelor Candidate Zhou Lin Supervisor Zhang Fayong ABSTRACT As a student whether it is in contact with all of our elementary school or university the largest in the school curriculum However we rarely focus on curriculum is how to row out in particular seems to be at the university curriculum is not complicated before Then to the university seemingly simple schedule has caught our attention There is no fixed course in the university classroom students are no longer the same as before with a class as a unit to go to class But according to their own situation to arrange elective class time and place but we also found that university classroom resources are often very tight As a course arrangement constitutes the optimal combination of many types of resources problem S Even et al 1975 will demonstrate to course scheduling problems NP complete problems Such issues are often not the only solution but only to obtain a more reasonable comparison solution within a limited range of requirements So how to give an optimal algorithm is arranging the core requirements for limited classroom teacher resources and a variety of soft rigid requirements This paper focuses on optimizing existing and Scheduling algorithms especially genetic algorithm arranging for its shortcomings in the application were optimized to be able to draw a more efficient and rational Arranging Course Scheduling algorithms to solve problems Keywords Keywords JSPJSP genetic genetic algorithmalgorithm Scheduling Scheduling SystemSystem 精品文档 5欢迎下载 目 录 第一章 绪论 1 1 1 排课算法研究背景 1 1 2 常用的排课算法对比 1 1 2 1 贪心算法 1 1 2 2 回溯算法 2 1 2 3 遗传算法 2 1 3 课题目标以及意义 3 1 3 1 课题目标 3 1 3 2 课题意义 3 第二章 相关知识概述 4 2 1 Java Server Pages 4 2 1 1 Java Server Pages 简介 4 2 1 2 Java Server Pages 特点 4 2 2 SQL Server 2005 5 2 2 1 SQL Server 2005 简介 5 2 2 2 SQL Server 2005 特点 6 2 3 MyEcplise 6 2 4 本章小结 7 第三章 排课算法设计 8 3 1 排课问题描述 8 3 2 排课问题分析 8 3 3 约束条件 9 3 4 约束条件数学表示 9 3 5 排课算法 遗传基因编码 11 3 6 排课算法 适应度计算 12 3 6 1 离散程度适应度计算 12 3 6 2 较难课程适应度计算 13 3 6 3 特殊课程适应度计算 13 3 7 排课算法 选择 交叉和变异 13 3 7 1 选择 14 3 7 2 交叉 14 3 7 3 变异 14 3 8 排课算法 课程冲突检测 14 3 9 主要算法描述 15 3 9 1 选择算法描述 15 3 9 2 交叉变异算法描述 16 3 9 3 排课算法描述 17 3 10 本章小结 20 第四章 排课系统总体设计 20 4 1 需求分析 20 4 2 系统总体结构 21 4 3 本章小结 21 第五章 排课系统详细设计与实现 22 5 1 数据库设计 22 5 1 1 数据库 ER 图 22 5 1 2 数据库各表设计 22 5 2 登录模块设计 26 5 3 系统主页面总布局 27 5 4 基础信息管理设计 28 5 5 排课设置管理模块设计 30 5 6 排课模块设计 31 5 7 系统管理模块设计 32 5 8 本章小结 33 第六章 总结与展望 33 6 1 总结 33 6 2 展望 33 致 谢 35 参考文献 36 精品文档 1欢迎下载 第一章 绪论 1 1 排课算法研究背景 最初在采用计算机自动排课以前 高等院校只能采用人工排课的方式 人工排课只能 依靠教务处的工作人员手动的安排整个学校教育教学工作 这种手工人力的排课方式有非 常多的缺点 首先最显著的缺点就是排课效率过于低下 其次课表排好以后很难修改 不 便于调整 对于实际使用过程中出现的特殊情况如临时调课等状况不能很好的应对 因此 当学生人数越来越多 达到数万甚至更多 教师人数达到数百数千 要为这成百上千的学 生和教师安排出科学合理的课程表 几乎是不可能的任务 就算能够完成 但也往往需要 花费很大的人力物力 工作量巨大 并且即使排出课程表也不够灵活 很难进行调整 随着高等教育的不断发展 不管是高等院校的在校学生人数还是教职工人数都在不断 地增加 课程安排复杂度也不断提高 着这种情况下 人工排课的缺点与不足就显得更加 突出 手动排课的方式已经无法在满足当前排课问题的需求 同时 随着计算机技术的快 速发展 计算机技术在各个领域的应用也越累越广泛 人们很自然地就将计算机技术应用 到这一领域中 显而易见 使用计算机技术进行排课 可以排课缩短排课时间 节省人力 资源 并且有比较高的排课质量 可以迅速地得出满足各种约束要求的可行排课结果 1 2 常用的排课算法对比 1 2 1 贪心算法 贪心法 greedy method 主要是将分级处理方法进行改进 着眼于局部 然后逐步产生 最优解 贪心算法从问题的一个初始解出发 在特点的原则下做出一系列的选择 一旦做出 选择 就不再进行修改 也就是选择当前状态下的最优选择 从而渐渐逼近原定的理想目 标 在排课问题中 贪心算法就是从某一个初始状态开始 根据给定的策略向安排好所有 待排课程这一目标逐步前进 贪心算法每一步都需要进行判别 在即将进行的下一步中能 否得到可行解的一个解元素 如果可以则持续进行 依然根据贪心策略想目标推进 当算 法不能再找到符合要求的解时 算法停止 最终可以得到可行解 贪心算法的优势在于时间复杂度较小 能用较少的执行步数得到相应的解 而其最大 的不足就是解不够合理 虽然每一步都能做到局部最优化 但是总体得到的结果却不一定 是整体最优解 为了能够尽可能的规避贪心算法的不足 在算法最后能够得到的解更科学 2 116112 10 周林 排课算法的研究与开发 2015 06 合理的整体较优解 为此 可以在算法中采用最优化算法 比如动态规划等 1 2 2 回溯算法 回溯算法也被叫做试探算法 可以认为它是对深度优先算法进行修改和扩充的孙发 回溯算法根据原定的优先条件进行深度优先搜索 但当搜索进行到某一步发现不能满足条 件时 则退回到前一步重新进行选择 其中能够满足返回条件的状态点被称为回溯点 实 际运用到排课算法中 优先条件就是排课问题中的制约条件 如果不能够满足制约条件 那么算法做出的选择就不是最优选择 当在一个状态点遍历了所有可能的选择之后不存在 满足条件的选择 那么这个状态点就是回溯点 回溯法所具有的一个非常重要的特点就是在搜索的过程中会产生解空间 在搜索算法 执行的任何时候 存储从开始到当前的搜索路径 所以 回溯算法的空间需求为一个常数 也就是从开始节点直到最远节点的路径长度 这个特点非常重要 使用回溯算法的解所需 要的空间大小往往是最长路径长度的指数倍数 因此 使用回溯算法排课往往过于消耗存 储空间 特别是数据量大的时候代价太大 回溯算法还有一个缺点就是时间复杂度非常大 1 2 3 遗传算法 遗传算法 英文全称Genetic Algorithm 简记为GA 最早是由美国密歇根大学J Holland教授于1975 年提出 并且在之后出版了非常具有影响历的 Adaptation in Natural and Artificial Systems 遗传算法基于自然进化过程中的自然选择机制和生物 遗传机制 由生物的自然进化过程抽象而来 遗传算法是一种全局优化策略适用于寻找最 优解的最优规划以及多目标规划问题 遗传算法能够有效避免陷入局部最优而能够考虑到 各个因素从而得到全体最优解或次于全体最优解的次优解 有一个故事可以帮助我们理解遗传算法 从前 有一大群袋鼠 它们被莫名其妙的零 散地遗弃于喜马拉雅山脉 于是只好在那里艰苦的生活 这些袋鼠并不知道它们的任务是 寻找珠穆朗玛峰 海拔低的地方弥漫着一种无色无味的毒气 海拔越高毒气越稀薄 可是 可怜的袋鼠们对此全然不觉 还是习惯于活蹦乱跳 于是 不断有袋鼠死于海拔较低的地 方 而越是在海拔高的袋鼠越是能活得更久 也越有机会生儿育女 就这样经过许多年 这些袋鼠们竟然都不自觉地聚拢到了一个个的山峰上 可是在所有的袋鼠中 只有聚拢到 珠穆朗玛峰的袋鼠完成了任务 遗传算法的实现过程实际上就像自然界的进化过程那样 首先寻找一种对问题潜在解 进行 数字化 编码的方案 建立表现型和基因型的映射关系 然后用随机数初始化一个 种群 种群里面的个体就是这些数字化的编码 接下来 通过适当的解码过程之后 用适 应性函数对每一个基因个体作一次适应度评估 用选择函数按照某种规定择优选择 让个 体基因交叉变异 然后产生子代 遗传算法并不保证你能获得问题的最优解 但是使用遗 传算法的最大优点在于你不必去了解和操心如何 去 找 最优解 而只要简单的 否定 精品文档 3欢迎下载 一些表现不好的个体就行了 这是遗传算法的精粹 1 3 课题目标以及意义 1 3 1 课题目标 本课题着重对遗传算法进行研究 将传统的遗传算法进行改进 尽量发挥遗传算法的 优势并改善固有缺陷然后应用到排课算法中 通过计算机来进行自动排课 抽象出问题中 所存在的要素 结合数学表达式来表达一系列的约束条件 并且能够依据课表形式和排课 过程中普遍存在的规律 可以有效缩减排课问题的空间搜索范围 从而快速高效的进行排 课 1 3 2 课题意义 教务排课管理系统是高校教务系统中的一项重要组成部分 排课系统否科学高效得排 出高质量的课程表将很大程度上会影响高校的正常教学 有时甚至关系到高校的教育教学 质量 排课系统的首要任务就是排课 首先要把获取学校所有班级 学生的课程信息 再 依据高校各个专业教育教学计划以及高校现有的教学资源来安排各个班级 学生的课程表 从而能够更为高效地配置所有教育资源 使高校教务工作能够非常科学 高效的完成 本 课题的主要研究意义在于实验并完善遗产算法在排课上的应用 同时设计并初步编码完成 一个实验性质的自动排课系统 应用于高校教务教学管理 从而能够提高教务管理的工作 效率 4 116112 10 周林 排课算法的研究与开发 2015 06 第二章 相关知识概述 2 1 Java Server Pages 2 1 1 Java Server Pages 简介 JSP 全名为 Java Server Pages 中文名叫 java 服务器页面 其根本是一个简化的 Servlet 设计 它 1 是由 Sun Microsystems 公司倡导 许多公司参与一起建立的一种动态 网页技术标准 JSP 技术有点类似 ASP 技术 它是在传统的网页 HTML 标准通用标记语言 的子集 文件 htm html 中插入 Java 程序段 Scriptlet 和 JSP 标记 tag 从而形成 JSP 文件 后缀名为 jsp 用 JSP 开发的 Web 应用是跨平台的 既能在 Linux 下运行 也能在其他操作系统上运行 它实现了 Html 语法中的 java 扩张 以 形式 JSP 与 Servlet 一样 是在服 务器端执行的 通常返回给客户端的就是一个 HTML 文本 因此客户端只要有浏览器就能浏 览 JSP 技术使用 Java 编程语言编写类 XML 的 tags 和 scriptlets 来封装产生动态网页 的处理逻辑 网页还能通过 tags 和 scriptlets 访问存在于服务端的资源的应用逻辑 JSP 将网页逻辑与网页设计的显示分离 支持可重用的基于组件的设计 使基于 Web 的应用程 序的开发变得迅速和容易 JSP JavaServer Pages 是一种动态页面技术 它的主要目的 是将表示逻辑从 Servlet 中分离出来 Java Servlet 是 JSP 的技术基础 而且大型的 Web 应用程序的开发需要 Java Servlet 和 JSP 配合才能完成 JSP 具备了 Java 技术的简单易用 完全的面向对象 具有 平台无关性且安全可靠 主要面向因特网的所有特点 2 1 2 Java Server Pages 特点 优点 1 一次编写 到处运行 除了系统之外 代码不用做任何更改 2 系统的多平台支持 基本上可以在所有平台上的任意环境中开发 在任意环境中 进行系统部署 在任意环境中扩展 相比 ASP 的局限性 JSP 的优势是显而易见的 精品文档 5欢迎下载 3 强大的可伸缩性 从只有一个小的 Jar 文件就可以运行 Servlet JSP 到由多台 服务器进行集群和负载均衡 到多台 Application 进行事务处理 消息处理 一台服务器 到无数台服务器 Java 显示了一个巨大的生命力 4 多样化和功能强大的开发工具支持 这一点与 ASP 很像 Java 已经有了许多非 常优秀的开发工具 而且许多可以免费得到 并且其中许多已经可以顺利的运行于多种平 台之下 5 支持服务器端组件 web 应用需要强大的服务器端组件来支持 开发人员需要利 用其他工具设计实现复杂功能的组件供 web 页面调用 以增强系统性能 JSP 可以使用成 熟的 JAVA BEANS 组件来实现复杂商务功能 缺点 1 与 ASP 也一样 Java 的一些优势正是它致命的问题所在 正是由于为了跨平台 的功能 为了极度的伸缩能力 所以极大的增加了产品的复杂性 2 Java 的运行速度是用 class 常驻内存来完成的 所以它在一些情况下所使用的 内存比起用户数量来说确实是 最低性能价格比 了 2 2 SQL Server 2005 2 2 1 SQL Server 2005 简介 Microsoft SQL Server 2005 是软件开发中使用非常广泛的数据库管理系统 它是由 美利坚合众国的微软公司开发并推出的数据库开发 管理系统 它是由一系列的图形工具 整合在一起构成的 这些图形工具主要有服务器管理 企业管理器和查询分析器 服务器 管理的主要功能是启动和关闭数据库服务 企业管理器的主要功能是创建 修改和备份数 据库 查询分析器的主要功能是交互执行标准 T SQL 语句 SQL 函数和存储过程 而且具 有图形化的查询分析功能 SQL Server 2005 作为一款数据库开发与分析的软件 能够方便快捷的为可伸缩性的 电子商务 企业 ERP 和数据仓库等创建出优秀的解决方案 在 SQL SERVER 的 2005 版出现 时 Internet 网络已兴起 所以它为网络应用程序的开发和设计做了很多工作 能很好的 适应网路应用程序的数据管理和数据分析 在开发电子商务 数据仓库应用时 如果采用 由 SQL SERVER 2005 作为核心组件之一的 Windows DNA Distributed Internet Architecture 架构 能够使得整个应用的开发周期大大缩短 另外 SQL SERVER 2005 全方位支持 HTTP 和 XML Extensible Markup Language 扩展标示语言 SQL Server 2005 具有着性能高和企业级可伸缩性的特点 SQL Server 2005 安装部署 与 Windows NT 操作系统之上 与操作系统一起提供了对多处理器 大内存和 64 位硬件平 台的支持 而且 SQL Server 2005 还支持 WindowsNT 的多路群集 为较大规模的应用提供 了良好的支持 在可管理性和易用性方面 SQL Server 的上一个版本 7 0 在行业内就处于 领先地位 而升级版的 2005 不仅在可管理性和易用性方面做了大量改进 而且在性能 扩 6 116112 10 周林 排课算法的研究与开发 2015 06 展性和安全性方面也做了许多改进 SQL Server 2005 能为具有商务活动的网络站点提供优异的性能 具有商务活动的网 络站点对性能 可管理性 易用性都有较高的要求 而 SQL Server 2005 能够很好的做到 这些 2 2 2 SQL Server 2005 特点 1 SQL Server 2005 的数据分析性能是非常高效的 SQL Server 2005 具有高效的数据操作机制 SQL Server 2005 在处理查询时 能够智 能优化 SQL 语句 对 Where 条件中的多个条件进行分析 找出最佳的过滤及交叉顺序 并 且可以将优化好的 SQL 语句缓存起来 下次再有同样的 SQL 查询时将直接使用缓存的优化 过的 SQL 语句 2 SQL Server 2005 的业务扩展性是灵活的 数据仓库技术直接回答的是业务问题 其实现方式也是以解决一个个业务需求的形式 组织的 随着新业务的出 业务需求建设新的模型 这种堆叠形式的建设方式为整个系统随 业务的发展而平稳发展提供了良好的条件 3 SQL Server 2005 的安全性是与操作系统集成在一起的 Microsoft SQL Server 2005 的安全性是与 操作系统集成 在一起的 从而可以利 用 windows 的强大功能 为数据库 用户实现更高的 安全性 操作系统提供了 OLAP 管 理器 通过 OLAP 管理器强大而专业的管理功能 实现对用户权限的更为细致和专业的 划分和控制 Microsoft SQL Server 2005 具有细致而全面的安全设置选项 数据库 用户具有不同的级别划分 数据库管理员可以根据实际情况 对数据库用户进行细致的 级别划分 使得数据系统的安全性更有保障 由高到低的级别依次为服务器级 数 据库级 多维数据集挖掘模型 级 维度成员 级和单元级 4 SQL Server 2005 的易用性 SQL Server 2005 的企业管理器是图形化工具 界面显示与操作方式都与 Windows 操 作系统的类似 在当前 Windows 普及的背景下 开发人员可以很快上手并熟悉 基本不用 化太多时间专门的学习 SQL Server 2005 软件的使用 SQL Server 2005 可以对工作负载 进行动态优化 根据最优的参数设置进行智能调节 从而尽可能减轻数据维护管理人员的 工作量 SQL Server 2005 还为开发人员提供了各种常用操作的向导程序及功能强大的图 形化编辑器 向导程序可以让开发人员能够在图形化界面下 按向导的操作提示逐步完成 相关操作 极大的方便了开发人员的使用 图形化编辑器更是使得开发人员可以通过几次 选择操作 就能完成本来需要手敲的脚本 大大提高了开发人员的开发效率 而且降低了 出错率 SQL Server 2005 还提供了将数据导入导出向导 可以方便的将数据库中导出到 Excel txt 等格式文件中 也可以这些格式文件中导入数据 2 3 MyEcplise 精品文档 7欢迎下载 MyEclipse 企业级工作平台 MyEclipseEnterprise Workbench 简称 MyEclipse 是对 EclipseIDE 的扩展 利用它我们可以在数据库和 JavaEE 的开发 发布以及应用程序 服务器的整合方面极大的提高工作效率 它是功能丰富的 JavaEE 集成开发环境 包括了完 备的编码 调试 测试和发布功能 完整支持 HTML Struts JSP CSS Javascript Spring SQL Hibernate 1 MyEclipse 是一个十分优秀的用于开发 Java J2EE 的 Eclipse 插件集合 MyEclipse 的功能非常强大 支持也十分广泛 尤其是对各种开源产品的支持十分不错 MyEclipse 可以支持 JavaServlet AJAX JSP JSF Struts Spring Hibernate EJB3 JDBC 数据库链接工 具等多项功能 可以说 MyEclipse 是几乎囊括了目前所有主流开源产品的专属 eclipse 开 发工具 2 4 本章小结 本章主要介绍了本课题所应用的核心技术以及其主要特点 8 116112 10 周林 排课算法的研究与开发 2015 06 第三章 排课算法设计 3 1 排课问题描述 排课工作是高校教务管理工作中非常关键 重要 而且极其复杂的工作 显而易见 排课工作的本质就是在高校有限的教育教学资源下 为所有学生安排课程的时间和地点 从而进一步保证整个学校的教育教学工作能够十分有序合理地进行 四十多年一来 业界 对排课算法的研究从来没有间断过 众多研究人员的努力 也让我们在这个领域取得了许 许多多成果 然而 对排课算法的研究依然还没有到达完美的境地 在面对一些非常复杂 的情况时例如排课数据规模极其庞大 排课约束条件异常复杂 并且不断变化等 总而言 之 排课问题到目前为止仍然没有得到完美解决 排课问题是一个规划组合问题 这个问 题在解决的过程中会涉及到很多因素 它要确保在排课过程中老师 教室和学生之间不可 以有冲突 这里说的冲突就是指同一个教室在同一个时间安排了超过一门课 或者同一个老 师或学生在同一时间有两门不同的课等等情况 与此同时还需要满足老师以及教室数量的 约束条件 排课问题的本质就是对高校中对老师 教室等教务资源的分配过程 排课问题的解决总 的来说可以分为2 个主要阶段 1 各个专业根据原定的教学计划产生课程计划 为对应课 程分配班级和教师 通常由手工完成 2 根据课程计划为课程分配时间和教室 3 2 排课问题分析 我们在解决排课问题的过程中 有着许许多多的矛盾和冲突 排课的班级 任课教师 上课时间 课程 上课地点等进行组合会产生一系列的互相不兼容的问题影响课表的实际 使用科学性 所谓排课任务 其实质就是将教室 老师 班级 课程的不同组合排列到一 周之中的所有上课时间片中 排课过程中 必须能够比较准确 科学 合理得安排课程 必须能够把人力 物力 空间 时间的利用效益最大化 排课问题并不是简简单单得将课程 班级 教室进行简单的排列组合就能够解决的 相反 排课问题在解决的过程中会涉及到许许多多实际因素和现实条件的制约 通过仔细 的分析和充分的调研 大致可以将排课问题所会涉及到的主要因素归纳为以下的制约因素 1 时间因素 排课问题中课表是按周来安排的 平均在一个学期之中存在大约 20 个 周 高校排课系统所需要排出的课表是以周为单位的周课表 每周中可以排课的有 5 天 周 一到周五 无特殊需求一般不考虑周末排课 每天五个时间段 本系统排课以大课时为单 位 上午下午各有 2 个大课时 晚上只有 1 个 精品文档 9欢迎下载 2 课程因素 所有课程都有各自不相同的难易程度以及课程类型 不同的课程需要指 定的对应的讲课教师 且部分较为特殊的课程对使用的教室也有特殊要求 比如 物理以 及相关实验课程需要安排在物理实验室上课 化学课程需要在化学试验室上课等 3 教室因素 教室属性中具有编号 类型 容纳人数 地点等属性 其中教室类型是 对应于课程对教室类型的需求 在排课过程中 教室容量必须不小于上课的班级中的人数 此外 还有一个显而易见的就是 在同一时刻 一个教室中只能安排一个课程 4 班级 个人 因素 同一个班级 学生 在同一时刻的同一个教室不可能上不同的 课或者在同一时刻不可能出现在不同的教室 5 教师因素 同一个教师在同一时刻的同一个教室不可能教不同的课或者在同一时刻 不可能出现在不同的教室 3 3 约束条件 通过在上一部分中的对排课问题分析 我们知道在排课问题的解决过程中有很多因素 需要考虑 也就是说在排课的过程中有很多约束条件 总结一下得到最基本的 6 项硬性约 束和 6 项非硬性 软性 约束 硬性约束 1 同一班级或者个人在相同课程时间段只能在相同的教室上相同的课程 2 同一教师在相同课程时间段只能在相同的教室相同的课程 3 在相同课程时间段的相同的教室不能安排不同的课程 4 参与排课的教室总数不得小于相同课程时间段被安排的课程总量 5 排课教室的必须能够容纳下在这个教室上这门课程的所有学生总人数 6 对应课程必须安排在对应的教室上课 如高等数学可以安排在普通教室是 而物 理实验课必须安排在物理试验室 非硬性 软性 约束 1 教学计划中的公共基础课或者必修课必须得到优先安排 2 单周内课时较多的课程 在排课的是最好能间隔一天以上排课 3 被认定为难度较高的课程应该尽量安排在前两大节课 4 体育课程尽量排在下午 5 排课过程中同一课程尽量安排在同一个教室以方便学生上课 6 课程尽量都安排在周一到周五的时间内 最好不要安排在周末 3 4 约束条件数学表示 为了方便编程以及算法的理解 可以将排课问题中的中的主要元素以及约束条件用数 字字符串来表示出来 教师集合公式 5 1 T TT T1 1 T T2 2 T Tt t 10 116112 10 周林 排课算法的研究与开发 2015 06 t 为教师总数 某教师可以表示为 T Tx x 1 x t 班级集合公式 5 2 C CC C1 1 C C2 2 C Cc c c 为班级总数 某班级可以表示为 C Cy y 1 y c 教室集合公式 5 3 R RR R1 1 R R2 2 R Rr r r 为教室总数 某教室可以表示为 T Tz z 1 z r 课程集合公式 5 4 K KK K1 1 K K2 2 K Kk k k 为教室总数 某教室可以表示为 K Kw w 1 w n 否 是 结束 开始 图 3 1 3 9 2 交叉变异算法描述 算法步骤如下 1 由选择算法任意选出两个个体 A B 并定义一个循环变量 n 0 2 由随机数产生一个取值 1 35 之间的随机数 R1 然后 n n 1 3 交换 A B 对应 R1 位置的 DNA 序列 4 在由随机数产生一个取值 1 1000 之间随机数 R2 5 判断 R2 是否大于 10 若是则进入第 6 步 否则进入第 7 步 精品文档 17欢迎下载 6 生产两个随机数 R3 和 R4 R3 的取值范围为 1 7 R4 的取值范围为 1 5 用 R3 和 R4 取代交换 DNA 序列的个体 A B 对应 R1 位置 DNA 编码的 M 和 N 此过程 对应遗传过程中的变异过程 7 判断当前的循环变量 n 是否大于 14 若是则算法结束 否则跳转到第 2 步 算法流程图如图 3 2 选出两个个体 A B n 0 产生随机数 R1 n n 14 否 是 交换 A B 在 R1 位置的 DNA 序列 生成一个 1 1000 之间随机数 R2 R2 10 是 否 生产随机数 R3 R4 取 代 DNA 编码的 M 和 N 结束 开始 图 3 2 3 9 3 排课算法描述 算法步骤如下 1 初始化一个具有 N 个个体的初始种群 定义遗传代数 g 0 2 由选择算法选出两个个体 18 116112 10 周林 排课算法的研究与开发 2015 06 3 由交叉变异算法得到两个新个体 4 判断产生的新个体是否满足硬性约束条件 是则进入第 5 步 否则跳转到 第 3 步 5 将新个体加入到种群当中 并计算其适应度 6 判断当前的种群数量 n 是否大于 2N 若是则进入到第 7 步 否则跳转到第 3 步 7 将种群中各个个体的进行排序 再根据适应度顺序保留前 n 个个体 剔除余下 个体 g 8 判断当前的遗传代数 g 是否大于 80 若是则结束算法 否则跳转到第 3 部 算法流程图如图 3 3 精品文档 19欢迎下载 初始化种群其大小为 N 定义 g 0 选出两个个体 g 14 否 是 由交叉变异算法得到两个新个体 加入种群 计算其适应度 新个体是否满 足硬性约束 是 否 当前种群大 小 n 2N 将种群中所有个体按适应度排名 保 留前 N 个个体 g 是 否 结束 开始 图 3 3 20 116112 10 周林 排课算法的研究与开发 2015 06 3 10 本章小结 本章着重介绍了遗传算法在排课问题中的应用方式 以及具体算法思路说明和算法步 骤展示 第四章 排课系统总体设计 4 1 需求分析 本课题将基于改进后的遗传算法应用带排课问题当中 在充分查阅和了解高校教务排 课管理系统特点和要求后 得出得到如下基础的功能性需求 排课系统信息设置 1 教室管理 条件搜索教室信息 查看教室信息 删除教室信息 添加教室信息和 修改教室信息 2 教师管理 条件搜索教师信息 查看教师信息 删除教师信息 添加教师信息和 修改教师信息 3 课程管理 条件搜索课程信息 查看课程信息 删除课程信息 添加课程信息和 修改课程信息 4 班级管理 条件搜索搜索班级信息 查看班级信息 删除班级信息 添加班级信 息和修改班级信息 排课设置 1 课程计划管理 可以录入专业课程计划 调整专业课程计划和删除专业课程计划 2 班级课程信息及任课教师信息管理 录入班级课程信息 调整班级课程信息和删 除班级课程信息 以及录入任课教师信息 调整任课教师信息和删除任课教师信 息 排课 1 自动排课 根据事先录入的排课数据 包括教室 学生 老师的数据 然后进 行基于遗传算法的自动排课算法 2 课表调整 手动调整排课结果 并自动检测调试是否符合相应规范 3 课表打印 实验课表打印功能 精品文档 21欢迎下载 4 2 系统总体结构 通过对高校排课特点分析 根据需求需求 把系统总体划分为三个主要功能模块 功 能模块示意图如图 3 1 所示 图 3 1 4 3 本章小结 本章主要冲全局的角度对排课系统所要解决的问题 如何解决问题进行综合叙述 描 述了排课系统的需求以及分析了排课系统功能性需求并展示了系统主要的功能模块划分 22 116112 10 周林 排课算法的研究与开发 2015 06 第五章 排课系统详细设计与实现 5 1 数据库设计 5 1 1 数据库 ER 图 数据库 E R 图如图 3 2 图 3 2 5 1 2 数据库各表设计 教室信息表 教室表 RoomTable 中存储的是自动排课系统中所需要的教室数据 每一条教室数据中 包含的教室信息有教室编号 类型 名称以及教师的容量能信息数据 如表 3 1 精品文档 23欢迎下载 表 3 1 教师信息表 教师信息表 TeacherTable 中存储的是录入到自动排课系统中的所有教师信息数据 每一条教师信息数据中包含了教师编号 工号 姓名 年龄 性别职称还有教学课程信息 各如表 3 2 表 3 2 班级信息表 班级信息表 ClassTable 中存储的是录入到自动排课系统中的所有需要排课的班级数 据 每一条班级信息数据中包含了班级编号 班级名称 班级人数 本机所处的院系和专 业 ID 以及入学年份等信息数据 如表 3 3 24 116112 10 周林 排课算法的研究与开发 2015 06 表 3 3 学期信息表 学期信息表 TermTable 中存储的是 2000 年到 2100 年的学期信息数据 每年可以分为 上半年和下半年两个学期 所以总共有 200 条数据记录 如表 3 4 表 3 4 课程信息表 课程信息表 CourseTable 中存储的是录入到自动排课系统中的所有需要参与排课的所 有课程数据 每一条课程信息数据中包含了课程编号 课程名称 课程类型 总课时数以 及课程需要的教师类型信息数据 如表 3 5 精品文档 25欢迎下载 表 3 5 班级课程信息表 班级课程信息表 C Cinfo 中存储内容是班级 教师 课程以及学期的综合信息 表中 的每一条数据包含的信息有班级和课程 ID 学期 ID 教师 ID 教室 ID 和班级 ID 如表 3 6 表 3 6 学期课程计划信息表 学期课程计划表 TermPlanTable 中存储了每一个专业的学期课程计划信息 表中的数 据包含了课程 ID 以及周课时数以及上课学期等数据 如表 3 7 表 3 7 课表信息表 课表信息表 STable 中保存最终排课结果 表中的每一条数据包含院系 ID 学期 ID 班级 ID 课程 ID 教师 ID 教室 ID 以及课程安排时间 学期和节次 如表 3 8 26 116112 10 周林 排课算法的研究与开发 2015 06 表 3 8 5 2 登录模块设计 登陆模块实现用户登录 高校自动排课系统系统专门为用户射设计了一个登陆页面 用户在对应的文本框中输入自己的登录名和密码 用户输入密码点击登录按钮后 系统首 先通过用户数据库验证用户登陆使用得账号是否存在 若账号存在则对比密码 验证通过 后就可以登录系统 若账号不存在则提示用户登陆错误 另外 本系统支持用户连续尝试 输入密码验证 5 次 连续五次密码输入错误将关闭登陆通道 5 分钟 本系统根据用户登陆 时输入的的账号名称来确定用户权限 而不是采用用户登录前自选本人的用户权限权限来 登陆的方式 所有的系统用户分为管理员 和普通用户 分别具有对系统不同的使用权限 登陆模块设计和登陆流程示意如图 4 1 和图 4 2 图 4 1 精品文档 27欢迎下载 开始 尝试次数大于 5 否 是否 是 用户是否存在 否 密码正确 否 是 登陆成功转到主界面 输入登录名和密码 等待 5 分钟 图 4 2 5 3 系统主页面总布局 系统主页面设计力求简洁直观 主页面布局分布主要采用教务网站常用的的布局 标 题在上部 功能菜单栏在左边 中部右侧作为主要功能页面的显示和操作区域 排课系统 主页面使用动态布局 能够自适应各种不同浏览器和不同分辨率使用环境 自适应调整窗 口大小以保证最佳的用户使用体验 用户在通过验证登陆以后就可以进入系统主页面 选 择不同的功能模块选项就可以进入相应功能模块 执行相应的操作 主页面设计如图 4 3 28 116112 10 周林 排课算法的研究与开发 2015 06 图 4 3 5 4 基础信息管理设计 排课基础信息管理模块的主要功能是管理排课相关的数据 对排课相关的数据执行删 除 添加和修改等操作 其中包括教室信息 班级信息 教师信息和课程信息 如图 4 3 其中教室信息管理模块主要是对高校现有的准备参与排课的教室资源管理 教室的主 要信息包括教室的编号 教室的名称 教室地点 教室类型以及教室容量 其中教室类型 根据教室的功能分为普通教室 相关体育场 计算机机房 以及物理和化学试验室等几类 根据需要排课的课程对教室类型的需求 在排课阶段 系统会根据相关信息自动选择合适 的教室进行排课 如图 4 4 精品文档 29欢迎下载 图 4 4 同样 对于教师信息也同样是系统在排课的时候需要用到的非常重要的基本信息 对 应于数据库中的数据内容也能够对数据进行相应的录入 增删和修改操作 本系统中教师 的数据信息包含了教师工号 编号 姓名 年龄 性别 职称 以及教师的任课信息 如 图 4 5 图 4 5 在所有排课基础信息中 课程信息是排课过程中所需要的最重要的基础数据之一 课 程信息中包含有课程编号 课时 课程类型 课程名称 教室类型等数据 其中课程类型 信主要是帮助排课算法实现软约束条件 比如较难课程应尽量安排在上午的上课时间 体 育课应该在其他课程拍完以后再排课并且应该尽量安排再下午的时间等等 课程信息中的 教室类型数据同教室信息管理模块中的教室类型是相互对应的 在进行排课的时候方便安 排符合课程要求的教室 课程信息管理窗口如图 4 6 30 116112 10 周林 排课算法的研究与开发 2015 06 图 4 6 5 5 排课设置管理模块设计 排课系统的排课信息基础管理模块主要有两个部分组成部分 两个部分分别是每个学 期的课程计划管理以及班级课程管理 任课教师管理 一般高校在教务工作安排上都会有 课程计划 针对每个专业 需要在什么阶段 学期 学习什么课程以及那些必修课程那些 选修课程 课程的开设和安排都是存在计划的 因为课程计划的存在 使得属于同一专业 的不同班级排课更加快速简便 当在班级数据库中录入同属于一个专业的班级时 则只需 要根据此班级所在的专业就立即得到这个班级在各个学期所需要开设的课程 如图 4 6 图 4 7 图 4 8 所示 图 4 6 精品文档 31欢迎下载 图 4 7 图 4 8 5 6 排课模块设计 排课模块是整个排课系统的核心功能模块 之前的 7 个小节详细介绍了如何具体的将 遗传算法应用到排课问题当中 这里简略展示自动排课模块的界面设计 排课模块的页面 设计如图 4 8 图 4 9 所示 32 116112 10 周林 排课算法的研究与开发 2015 06 图 4 8 图 4 9 5 7 系统管理模块设计 系统管理模块主要是管理整个系统的用账号 可以对系统用户进行增删操作以及信息 修改等 窗口设计如图 4 10 精品文档 33欢迎下载 图 4 10 5 8 本章小结 本章主要简要介绍了系统关系数据库的总体设计和数据库中数据表的具体设计 同时 粗略的介绍了系统各个模块的详细设计以及系统界面展示 第六章 总结与展望 6 1 总结 本文从教务排课问题出发 首先介绍了排课算法的研究背景 并简略介绍了三种在排 课应用中最常用的三种排课算法 贪心算法 回溯算法和遗传算法 比较了这三种算法 的显著优点和缺点 本文详细介绍了遗传算法