排课系统设计毕业论文.pdf
《排课系统设计毕业论文.pdf》由会员分享,可在线阅读,更多相关《排课系统设计毕业论文.pdf(15页珍藏版)》请在三一文库上搜索。
1、本科毕业论文(设计) 题目:排课算法的研究与开发 姓名:周林学号: 20111001954 所在 院 系 :信工学院专业:信息工程 指导教师:张发勇职称:副教授 评 阅 人:职称: 2015 年06 月 学位论文原创性声明 本人郑重声明:所呈交的论文是本人在导师的指导下独立进行研究所取得 的研究成果。除了文中特别加以标注引用的内容外,本论文不包含任何其他个 人或集体已经发表或撰写的成果作品。本人完全意识到本声明的法律后果由本 人承担。 作者签名:年月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保障、使用学位论文的规定,同意学校 保留并向有关学位论文管理部门或机构送交论文的复印件和
2、电子版,允许论文 被查阅和借阅。本人授权省级优秀学士学位论文评选机构将本学位论文的全部 或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文。 本学位论文属于 1保密 ,在 _年解密后适用本授权书。 2不保密 。 (请在以上相应方框内打“” ) 作者签名:年月日 导师签名:年月日 排课算法的研究与开发 本科生:周林指导教师:张发勇 摘要 作为一个学生,无论是在小学中学还是大学,课表都是我们在学校里接触最多的。然 而,我们很少会去关注课表是怎么排出来的,尤其是在大学以前似乎课表并不复杂。然后, 到了大学里,看似简单的课表却引起了我们的注意。大学里的课程往往具
3、有很强的随机性 和流动性,学生个人的课程有一定的共性但是却不完全相同尤其是课程往往没有固定的教 室。而是根据自己的选课情况来安排上课时间和地点,而且我们也发现大学中教室的资源 往往非常紧张。 这样一来排课问题就构成了一个多类资源的优化组合问题。S.Even 等人在 1975 年将排课问题论证为NP 完全问题。这类问题往往没有唯一解,而只能在有限的要求 范围内求得相比较而言更合理的解。那么,如何在有限的教室、老师资源以及各种硬性软 性要求给出一个最优解就是排课算法的核心要求。本课题着重与在优化现有的排课算法, 尤其是遗传算法,针对其在排课应用中的不足进行优化从而能够得出更为高效、合理的排 课算法
4、解决高校排课问题。 关键词: JSP、遗传算法、排课系统 Scheduling Algorithm Research and Development Bachelor Candidat e:Zhou LinSupervisor: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
5、 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 t
6、o 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 demonstrat
7、e 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 r
8、esources, 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 algorit
9、hms to solve problems. Keywords: JSP ;genetic algorithm ;Scheduling System 目录 第一章绪论 . 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
10、特点 . 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
11、选择 . . 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基础信息管理
12、设计. 28 5.5排课设置管理模块设计. 30 5.6排课模块设计. 31 5.7系统管理模块设计. 32 5.8本章小结. 33 第六章总结与展望 33 6.1 总结 . . 33 6.2 展望 . . 33 致谢 . 35 参考文献. 36 2015.06 中国地质大学(武汉)学士学位论文1 第一章绪论 1.1 排课算法研究背景 最初在采用计算机自动排课以前,高等院校只能采用人工排课的方式。人工排课只能 依靠教务处的工作人员手动的安排整个学校教育教学工作。这种手工人力的排课方式有非 常多的缺点。 首先最显著的缺点就是排课效率过于低下,其次课表排好以后很难修改,不便 于调整。 对于实际使用
13、过程中出现的特殊情况如临时调课等状况不能很好的应对。因此,当 学生人数越来越多, 达到数万甚至更多,教师人数达到数百数千,要为这成百上千的学生和 教师安排出科学合理的课程表,几乎是不可能的任务。就算能够完成,但也往往需要花费 很大的人力物力,工作量巨大。并且即使排出课程表也不够灵活,很难进行调整。 随着高等教育的不断发展,不管是高等院校的在校学生人数还是教职工人数都在不断 地增加, 课程安排复杂度也不断提高。着这种情况下, 人工排课的缺点与不足就显得更加突 出,手动排课的方式已经无法在满足当前排课问题的需求。同时,随着计算机技术的快速发 展,计算机技术在各个领域的应用也越累越广泛。人们很自然地
14、就将计算机技术应用到这 一领域中。显而易见,使用计算机技术进行排课,可以排课缩短排课时间、节省人力资 源、并且有比较高的排课质量,可以迅速地得出满足各种约束要求的可行排课结果。 1.2 常用的排课算法对比 1.2.1 贪心算法 贪心法 (greedy method)主要是将分级处理方法进行改进,着眼于局部,然后逐步产生 最优解。贪心算法从问题的一个初始解出发,在特点的原则下做出一系列的选择( 一旦做出 选择,就不再进行修改),也就是选择当前状态下的最优选择,从而渐渐逼近原定的理想目 标。 在排课问题中,贪心算法就是从某一个初始状态开始,根据给定的策略向安排好所有 待排课程这一目标逐步前进。贪心
15、算法每一步都需要进行判别,在即将进行的下一步中能 否得到可行解的一个解元素。如果可以则持续进行,依然根据贪心策略想目标推进。当算 法不能再找到符合要求的解时,算法停止。最终可以得到可行解。 贪心算法的优势在于时间复杂度较小,能用较少的执行步数得到相应的解。而其最大的 不足就是解不够合理,虽然每一步都能做到局部最优化,但是总体得到的结果却不一定是整 体最优解。 为了能够尽可能的规避贪心算法的不足,在算法最后能够得到的解更科学合理的 2 116112-10 周林:排课算法的研究与开发2015.06 整体较优解。为此,可以在算法中采用最优化算法( 比如动态规划等) 。 1.2.2 回溯算法 回溯算法
16、也被叫做试探算法。可以认为它是对深度优先算法进行修改和扩充的孙发。 回溯算法根据原定的优先条件进行深度优先搜索。但当搜索进行到某一步发现不能满足条 件时,则退回到前一步重新进行选择。其中能够满足返回条件的状态点被称为回溯点。实 际运用到排课算法中,优先条件就是排课问题中的制约条件,如果不能够满足制约条件, 那么算法做出的选择就不是最优选择。当在一个状态点遍历了所有可能的选择之后不存在 满足条件的选择,那么这个状态点就是回溯点。 回溯法所具有的一个非常重要的特点就是在搜索的过程中会产生解空间。在搜索算法 执行的任何时候,存储从开始到当前的搜索路径。所以,回溯算法的空间需求为一个常 数,也就是从开
17、始节点直到最远节点的路径长度。这个特点非常重要,使用回溯算法的解 所需要的空间大小往往是最长路径长度的指数倍数。因此,使用回溯算法排课往往过于消 耗存储空间, 特别是数据量大的时候代价太大。回溯算法还有一个缺点就是时间复杂度非常 大。 1.2.3 遗传算法 遗传算法(英文全称 Genetic Algorithm, 简记为 GA ) 最早是由美国密歇根大学J. Holland 教授于 1975 年提出,并且在之后出版了非常具有影响历的Adaptation in Natural and Artificial Systems 。遗传算法基于自然进化过程中的自然选择机制和生物遗传机制,由生物 的自然进
18、化过程抽象而来。遗传算法是一种全局优化策略适用于寻找最优解的最优规划以及 多目标规划问题。 遗传算法能够有效避免陷入局部最优而能够考虑到各个因素从而得到全体 最优解或次于全体最优解的次优解。 有一个故事可以帮助我们理解遗传算法:从前, 有一大群袋鼠, 它们被莫名其妙的零散 地遗弃于喜马拉雅山脉,于是只好在那里艰苦的生活。这些袋鼠并不知道它们的任务是寻找 珠穆朗玛峰。 海拔低的地方弥漫着一种无色无味的毒气,海拔越高毒气越稀薄。可是可怜的 袋鼠们对此全然不觉,还是习惯于活蹦乱跳。于是,不断有袋鼠死于海拔较低的地方,而越 是在海拔高的袋鼠越是能活得更久,也越有机会生儿育女。就这样经过许多年,这些袋鼠
19、们 竟然都不自觉地聚拢到了一个个的山峰上,可是在所有的袋鼠中,只有聚拢到珠穆朗玛峰的 袋鼠完成了任务。 遗传算法的实现过程实际上就像自然界的进化过程那样。首先寻找一种对问题潜在解进 行“数字化”编码的方案(建立表现型和基因型的映射关系)。然后用随机数初始化一个种 群,种群里面的个体就是这些数字化的编码。接下来,通过适当的解码过程之后,用适应性 函数对每一个基因个体作一次适应度评估,用选择函数按照某种规定择优选择。让个体基因 交叉变异, 然后产生子代。 遗传算法并不保证你能获得问题的最优解,但是使用遗传算法的 最大优点在于你不必去了解和操心如何去“找”最优解,而只要简单的“否定”一些表现 201
20、5.06 中国地质大学(武汉)学士学位论文3 不好的个体就行了,这是遗传算法的精粹。 1.3 课题目标以及意义 1.3.1 课题目标 本课题着重对遗传算法进行研究,将传统的遗传算法进行改进,尽量发挥遗传算法的 优势并改善固有缺陷然后应用到排课算法中。通过计算机来进行自动排课,抽象出问题中 所存在的要素,结合数学表达式来表达一系列的约束条件,并且能够依据课表形式和排课 过程中普遍存在的规律,可以有效缩减排课问题的空间搜索范围,从而快速高效的进行排 课。 1.3.2 课题意义 教务排课管理系统是高校教务系统中的一项重要组成部分,排课系统否科学高效得排 出高质量的课程表将很大程度上会影响高校的正常教
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 系统 设计 毕业论文
链接地址:https://www.31doc.com/p-5000212.html