发布时间 : 星期三 文章排课表问题的数学原理及其算法研究更新完毕开始阅读7b3dfca4ccbff121dc36831e
兰州大学
2013届本科毕业论文
排课表问题的数学原理及其算法研究
姓 名: 姜涛
系 别:数学与信息科学学院
专 业: 应用数学
学 号: 090211133
指导教师: 梁云
2012年 5 月 5 日
2013届本科生毕业论文
目 录
摘 要 .................................................................................................................................................................. III 关键词 .................................................................................................................................................................. III ABSTRACT ......................................................................................................................................................... III KEY WORDS ...................................................................................................................................................... III 0 引言 .................................................................................................................................................................... 1 1 绪论 .................................................................................................................................................................. 1
1．1 课题背景与研究的意义 ............................................................................................................. 1 1．2 课题的现状分析 ......................................................................................................................... 1 1．3 解决NP问题的几种算法及其比较 ......................................................................................... 2
2 目前流行的几种排课算法的介绍 ................................................................................................................... 3
2．1 自动排课算法 ............................................................................................................................. 3
2．2 基于优先级的排课算法 ............................................................................................................. 5
3 排课中的基本原则和要求 ............................................................................................................................... 7
3．1 排课中的基本原则 ..................................................................................................................... 7
3．2 排课的基本要求 ......................................................................................................................... 7 3．3 基于时间片优先级排课算法描述 ............................................................................................. 8 3．4 算法分析 ................................................................................................................................... 10
4 结束语 ............................................................................................................................................................ 10 参考文献 .............................................................................................................................................................. 10 致 谢 .................................................................................................................................................................... 10
II
2013届本科生毕业论文
排课表问题的数学原理及其算法研究
摘 要
本文首先介绍了解决NP问题的几种常用算法:动态规划算法、贪心算法和回溯算法,进而运用这些算法的思想,探究了排课表问题的几种算法.经过比较我找出了这几种算法的优缺点及试用领域,解决了各种教学资源如教室、教师的合理有效利用问题,避免了教师、班级在上课时间、地点上的冲突,使排课时间分配均匀.
关键词
NP问题;动态规划算法;贪心算法;回溯算法
Principia mathematica of the table problem and its algorithm
Abstract
This paper first introduces several commonly used algorithms to solve the NP problem: dynamic programming algorithm, greedy and backtracking algorithms, then use the idea of these algorithms, explore several algorithms of the table problem. By comparison, I find out the advantages and disadvantages of several algorithms and trial areas, solve a variety of teaching resources such as classrooms, teachers rational and efficient use, to avoid the teachers, class conflict on the time, place, timetable the time allocation uniform.
Key words
NP problem ;Dynamic programming algorithm ;Greedy algorithm ;Backtracking algorithm
III
2013届本科生毕业论文
0 引言
课程表是一个学校日常教学工作和其他各项活动的指挥调度表,它不仅是学生和教师上课的依据,而且对学校其他工作的统一安排也有直接影响.高校排课工作是执行教学计划、实现学校培养目标的重要一环,是学校教学教务管理工作中最基本而又非常重要的一项,它是学校建立稳定的教学秩序的最根本的保证,是学校贯彻教育方针、培养合格人才的具体体现,并对学生的学习效果和课堂的教学质量有直接的影响.因此如何利用有限的师资力量和有限教学资源,排出一个合理的课程安排结果,对稳定教学秩序、提高教学质量有着积极的意义.
1 绪论
1．1 课题背景与研究的意义
国外从20世纪50年代末就对排课问题开展了研究.1963年Gotlieb对课程表问题做了形式化描述,提出了排课问题的数学模型.但由于在实践中遇到的困难,人们对排课问题的了解是否存在产生了疑问.1976年Seven和Cooper等人证明了排课问题是NP完全类问题[1],这就从理论的角度回答了排课实践中遇到困难的原因,正式确立了排课问题的学术地位,把人们对课表编排复杂性的认识提高到了理论的高度.自Gotlieb提出排课问题数学模型之后,人们又对排课问题的算法作了许多探索,但由于排课问题是NP完全类问题,并且易受实际问题的影响,大多数求解结果都不理想.Ferland和吴金荣等人把排课问题化成整数规划来解决,但计算量很大,而且仅仅适用于规模很小的课表编排,对于大规模复杂的排课情况,至今没有一个切实可行的算法.何永泰和胡顺仁等人试图用图论中的染色问题来求解排课问题[2],可惜图的染色问题本身也是NP完全类问题.由于问题的复杂性,研究者探索利用启发式函数来解决排课问题,通过模拟手工排课过程来实现计算机排课.由于实际的排课问题存在各种各样的限制条件与特殊要求,对这些因素处理的好坏就显得尤为重要.
国内对排课问题的研究开始于80年代初期,所用方法包括模拟手工排课的人工智能、专家系统等方法.基于时间位图迭加匹配的算法定义了教学过程中的时间位图、课时模式和时间匹配等概念,将排课问题转化为基于时间位图迭加匹配的课时模式查找问题,给出了相应的抽象具体排课过程,并对于排课过程中可能出现的冲突,探讨了三种回溯消除冲突方式.基于优先级自动排课算法用了运筹学中分层规划的思想,把排课问题在数学上看作为一个时间、教师、学生和教室四维空间,以教学计划和各种特殊要求为约束条件的组合规划问题,采用了化整为零的思想并且提出了优先级的概念,有效地抽象了实际排课问题,缩小了求解问题的空间[3].本课题的研究对开发高校排课系统有指导作用.排课问题的核心为多维资源的冲突与抢占,对其研究对类似的问题（特别是与时间表有关的问题:如考试排考场问题、电影院排座问题、航空航线问题）也是个参考. 1．2 课题的现状分析
课程表是地方高校开展教学活动的指令性文件,在地方高校的传统排课方式下,课表编排主要是靠手工完成的,排课人员需要花费大量的时间和精力,并且容易出错,同时手工操作也不能满足资源需求的经常变化.
当前地方高校普遍利用计算机进行自动排课,不但能使教务人员从繁杂的排课任务中解脱出来,提高教务管理工作效率,而且能改善教学管理质量,合理、高效地利用有限的教学资源,使学校的各种教学活动、教学管理及其它相关的工作能够有序、规范地进行,维持正常的教学秩序,同时对推动教务管理的信息化起到非常重要的作用.由此出现了众多的计算机排课软件.但是当前地方高校在采用计算机进行排课过程中,大多采用传统方法进行程序设计,把程序作为系统核心.系统中所使用的排课数据主要考虑了一般性排课原则,而对于不同学校的特点考虑不足,特别是学生层次的关注度不够,并且数据与程序结合过于紧密,程序的修改维护有很大难度,不便于系统扩充和升级,因此限制了系统的通用性.而且在发生特殊情形下,只能依赖于人工调整,同时课表编排问题涉及教师、教室、学生、课程及教学时间等多种因素的组合规划,具有规模大、约束条件复杂以及不断变化等特点.因此,探究出适合具体条件的算法是解决问题的关键.
1