高校自动排课系统的研究与开发-毕业论文

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