《排课系统的设计与实现》由会员分享，可在线阅读，更多相关《排课系统的设计与实现（34页珍藏版）》请在金锄头文库上搜索。
1、0毕业设计(论文)课 题 名 称 课表编排系统设计与实现 学 生 姓 名 吕季干 学 号 0840819035 系、年级专业 理学与信息科学系 08 级信息与计算科学 指 导 教 师 戴亚滨 职 称 讲师 2012 年 05 月 300摘 要近年来随着大学的扩招和规模的扩大，排课问题已成为一个非常棘手的问题，在教室资源有限的前提下课程编排显得更加繁重，同时课程的编排也更成为教学管理工作的关键，在一定程度和深度上影响着学生的培养与教学质量的提高。利用计算机进行自动排课，不但能使教务人员从繁杂的排课任务中解脱出来，提高教务管理工作效率，而且能改善教学管理质量，合理、高效地利用有限的教学资源，使学校
2、的各种教学活动、教学管理及其它相关的工作能够有序、规范地进行，维持正常的教学秩序，同时对推动教务管理的信息化起到非常重要的作用。排课问题是一个有约束的、多目标的、难解的组合优化问题，是属于 NP-完全问题。研究者提出了多种排课算法，例如模拟退火、列表寻优搜索、约束满意等算法，而遗传算法是很有效的求解最优解的算法之一。遗传算法通过交叉、变异、选择三种遗传算子来实现遗传和变异的功能,并采用适应度函数保证排课结果趋于最优，对现有教学资源进行科学合理的安排，在实践中具有一定的应用价值。针对之前研究者未解决的运行时间太长问题，本文提出了一套基于二维编码的改进的编码方法和教室位置填充方法，精简了染色体信息
3、量而大大缩短了系统的运行时间。此外，在系统设计中，运用了基于容器的容器编程技术，实现了不定数据量的便捷处理。关键词 遗传算法； 排课问题； 适应度函数0ABSTRACTAbstract In recent years, with the University Expansion and expansion of the scale.timetabling has become a very difficult problem. Limited resources in the classroom context, Curriculum has become more onerous. The
4、courses become the key to teaching management at the same time. It affects students in developing and improving the quality of teaching to some extent. Arranging automatically by computer, not only to academic staff from the cumbersome task of freeing Arranging, improve efficiency of educational adm
5、inistration, but also to improve the quality of teaching management. Rational and efficient use of limited teaching resources, making variety of teaching activities, teaching management and other related work orderly and standardized manner, keeping the normal teaching order, At the same time promot
6、ing the academic management of information technology play a very important role.Timetabling problem is a constrained, multi-objective, intractable combinatorial optimization problems, it belongs to NP-Complete problems. Researchers have proposed many other Timetabling Problem, such as Simulated Ann
7、ealing, List of search optimization, Constraint satisfaction and so on. But genetic algorithm is very effective algorithm for solving the optimal solution .GA carry out genetic and functional variation through Crossover, mutation and selection of three genetic operators. And adopt fitness function e
8、nsure Arranging Results tend to the best. 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 the classroom filled method, simplifying the chromosome information and gre
9、atly 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 words curriculum arrangement; genetic algorithm; Priority strategy1目录中文摘要 . I英文摘要
10、 . II1 前言 . 12 排课问题描述 . 22.1 问题需求分析 . 22.2 数据需求分析2.2.1 时间问题2.2.2 教师和课程问题2.2.3 教室的问题2.3 功能需求分析2.3.1 院管理模块2.3.2 自动排课模块2.4 排课过程的约束条件3 自动排课系统的设计. 23.1 遗传算法的思想 3.2 构建基因编码和染色体3.2.1 混合式编码3.2.2 染色体的表示3.2.3 初始化种群4 数据库问题 .34.1 数据库设计4.1.1 概念模型设计24.1.2 逻辑模型设计 4.1.3 数据库的物理设计4.2 期望结果4.2.1 构造适应度函数4.3 功能模块的设计4.3.1
11、登录模块4.3.2 主界面模块4.3.3 学院管理模块4.3.4 查询模块4.3.5 排课模块5 冲突问题解决. 46 结果评估 . 57 结束语 . 6致敬词 . 7参考文献 . 8附录 . 831 前言 随着高校招生逐年扩张，大学课程向着广度和深度发展，高校的教师、教室等一些资源越发显得紧张，不管是在时间还是效率方面，用人工排课已不能够解决现有的问题。排课是高校日常教学工作和其他活动的基础，是教师和学生正常科学工作学习的依据。所以计算法自动排课已成为一个重要的研究课题1。国内学者在自动排课系统方面曾做过一些研究，如用到到退火算法、回溯算法、遗传算法，但运行结果尚有待改进的地方，排课效果不尽
12、人意5。我们认为，问题不尽在数学建模上，还与问题的处理方式有关。将遗传算法应用于排课问题中，首先，初始化课表种群，其次，检测初试种群中的冲突，然后，对种群做选择，杂交，突变操作，一直迭代到具体指定的代数，最后就会得到较优解。文1中提到编码时染色体上基因片存储信息大小为 11 字节，而本文的编码方式一个基因片只用了 6 字节，轻装运行，经试验得出，速度更快。还有,文1介绍把教室与时间等信息共同处理的思路，这可能会产生空间上的冲突，而本文提出将教室分离出以单独处理，就完全解决了空间上的冲突问题。本文根据高校开课的具体情况，采用优化的编码方案，满足排课过程中的一些硬性和软性约束因素，利用遗传算法对课
13、表进行了优化，从而得到了最终的无冲突、更人性的排课方案。2 排课问题描述2.1 问题需求分析排课工作是一项十分繁重而复杂的工作，就以一般高校而言，它涉及到几千多门课程进行合理的组织安排，而所使用的教室资源却在学生规模每年都在增加的趋势下越发显得紧张了。排课的整个过程中充满了矛盾运动，其中包括上课班级、所开课程、任课教师、上课时间、上课地点这 5 个方面在排列组合中发生的冲突和矛盾现象。课程门类多、班级多、教师少、教室少、教师连续上课的要求、班级连续上课的时间合理安排是排课时发生冲突和矛盾的主要因素，而班级多、教室少则是矛盾的重要方面。课程表则是解决这些矛盾的舞台，是提高教学管理水平、组织师生进行有序教学的规范之一，对有效地提高教育教学质量有重要作用。如果课程表编排得不合理、不科学，4将影响课堂教学的效率和教学的整体效果。要想编排好学校的课程表，需要综合考虑学校的教师、教室、学生、班级、时间等多方面因素，反复调整，避免冲突。一张正确的课表应至少满足以下硬约束条件： 3(1) 一个教师或者一个班级或者一个教室在同一时间段内只能安排一门课程；(2) 分配的教室可容纳人数应该大于学生数。除了上述的硬性约束，还有些软约束，这些软约束有助于使得课表更加合理，更加人性化。这些软约束条件可能是 4：(1) 尽
