1、 1 本科毕业论文 (科研训练、毕业设计 ) 题 目：高校自动排课系统的研究与开发 姓 名： 学 院：软件学院 系： 专 业：软件工程 年 级： 学 号： 指导教师（校内）： 职称： 指导教师（校外）： 职称： 年 月 日 2 高校自动排课系统的研究与开发 摘要 本文讲述了排课问题 的提出，介绍了过去对该问题的研究情况。提出了一种 简单有效的数据结构和算法作为解决问题的途径。介绍 了 时间片的选择、优先级的计算、算法复杂性的降低等有 自我特色的改进。概述了系统采用的数据结构和算法流程，数据库中的表的设计，系统 的 模块的划分。重点描述录入子系统的设计与实现。 关键词 排课系统 时间片 优先级
2、算法 Jbuilder 高校自动排课系 统的研究与开发 1 目录 引言 . 2 第一章 绪论 . 2 第一节 问题的提出 . 2 第二节 计算机自动排课的发展历程 . 2 第三节 解决问题的途径 . 3 第四节 技术难点 . 3 第二章 系统开发环境 . 3 第一节 系统平台 . 3 第二节 数据库 . 3 第三节 开发工具 . 3 第三章 系统的建立与实现 . 4 第一节 数据结构 . 4 第二节 排课算法流程图 . 4 第三节 数据库设计 . 6 第四节 系统结构与模块划分 . 7 第四章 录入子系统的设计与实现 . 8 第一节 录入系统的组成： . 8 开课计划录入 . 8 教师信息录入
3、 . 9 班级信息录入 . 10 教室信息录入 . 10 第二节 资源录入的实现 . 11 数据库表的设置： . 11 调用数据库的方法 . 11 资料输入 . 11 时间表的设置 . 11 多媒体选项 . 12 课程安排 . 12 第五章 结论 . 12 致谢语 . 13 参考文献 ： . 13 高校自动排课系 统的研究与开发 2 引言 针对厦门大学以往采用的排课系统，排课结果不尽人意，需要人工反复修改等的不足，总结经验，认真分析了排课算法的数学模型，结合我校教育资源特点 ，开发这套独立可靠的排课管理系统，以实现开课计划、教师信息和教学资源信息电子化，排课管理流程化。 第一章 绪论 第一节
4、问题的提出 课表编排属于一类涉及多种因素的组合规划问题，他要保证在课程安排中教师、学生、教室等各种资源不产生冲突，即上下不同课程的两个以上班级在同一时间使用同一教室，或者同一教师在同一时间段安排多门课程等多种情况，并且要求满足教师的要求和教室资源等约束条件。这看起来是一简单的数学问题，但由于涉及到教师、学生和教室等多种因素，同时认为要求也比较多，因此往往令管理人员感到棘手。 第二节 计算机自动排课的发展历程 早在 60 年代国内外就开始了对计算机排课问题的探索。 63 年 C.C.Gotlieb 给出了课表编排问题的数学模型，使之成为数学家和计算机应用专家共同研究的问题。由于实际中遇到的各种难
5、题，并未能取得满意的成果。 70 年代中期，美国 S.Even 等人论证了课表问题是 NP完全问题（完全不确定多项 式） ，宣布了这一时空组合问题的学术地位 和难度 ，使得人们对该问题的求解失去了信心。 80 年代计算机的普及发展，使该课题又出现了勃勃生机。排课问题虽然是数学上的时间与空间组合问题，而排课过程确 是 人的主观因素作 用下的人文决策过程。要实现用计算机排课，如果试图从纯粹数学的角度建立模型，研究设计一种计算机解法，无疑将让这个问题的解决陷入困境。近 40 年来，人们对课表问题的计算机解法做了许多尝试，其中课表编排的整数规划模型将问题归结为求一组 0 1 变量的解，但是计算量非常大
6、。解决 0 1 线性优化问题的分支定界技术却只适用于规模较小的课程编排， Mihoc 和 Balas 将课表公式化为一个优化问题， Krawczk 则提出一个线性编程的方法。 Junginger 将课表问题 转 化 为三维运输问题，而 Tripathy 则把课表问题视作整数线性编程 问题并提出了大量课表的数学模型。 进入 90 年代以后，国外对课表问题的研究仍然十分活跃。比较有代表性的有印度的Vastapur 大学管理学院的 Arabinda Tripathy、加拿大的 Montreal 大学的 Jean Aubin 和 Jacques Ferland 等。目前，解决课表问题的方法有：模拟手工
7、排课，图论方法，拉格朗日松弛法，二次分配型法等多种方法。由于课表约束复杂，用数学方法进行问题描述往往导致问题规模剧烈增大，这已经成为应用数学编程解决课表问题的巨大障碍。 高校自动排课系 统的研究与开发 3 第三节 解决问题的途径 研究表明，比较 可行与容易操作的方法是：将问题转化为在现有资源的约束下，得到一个相对最佳的课程与其它各种资源的匹配，即得到一个相对最合理的课程表的问题。约束条件可分为绝对约束条件和相对约束条件。绝对约束条件是必须满足的，否则课程表不能使用。相对约束条件满足得越好 ， 课程表越能符合用户的要求 。 约束条件的取舍原则：在一个可行的系统中绝对约束条件必须得到满足，不存在取
8、舍问题。而对相对约束条件就有取舍问题。取舍的原则为突出在教学中的主要因素，优先解决主要矛盾，尽量满足师生的合理要求。 第四节 技术难点 1 构造适合的数据结构 2 制 定合理的算法流程 3 设计数据库 第二章 系统开发环境 第一节 系统平台 Windows2000 较前代的微软操作系统，增加了许多新特性及其功能。比如智能镜像、终端服务、分布式文件系统、磁盘定额、 DNS 增强以及活动目录等等。 第二节 数据库 Microsoft Access 是当今最流行的关系数据库管理系统之一，基本的核心是 Microsoft Jet 数据库引擎。它以操作方便、简单易学以及和 Microsoft Offic
9、e 的完美结合而著称于世。同时， Access 又能满足小型企业客户 /服务器解决方案 的要求来组建客户 /服务器的数据库应用系统，是一种功能较完备的系统，几乎涵盖了数据库领域的所有技术和内容。 第三节 开发工具 JBuilder 是一款非常优秀的 Java 可视化开发环境，它是由 Borland 公司推出的一种基于组件技术的特点主要有以下几个方面：简单、面向对象、分布式、解析执行、健壮、安全、可移植性、可视化 Java 开发工具，并适用于各个层次上的 Java 程序开发，其中包括开发JavaBeans 组件、编写 XML 文档、开发数据库应用程序以及实现网络链接和多媒体技术等等。 高校自动排
10、课系 统的研究与开发 4 JBulider 的 组件和类库资源非常丰富，并为不同类型的应用程序提供了开发模板。 JBuilder 的使用和维护也很方便。整个开发界面统一、明晰，功能向导丰富、实用，同时 JBuilder 还提供了丰富的帮助文件，可以帮助解答开发过程中的疑难问题。 数据访问是通过 JDBC/ODBC 桥接器来实现连接的。 JDBC 是 Java 的核心 API，为与 SQL 兼容的数据库提供了一个标准的接口集合。 JDBC 不仅提供了一些相当低层的接口方法来存取数据库，同时也在高层提供了功能强大的对象来处理数据库。 在 Java 开发中，有多种的开发工具可供选择， 如 JCrea
11、tor、 Ultraedit 等。 JCreator 应该来说是一款比较突出的针对于 Java 的编程开发工具，在编译源代码，执行程序，以及对工程及源代码的管理上，有自己突出的优点。它能够以特定的颜色支分辩源代码中，哪些是 Java 类方法，预保留字，哪些是作者的注释内容等等。基于以上的优点，所以我们选择以 JCreator 作为开发的辅助工具。 同时，它也有自身的不足。它没有可供大家选择的各种组件，所以在开发过程中，尤其是在开发用户界面的时候，使用不够方便，不如 JBuilder。 Ultraedit 在对 Java 源代码的分析有自己的独到之处。可能是过于广泛，对太多的语言兼容，导致其不是
12、一个成熟的 Java 编程工具。 基于以上对各常用的开发工具的对比，我们首选以 JBuilder 作为我们的开发工具，在必要的时候选择 JCeator 作为辅助使用。 第三章 系统的建立与实现 第一节 数据结构 通常情况下一天上午可安排 4 节课，下午可以安排 2 节课，晚上可以安排 2 节课。将两节课程看作一个时间片，则一天有 4 个时间片，一周 5 天有 20 个时间片。用一个长度为 20 的字符串来表示各种资源的当前时间片的占用情况。 T 表示空闲， F 表示占用。 当二十 个时间片全为空闲的时候，则记二十个时间片为“ TTTTTTTTTTTTTTTTTTTT”。当有某个时间段被选以后，
13、将相对应的那个时间段的“ T”改为“ F”。 算法的关键就在这二十个时间片的对比。 对修课班、教室和教师都设置了一个这样的时间占用标记。通过对该标记的运算得出共同的剩余时间。从而在剩余时间中按照允许的时间模式得出排课时间。 (详细描述见于同组 陈沫、范丽君 同学的论文 ) 第二节 排课算法流程图 (详细描述见于同组 陈沫、范丽君 同学的论文 ) 高校自动排课系 统的研究与开发 5 开 始 从开课计划表中获取课程信息 分别考察教师表、修课班表 ，找出共同的剩余时间 考察教室表匹配一个教室 从教师、修课班、当前教室的共同剩余时间中根据时间模式和周学时分配时间 分配成功？ 写课程表记录并修改各表资源
14、占用标记 排 完？ 结 束 发换教室信息 下一门课 程 否 否 高校自动排课系 统的研究与开发 6 第三节 数据库设计 (详细描述见于同组郭蔡伟、林 爱娟同学的论文 ) 主键： KCBH（课程编号） 字段名 数据类型 长度 说明 KCBH 文本 课程编号 JSBH 文本 教师编号 XKB1 文本 修课班 XKB2 文本 修课班 XKB3 文本 修课班 RS 数字 整型 最大班级人数 KCMC 文本 课程名称 LLXS 数字 整型 理论学时 SJXS 数字 整型 实践学时 XF 数字 整型 学分 KCQZ 文本 课程权重 MZCS 数字 整型 每周上课次数 DMT 数字 整型 是否需要多媒体 P
15、KBJ 文本 课程是否安排的标记 表 开课计划表 教室表：用来存放学校所有可用教室的信息，通过教室编号（ JSBH）与开课计划表、课程表关联。 主键： JSBH（教室编号） 字段名 数据类型 长度 说明 JSBH 文本 教师编号 JSMC 文本 教室名称 RS 数字 整型 容纳人数 DMTBJ 数字 整型 多媒体标记 ZYBJ 文本 教室占用标记 表 教室表 教师表：存放全校教师基本情况，通过教师编号（）与开课计划表、课程表关联。 主键： TBH(教师编号 ) 字段名 数据类型 长度 说明 TBH 文本 4 教师编号 TXM 文本 8 教师姓名 WORK 文本 20 职称 DEPARTMENT
16、 文本 20 院系 SJBJ 文本 20 教师时间标记 表 教师表 高校自动排课系 统的研究与开发 7 修课班表：用来存放全校的班级信息，通过修课班编号与开课计划表、课程表表关联。 主键： XKBBH(修课班编号 ) 字段名 数据类型 长度 说明 XKBBH 文本 6 修课班编号 XKBMC 文本 10 修课班名称 XKBRS 数字 整型 人数 DEPARTMENT 文本 20 院系 SJXZ 文本 20 时间限制 表 修课班表 课程表：用来存放排课后的结果信息，在系统中为各主要数据的关联对象。 主键： XKBBH（修课班编号）、 SJ（上课时间） 字段名 数据类型 长度 说明 XKB 文本
17、6 修课班编号 SJ 文本 20 上课时间 KCBH 文本 6 课程编号 KCMC 文本 20 课程名称 LLXS 数字 整型 理论学时 SJXS 数字 整型 实践学时 XF 数字 整型 学分 XKBMC 文本 20 修课班名称 TBH 文本 4 教师编号 TXM 文本 8 教师姓名 JSBH 文本 6 教室编号 JSMC 文本 10 教室名称 表 课程表 第四节 系统结构与模块划分 在对当前有关学校需求分析的基础之上，我们小组确立了系统的总体结构。本系统包含四个子系统，他们分别为：录入子系统、自动排课子系统、查询子系统、资料维护子系统。系统的总体结构设计如下图所示： 高校自动排课系 统的研究
18、与开发 8 图 系统总体结构 录入子系统：录入数据库中各个表的基础数据信息，包括编排课表所需要的各种信息。（详细描述见于本论文第四章） 自动排课子系 统：根据录入的各项信息，分析各种数据，根据所设计的算法以及一些限制性条件编排出课程表。并可显示排课结果。（详细描述见于同组 陈沫、范丽君 同学的论文） 查询子系统：根据用户输入的关键字，完成用户提出的各种查询，并实现数据的添加、删除、修改的功能。并可以以图形化界面显示特定的排课结果。（详细描述见于同组高泉盛、吕振文同学的论文 手动调课子系统：根据教师或修课班级的需要，手动调整上课时间、地点。（详细描述见于 同组郭蔡伟、林爱娟同学的论文 ） 第四章 录入子系统的设计与实现 第一节 录入 系统的组成： 开课计划录 入 主要用于录入打算开课的课程信息。在这个窗口中要求填写的内容包括：课程编号、课程名称、理论学时、实践学时、每周课次、教师编号、修课班编号（可设置为 1-3 个班同时学生 教师 管理员 数据库 自动排课 子系统 录入子系统 手动调课 子系统 查询子系统 数据库 用户界面
