《网络工程专业精品毕业论文基于遗传算法的高校排课系统设计实现》由会员分享，可在线阅读，更多相关《网络工程专业精品毕业论文基于遗传算法的高校排课系统设计实现（44页珍藏版）》请在金锄头文库上搜索。
1、目 录1.引言.1 2.问题分析.1 2.1 业务需求分析.1 2.2 数据需求分析2 2.2.1 时间问题.3 2.2.2 教师和课程问题4 2.2.3 教室的问题.4 2.3 功能需求分析.4 2.3.1 院管理模块.5 2.3.2 校管理模块.5 2.3.3 自动排课模块.5 2.4 排课过程的约束条件.6 3.数据模型7 3.1 问题陈述7 3.2 数据流程图8 4.问题解决.10 4.1 数据库设计10 4.1.1 概念模型设计10 4.1.2 逻辑模型设计12 4.1.3 数据库的物理设计16 4.2 自动排课系统的设计.16 4.2.1 遗传算法的思想.16 4.2.2 构建基因
2、编码和染色体.17 4.2.3 初始化种群20 4.2.4 冲突检测及排除21 4.2.5 构造适应度函数22 4.2.6 遗传算子.24 4.2.7 设置控制参数.26 4.3 教室位置填充设计.27 4.4 功能模块的设计.28 4.4.1 登录模块28 4.4.2 主界面模块.29 4.4.3 学院管理模块.30 4.4.4 校管理模块.30 4.4.5 查询模块.31 4.4.6 排课模块31 5.系统运行结果及分析.31 5.1 结果.31 5.2 分析.32 6.总结及后续工作.35 参考文献：35摘摘 要要排课问题是当今各大高校在教学资源管理、最优化配置上面临的主要问题之一。本文
3、将遗传算法应用于排课问题的求解中,采用基于轮盘赌算法的选择操作方法和优化的个体适应度计算方法，满足了排课过程中多部分软硬约束条件，实现了各种类型课程的排课。针对之前研究者未解决的运行时间太长问题，本文提出了一套基于二维编码的改进的编码方法和教室位置填充方法，精简了染色体信息量而大大缩短了系统的运行时间。此外，在系统设计中，运用了基于容器的容器编程技术，实现了不定数据量的便捷处理。 。关关键词键词： ：遗传算法；排课；教室安排；AbstractTimetabling problem is one of the major problem,which todays universities fac
4、e in teaching resource management and the optimized configuration.This article,where genetic algo-rithm will was applied to solve problems,uses the course choice operation method based on rou-lette algorithm and the optimization calculation method of individual fitness, satisfying most ofthe soft an
5、d hard constraint conditions int the timetabling process and achieving the timetablation of various types of courses. According to the problem that running time is too long,which the res-earchers didnt resolved well before,this paper puts forward a improved method based on two-dimensional coding and
6、 the classroom filled method, simplifying the chromosome informationand greatly shortening the syetem operation time. In addition, in the system design, we use the programming method of container based on container , realizing the convenient and fast processing of uncertain quantity data. Key word:
7、Genetic Algorithm; Timetabling; Classroom Arrangement;11.1.引言引言随着高校招生逐年扩张，大学课程向着广度和深度发展，高校的教师、教室等一些资源越发显得紧张，不管是在时间还是效率方面，用人工排课已不能够解决现有的问题。排课是高校日常教学工作和其他活动的基础，是教师和学生正常科学工作学习的依据。所以计算法自动排课已成为一个重要的研究课题1。国内学者在自动排课系统方面曾做过一些研究，如用到到退火算法、回溯算法、遗传算法，但运行结果尚有待改进的地方，排课效果不尽人意5。我们认为，问题不尽在数学建模上，还与问题的处理方式有关。将遗传算法应用于排
8、课问题中，首先，初始化课表种群，其次，检测初试种群中的冲突，然后，对种群做选择，杂交，突变操作，一直迭代到具体指定的代数，最后就会得到较优解。文1中提到编码时染色体上基因片存储信息大小为 11 字节，而本文的编码方式一个基因片只用了 6 字节，轻装运行，经试验得出，速度更快。还有,文1介绍把教室与时间等信息共同处理的思路，这可能会产生空间上的冲突，而本文提出将教室分离出以单独处理，就完全解决了空间上的冲突问题。本文根据高校开课的具体情况，采用优化的编码方案，满足排课过程中的一些硬性和软性约束因素，利用遗传算法对课表进行了优化，从而得到了最终的无冲突、更人性的排课方案。22.2.问题分析问题分析
9、2 2.1.1 业务需求业务需求分析分析排课工作是一项十分繁重而复杂的工作，就以一般高校而言，它涉及到几千多门课程进行合理的组织安排，而所使用的教室资源却在学生规模每年都在增加的趋势下越发显得紧张了。排课的整个过程中充满了矛盾运动，其中包括上课班级、所开课程、任课教师、上课时间、上课地点这 5 个方面在排列组合中发生的冲突和矛盾现象。课程门类多、班级多、教师少、教室少、教师连续上课的要求、班级连续上课的时间合理安排是排课时发生冲突和矛盾的主要因素，而班级多、教室少则是矛盾的重要方面。课程表则是解决这些矛盾的舞台，是提高教学管理水平、组织师生进行有序教学的规范之一，对有效地提高教育教学质量有重要
10、作用。如果课程表编排得不合理、不科学，将影响课堂教学的效率和教学的整体效果。要想编排好学校的课程表，需要综合考虑学校的教师、教室、学生、班级、时间等多方面因素，反复调整，避免冲突。分析一般高校的排课流程，其过程将如下，下面将排课整个流程作个介绍:(1)各学院从教学计划中导入开课任务书，让各学院安排好教师及教师的各种相关要求，比如班级、教室类型、时间类型等。同时做好教学楼、教室和时间基础数据的输入（已存在数据库中） 。这一时间段主要做好班级、课程、教师的协调。(2)把各个学院开课任务书集合为学校开课任务书，同时规划好学院上课所在的教学楼形成位置表，以减少学生的跑动范围。(3)系统会根据校开课任务
11、书自动排课。这一过程主要完成班级、课程、教师及上课时间的安排。(4)把上一步排出的结果与位置表结合，就完成了课表的安排，中间整个过程都要解决冲突问题。(5)课表确定后，进行课表的查询。3图 2-1 排课流程图Chart 2-1 timetabling flow chart2 2.2.2 数据需求分析数据需求分析排课涉及的相关数据主要包括:时间、班级、课程、教室（空间） 、教师等 5 个要素。开始算法设计的基础是对这些数据之间的问题的透彻分析和适当的处理。2 2.2.1.2.1 时间问题时间问题在本文中考虑的是周课表，通过对全国部分高校做的调查，综合分析了其中大部分高校的教学特点，我们在此做出了
12、一个较大众化的且较合理的时间划分模式。设定周一至周五，共五天上课，一天有十节课，上课方式都为一大节包括 2 个相邻的小节，不能在上、下午之间跨时段。把每天用于上课的时间划分为 5 个时间片，根据学院开课的实际情况，一般每学时是 45 分钟，为 1 小节课，每 2 小节课合为一大节课，故把每 2 小节课时间定为一个时间片，一天划分为 5 个时间片:4(1)上午 1, 2 节课 8:10-9:50;(2)上午 3, 4 节课 10:10-11:50;(3)下午 5, 6 节课 2: 30-4:10;(4)下午 7, 8 节课 4:20-5:50;(5)晚上 9, 10 节课 7:30-9:10;这
13、样，每周 5 天涉及 25 个时间片。用 Tl, T2,T25 表示，其中TI, T2, T3, T4, T5 为星期一的 5 个时间片，依次类推。则排课问题类似于填充 55 的周时间片安排表。 表 2-1 周时间片分布表Table2-1 the management table of the week time slip 周一周二周三周四周五T1T6T11T16T21T2T7T12T17T22T3T8T13T18T23T4T9T14T19T24T5T10T15T20T25根据时间片编号，可进一步转化为 125 的表格。全校有 N 个教学班级，则周课表为:以 25 个时间片为列，形成一维的时间
14、序列，每个班级为行组成的一个二维数据表。我们在此系统的排课都是按一个大节开设的，符合按 25 个时间片划分的设计，但确有少量的课程的周学时数为单数，如“3 学时”或“5 学时” ，在此仍按“4 学时”或“6 学时”进行编排，虽然这会浪费一小节课程。2 2.2.2.2.2 教师和课程问题教师和课程问题每个课程都有自己的编号、名称以及开课学院。每个课程都要有授课教师。每门课程都有指定的教室类型。如普通教室、语音室、操场、实验室或机房等等。每门课程都有授课计划，包括起始周和截止周以及周学时安排。在处理课程与教师时要注意以下几个问题:(1)“授一班多门课”问题:同一教师可以只上一门课，也可上多门课，如
15、果同一教师在同一个班级教授多门课程，那么把课程和教师作同一变量考虑就会引起课程的混乱，此问题5须分情况解决，我们将在系统设计中，学院安排开课任务时解决此问题。(2)“一师多班”冲突问题:一位教师可能只给一个班讲课，也可能同时给多个班级讲课，也就是说同一教师可以在多个班出现，这样可能会出现同一时间，同一教师在多个班级上课的冲突，在编排课程表时此类冲突必须解决。(3)“多学时”问题:对于有些课程既可能只上一次，既 2 学时课程，而有些课程可能上多次，如 4 学时、6 学时等，多学时的课程如何处理也是在编排课程表时必须解决的问题。(4)“固定课”问题:有的教师因为某些原因需要安排特定的教学时一段，如
16、教室受到其他课程的影响，或者某学院部门领导，因工作性质关系，须指定安排上课时间为“星期五的第 5、6 节” ，这样的要求在编排课程表时必须满足，即“固定时段”问题。(5)“特殊课”问题：像体育课，要跟硬件设施有关，故要妥善处理。2 2.22.3 3 教室的问题教室的问题如今的大学都有很多的教学楼，校园面积也很大，宿舍与教学楼，教学楼与教学楼之间的距离可能会比较大，如果安排不佳的话，会导致学生上课时要跑动很远距离，浪费不必要的时间。本文在地理位置上是学校统一规划，进而综合解决位置问题，学校要规划好各个学院的学生在哪些教学楼里就近上课，而这样做的目的就是为了减少学生和教师的走动范围。至于如何去确定一个教室，例如 5-0122，就表示 5 教学楼，1 楼 22 号教室。每个教室在同一时间内只能接纳一门课程的授课，并且教室容量应该大于等于上课的人数。当上课的人数远远小于教室容量时，这种情况也往往不合适的。2 2.3.3 功能需求分析功能需求分析根据业务分析和数据分析，可得出排课系统主要完成以下几个功能:2 2.3.3.1.1
