网络工程毕业设计论文基于遗传算法的高校排课系统设计实现.doc

本科毕业论文（设计）题 目 基于遗传算法的高校排课系统学 院 计算机与信息科学学院、软件学院 专 业 网络工程 年 级 200X 级 学 号 姓 名 指 导 老 师 成 绩 200X 年 4 月 30 日 1.引言 12.问题分析 12.1业务需求分析 12.2 数据需求分析 22.2.1时间问题 32.2.2 教师和课程问题 42.2.3教室的问题 42.3功能需求分析 42.3.1院管理模块 52.3.2校管理模块 52.3.3自动排课模块 52.4排课过程的约束条件 63.数据模型 73.1 问题陈述 73.2 数据流程图 84.问题解决 104.1 数据库设计 104.1.1 概念模型设计 104.1.2 逻辑模型设计 124.1.3 数据库的物理设计 164.2自动排课系统的设计 164.2.1遗传算法的思想 164.2.2构建基因编码和染色体 174.2.3 初始化种群 204.2.4 冲突检测及排除 214.2.5 构造适应度函数 224.2.6遗传算子 244.2.7设置控制参数 264.3教室位置填充设计 274.4功能模块的设计 284.4.1 登录模块 284.4.2主界面模块 294.4.3学院管理模块 304.4.4校管理模块 304.4.5查询模块 314.4.6 排课模块 315.系统运行结果及分析 315.1结果 315.2分析 326.总结及后续工作 35参考文献： 35基于遗传算法的高校排课系统 XXXXXX大学计算机信息与科学学院，重庆 400715摘要：排课问题是当今各大高校在教学资源管理、最优化配置上面临的主要问题之一。

本文将遗传算法应用于排课问题的求解中,采用基于轮盘赌算法的选择操作方法和优化的个体适应度计算方法，满足了排课过程中多部分软硬约束条件，实现了各种类型课程的排课针对之前研究者未解决的运行时间太长问题，本文提出了一套基于二维编码的改进的编码方法和教室位置填充方法，精简了染色体信息量而大大缩短了系统的运行时间此外，在系统设计中，运用了基于容器的容器编程技术，实现了不定数据量的便捷处理关键词：遗传算法；排课；教室安排；University Timetabling System based on genetic algorithm Zhang XiaodongThe college of Computer Information and Science ,Southwest University, Chongqing 400715, ChinaAbstract:Timetabling problem is one of the major problem,which today's universities face 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 and 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 didn't resolved well before,this paper puts forward a improved method based on two-dimensional coding and 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: Genetic Algorithm; Timetabling; Classroom Arrangement;1.引言随着高校招生逐年扩张，大学课程向着广度和深度发展，高校的教师、教室等一些资源越发显得紧张，不管是在时间还是效率方面，用人工排课已不能够解决现有的问题。

排课是高校日常教学工作和其他活动的基础，是教师和学生正常科学工作学习的依据所以计算法自动排课已成为一个重要的研究课题[1]国内学者在自动排课系统方面曾做过一些研究，如用到到退火算法、回溯算法、遗传算法，但运行结果尚有待改进的地方，排课效果不尽人意[5]我们认为，问题不尽在数学建模上，还与问题的处理方式有关将遗传算法应用于排课问题中，首先，初始化课表种群，其次，检测初试种群中的冲突，然后，对种群做选择，杂交，突变操作，一直迭代到具体指定的代数，最后就会得到较优解文[1]中提到编码时染色体上基因片存储信息大小为11字节，而本文的编码方式一个基因片只用了6字节，轻装运行，经试验得出，速度更快还有,文[1]介绍把教室与时间等信息共同处理的思路，这可能会产生空间上的冲突，而本文提出将教室分离出以单独处理，就完全解决了空间上的冲突问题本文根据高校开课的具体情况，采用优化的编码方案，满足排课过程中的一些硬性和软性约束因素，利用遗传算法对课表进行了优化，从而得到了最终的无冲突、更人性的排课方案2.问题分析2.1业务需求分析排课工作是一项十分繁重而复杂的工作，就以一般高校而言，它涉及到几千多门课程进行合理的组织安排，而所使用的教室资源却在学生规模每年都在增加的趋势下越发显得紧张了。

