高校排课系统设计含需求分析数据库算法和部分代码毕业论文目录1 绪论 01.1 课题背景和意义 01.2 排课问题发展现状 01.3 排课算法简介 (1)1.3.1 回溯搜索算法 (1)1.3.2 遗传算法 (1)1.3.3 贪心算法 (2)1.3.4 模拟退火算法 (2)1.4 课题主要内容 (2)1.4.1 软件设计的主要功能 (2)1.4.2 论文结构说明 (3)2 开发平台 (4)2.1 基于平台开发概述 (4)2.1.1 概述 (4)2.1.2 的优点 (4)2.1.3 的发展前景 (6)2.2 概述 (6)3 排课系统分析 (9)3.1 排课问题分析 (9)3.1.1 排课基本原则 (9)3.1.2 排课资源分析 (9)3.1.3 排课冲突分析 (10)3.2 系统分析 (10)3.2.1 需求分析 (10)3.2.2 系统功能分析 (11)4 数据库设计 (13)4.1 数据库概念结构设计 (13)4.2 数据库逻辑结构设计 (13)4.3 数据库物理结构设计 (14)5 排课系统算法及功能的实现 (17)5.1 回溯算法简介 (17)5.1.1 回溯算法的基本思想 (17)5.1.2 回溯算法的求解步骤 (17)5.1.3 回溯算法在排课系统上的特点 (18)5.2 排课系统算法分析 (18)5.3 排课过程 (18)5.3.1 自动排课算法流程 (18)5.3.2 自动排课程序 (20)5.4 功能的实现 (23)5.4.1 用户登录 (23)5.4.2 查询功能设计 (26)5.4.3 排课管理界面 (32)6 排课系统测试 (35)6.1 系统测试数据 (35)6.2 系统测试结果 (35)结论 (37)致谢 (38)参考文献 (39)附录A 英文原文 (40)附录B 中文翻译 (50)1 绪论1.1 课题背景和意义每个新学期开始，对于学校教务科来说首要而急需完成的任务是：如何合理而高效的排课。

其本质是将课程、教师和学生在合适的时间段内分配到合适的教室中。

但由于涉及到的问题较多，同时学校扩招，学生和课程数量比以往大大增加，教室资源明显不足，在这种情况下排课很难在同时兼顾多重条件限制的情况下用人工方式排出令教师和学生都满意的课表。

虽然排课问题很早以前就成为众多科研人员和软件公司的研究课题，但是真正投入使用的排课软件却很少。

原因是多方面的，其中算法的选择是最关键的一个问题，S.Even等人在1975年的研究中证明了排课问题是一个NP-Complete问题，即若是用“穷举法”之外的算法找出最佳解是不可能的。

然而由于穷举法成本太高，时间太长，根本无法在计算机上实现。

如果假设一个星期有n个时段可排课，有m位教师需要参与排课，平均每位教师一个星期上k节课，在不考虑其他限制情况下，能够推出的可能组合就有n*m*k种，如此高的复杂度是目前计算机所无法承受的。

这就促使我们必须采用一些以计算机为辅助的手段来帮助。

1.2 排课问题发展现状国外对于课表问题的研究始于20世纪50年代。

1963年Gotlieb在他的论文中提出了课表问题的数学模型，并用匈牙利算法解决了三维线性运输问题[1]。

直到1976年S.Even、Tim B.Cooper等人在他们的论文中证明了排课问题是一个NP完全问题[2]，人们才将注意力更多地转向课表编排实用算法的探索与研究。

近几十年，国外对于排课算法的研究依然很活跃，Ferland等人把排课问题化成整数规划来解决[3]，但计算量很大，其仅仅适用于规模很小的课表编排，对于大规模复杂的排课情况，至今没有一个切实可行的算法。

还有人用图论的染色体问题来解决课表问题，但是遗憾的是染色体问题本身也是NP完全问题。

除此之外，还有印度Vastapur大学管理学院Arabinda Tripathy的拉格朗日松弛法[4]等求解算法。

我国对于排课问题的研究较晚，始于上个世纪80年代初期。

1984年林漳希和林尧瑞发表了在排课问题上的实验性研究成果《人工智能技术在课表编排中的应用》[5]。

许多高校也进行了一些排课系统软件的研究，具有代表性的有南京工学院的UTSS（A University Timetable Scheduling System）系统[6]、清华大学的TISER（Timetable SchedulER）系统、大连理工大学的智能教学组织管理及课程调度系统[7]、浙江大学的正方现代教学管理信息系统等。

1.3 排课算法简介时间表问题(TTP)是典型的组合优化和不确定性调度问题，该问题已经被证明是NP 完全问题，广泛应用于学校课程安排、会议日程安排、体育比赛和航班时刻表的制定等。

由于问题的复杂性，一般只能得到较佳解算法。

常见的算法有：1.3.1 回溯搜索算法回溯算法(Backtracking Algorithm)也叫试探法，它是一种系统地搜索问题的解的方法。

它的基本思想是：从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。

这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”。

