欢迎来到天天文库
浏览记录
ID:28830662
大小:50.00 KB
页数:10页
时间:2018-12-14
《自动排课算法分析报告报告材料》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、实用标准文案自动排课算法分析1绪论1.1课题背景与研究意义1.2课题的应用领域1.3课题的现状1.4解决NP问题的几种算法及其比较2目前流行的几种排课算法的介绍2.1.自动排课算法2.2基于优先级的排课算法3基于时间片优先级排课算法描述与分析3.1排课中的基本原则3.2排课的基本要求3.3基于时间片优先级排课算法描述3.4算法分析参考资料1绪论1课题背景与研究意义排课问题早在70年代就证明是一个NP完全问题,即算法的计算时间是呈指数增长的,这一论断确立了排课问题的理论深度。对于NP问题完全问题目前在数学上是没有一个通用的算法能够很
2、好地解决。然而很多NP完全问题目具有很重要的实际意义,例如。大家熟悉地路由算法就是很典型的一个NP完全问题,路由要在从多的节点中找出最短路径完成信息的传递。既然都是NP完全问题,那么很多路由算法就可以运用到解决排课问题上,如Dijkstra算法、节点子树剪枝构造网络最短路径法等等。目前大家对NP完全问题研究的主要思想是如何降低其计算复杂度。即利用一个近似算法来代替,力争使得解决问题的时间从指数增长化简到多项式增长。结合到课表问题就是建立一个合适的现实简约模型,利用该简约模型能够大大降低算法的复杂度,便于程序实现,这是解决排课问题一
3、个很多的思路。在高等院校中,培养学生的主要途径是教学。在教学活动中,有一系列管理工作,其中,教学计划的实施是一个重要的教学环节。每学期管理人员都要整理教学计划,根据教学计划下达教学任务书,然后根据教学任务书编排课程表。在这些教学调度工作中,既有大量繁琐的数据整理工作,更有严谨思维的脑力劳动,还要填写大量的表格。因此工作非常繁重。加之,随着教学改革的进行及“211”工程的实施,新的教育体制对课表的编排提出了更高的要求。手工排课时,信息的上通下达是极其麻烦的,而采用计算机排课,教学中的信息可以一目了然,对于优化学生的学习进程,评估每位
4、教师对教学的贡献,领导合理决策等都具有重要的意义,必将会大大推进教学的良性循环。2课题的应用领域本课题的研究对开发高校排课系统有指导作用。排课问题的核心为多维资源的冲突与抢占,对其研究对类似的问题(特别是与时间表有关的问题:如考试排考场问题、电影院排座问题、航空航线问题)也是个参考。3课题的现状年代末,国外就有人开始研究课表编排问题。1962年,Gotlieb曾提出了一个课表问题的数学模型,并利用匈牙利算法解决了三维线性运输问题。次后,人们对课表问题的算法、解的存在性等问题做了很多深入探讨。但是大多数文献所用的数学模型都是Gotl
5、ieb的数学模型的简化或补充,而至今还没有一个可行的算法来解决课表问题。精彩文档实用标准文案近40年来,人们对课表问题的计算机解法做了许多尝试。其中,课表编排的整数规划模型将问题归结为求一组0-1变量的解,但是其计算量非常大。解决0-1线性优化问题的分支一定界技术却只适用也规模较小的课表编排,Mihoc和Balas(1965)将课表公式化为一个优化问题,Krawczk则提出一种线性编程的方法。Junginger将课表问题简化为三维运输问题,而Tripathy则把课表问题视作整数线性编程问题并提出了大学课表的数学模型。此外,有些文献
6、试图从图论的角度来求解排课表的问题,但是图的染色问题也是NP完全问题,只有在极为简单的情况下才可以将课表编排转化为二部图匹配问题,这样的数学模型与实际相差太远,所以对于大多数学校的课表编排问题来说没有实用价值。进入九十年代以后,国外对课表问题的研究仍然十分活跃。比较有代表的有印度的Vastapur大学管理学院的ArabindaTripathy、加拿大Montreal大学的JeanAubin和JacquesFerland等。目前,解决课表方法的问题有:模拟手工排课法,图论方法,拉格朗日法,二次分配型法等多种方法。由于课表约束复杂,用
7、数学方法进行描述时往往导致问题规模剧烈增大,这已经成为应用数学编程解决课表问题的巨大障碍。国外的研究表明,解决大规模课表编排问题单纯靠数学方法是行不通的,而利用运筹学中分层规划的思想将问题分解,将是一个有希望得到成功的办法。在国内,对课表问题的研究开始于80年代初期、具有代表性的有:南京工学院的UTSS(AUniversityTimetableSchedulingSystem)系统,清华大学的TISER(TimetableSchedulER)系统,大连理工大学的智能教学组织管理与课程调度等,这些系统大多数都是模拟手工排课过程,以“
8、班”为单位,运用启发式函数来进行编排的。但是这些系统课表编排系统往往比较依赖于各个学校的教学体制,不宜进行大量推广。从实际使用的情况来看,国内外研制开发的这些软件系统在实用性上仍不尽如人意。一方面原因是作为一个很复杂的系统,排课要想面面俱到是一件很
此文档下载收益归作者所有