排课的整个过程中充满了矛盾运动，其中包括上课班级、所开课程、任课教师、上课时间、上课地点这5个方面在排列组合中发生的冲突和矛盾现象课程门类多、班级多、教师少、教室少、教师连续上课的要求、班级连续上课的时间合理安排是排课时发生冲突和矛盾的主要因素，而班级多、教室少则是矛盾的重要方面课程表则是解决这些矛盾的舞台，是提高教学管理水平、组织师生进行有序教学的规范之一，对有效地提高教育教学质量有重要作用如果课程表编排得不合理、不科学，将影响课堂教学的效率和教学的整体效果要想编排好学校的课程表，需要综合考虑学校的教师、教室、学生、班级、时间等多方面因素，反复调整，避免冲突分析一般高校的排课流程，其过程将如下，下面将排课整个流程作个介绍:(1)各学院从教学计划中导入开课任务书，让各学院安排好教师及教师的各种相关要求，比如班级、教室类型、时间类型等同时做好教学楼、教室和时间基础数据的输入（已存在数据库中）这一时间段主要做好班级、课程、教师的协调2)把各个学院开课任务书集合为学校开课任务书，同时规划好学院上课所在的教学楼形成位置表，以减少学生的跑动范围3)系统会根据校开课任务书自动排课这一过程主要完成班级、课程、教师及上课时间的安排。

4)把上一步排出的结果与位置表结合，就完成了课表的安排，中间整个过程都要解决冲突问题5)课表确定后，进行课表的查询图2-1排课流程图Chart 2-1 timetabling flow chart2.2 数据需求分析排课涉及的相关数据主要包括:时间、班级、课程、教室（空间）、教师等5个要素开始算法设计的基础是对这些数据之间的问题的透彻分析和适当的处理2.2.1时间问题在本文中考虑的是周课表，通过对全国部分高校做的调查，综合分析了其中大部分高校的教学特点，我们在此做出了一个较大众化的且较合理的时间划分模式设定周一至周五，共五天上课，一天有十节课，上课方式都为一大节包括2个相邻的小节，不能在上、下午之间跨时段把每天用于上课的时间划分为5个时间片，根据学院开课的实际情况，一般每学时是45分钟，为1小节课，每2小节课合为一大节课，故把每2小节课时间定为一个时间片，一天划分为5个时间片: (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; 这样，每周5天涉及25个时间片。

用Tl, T2,......,T25表示，其中TI, T2, T3, T4, T5为星期一的5个时间片，依次类推则排课问题类似于填充5×5的周时间片安排表 表2-1周时间片分布表Table2-1 the management table of the week time slip 周一周二周三周四周五T1T6T11T16T21T2T7T12T17T22T3T8T13T18T23T4T9T14T19T24T5T10T15T20T25根据时间片编号，可进一步转化为1×25的表格全校有N个教学班级，则周课表为:以25个时间片为列，形成一维的时间序列，每个班级为行组成的一个二维数据表我们在此系统的排课都是按一个大节开设的，符合按25个时间片划分的设计，但确有少量的课程的周学时数为单数，如“3学时”或“5学时”，在此仍按“4学时”或“6学时”进行编排，虽然这会浪费一小节课程2.2.2 教师和课程问题每个课程都有自己的编号、名称以及开课学院每个课程都要有授课教师每门课程都有指定的教室类型如普通教室、语音室、操场、实验室或机房等等每门课程都有授课计划，包括起始周和截止周以及周学时安排。

在处理课程与教师时要注意以下几个问题:(1)“授一班多门课”问题:同一教师可以只上一门课，也可上多门课，如果同一教师在同一个班级教授多门课程，那么把课程和教师作同一变量考虑就会引起课程的混乱，此问题须分情况解决，我们将在系统设计中，学院安排开课任务时解决此问题 (2)“一师多班”冲突问题:一位教师可能只给一个班讲课，也可能同。