基于回溯法解决排课问题，在使用初期，没有足够的信息可能会出现死锁，引起回溯失败。

失败的原因一般为：教室资源不足；安排课程过多或约束条件过于苛刻。

1.3.2 遗传算法遗传算法(Genetic Algorithm)是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。

其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则[8]。

近几十年，很多人使用遗传算法来解决时间表问题，虽然取得了一定成果，但是仍有不足。

其主要表现在，只能在排课模型较简单、限制条件有限情况下求解，且速度较慢，系统开销较大。

1.3.3 贪心算法贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解[9]。

在贪心算法中较为有名的算法是Dijkstra算法。

它作为路由算法用来寻求两个节点间的最短路径。

Dijkstra算法的思想是：假若G有n个顶点，于是我们总共需要求出n-1条最短路径，求解的方法是：初试，写出V0(始顶点)到各顶点(终顶点)的路径长度，或有路径，则令路径的长度为边上的权值；或无路经，则令为∞。

再按长度的递增顺序生成每条最短路径。

事实上生成最短路径的过程就是不断地在始顶点V何终顶点W间加入中间点的过程，因为在每生成了一条最短路径后，就有一个该路径的终顶点U，那么那些还未生成最短路径的路径就会由于经过U而比原来的路径短，于是就让它经过U[10]。

1.3.4 模拟退火算法模拟退火(Simulated Annealing)算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态[11]，最后在常温时达到基态，内能减为最小。

模拟退火算法可以在较大的解空间内用较短的时间找到最优解，用其解决编排课程表这样的组合优化问题是很有效的。

但是模拟退火算法受收敛速度慢，执行时间长，算法性能与初始值有关及参数敏感等缺点所限。

1.4 课题主要内容1.4.1 软件设计的主要功能在论文阶段，对排课系统进行系统分析、数据库设计、系统设计和界面设计，最后对排课系统进行测试。

这个课题设计用到的开发平台是visual studio 2010，在的特定环境下实现的。

软件的内容主要包括排课管理、信息查询二大部分。

通过整合，系统的基本模块为：（1）自动排课模块:该模块是系统的核心模块，通过对系统管理员录入的基本信息，通过加权优先级自动生成排课成功的课表。

（2）手动调整模块:由于某些特殊因素，可能存在排课失败或临时调整的情况，手动调整可以在不影响硬性约束条件下满足这个需求。

（3）信息查询模块:包括对特定班级课表的浏览、特定教师课表的浏览操作。

另外系统还设置了用户管理模块归并在系统中，用户权限分为三类：学生用户、教师用户和管理员用户。

其中学生用户只有浏览课表的权限；教师用户只有查找自己课程时间的权限；管理员用户则拥有排课，修改，查找单独课表的权限。

1.4.2 论文结构说明论文整体分为六大章，从基本的课题题目的理解到设计系统的后期测试，层层递进。

第一章，也就是绪论。

主要介绍的是“基于回溯算法的高校排课系统的设计与实现”这个课题的背景以及发展前景。

同时还介绍了回溯算法与其他类似算法的概念。

第二章，主要介绍了本系统的开发使用平台ASP,NET开发平台。

介绍了平台的概念、优点以及数据库的介绍。

第三章，主要是对课题的进一步分析。

对排课系统进行排课原则分析、排课资源分析、排课冲突分析。

也对整个系统的需求分析进行了简单的阐述。

第四章，是系统数据构造的主要章节。

这一章节具体的写出了数据库的概念结构、逻辑结构和物理结构，完整的看出本系统所需要的各种数据结构，也更加直观的阐明了系统数据的设计思想与方法。

第五章，是系统实现与功能介绍的主要章节。

介绍了如何使用回溯算法实现排课系统的，以及排课系统的其他功能，如：学生如何查看课程表，教师如何查看课程安排等。

第六章，说明了系统的测试数据和测试过程。

以上就是论文的主要内容，当然论文的内容还不够全面，还需要完善。

2 开发平台2.1 基于平台开发概述2.1.1 概述是微软推出的ASP的下一代Web开发技术，作为一种网络应用的商业开发模式，涉及许多网络应用方面的知识。

同时，作为 Framework平台的一部分，提供了一种基于组件的、可扩展且易于使用的方式来构建、部署及运行面向任意浏览器和移动设备的Web应用程序。

是Web开发领域的最前沿的技术，是其中的佼佼者，在构建基于HTTP协议进行传输的分布式应用程序方面，它是目前最先进，特征最丰富、功能最强大的平台。

2.1.2 的优点1、与浏览器无关是一个与浏览器无关的程序设计框架，利用它编写的应用程序可以与最新版本的Internet Explorer、Netscape Navigator等常用的浏览器兼容。

2、将业务逻辑代码与显示逻辑分开在中引入了“代码隐藏”这一新概念，通过在单独的文件中编写表示应用的业务逻辑代码，使其与HTML编写的显示逻辑分开，从而更好的理解和维护应用程序，并使得程序员可以独立于设计人员工作。