基于迭代前向搜索算法的高校排课问题研究

发布时间：2017-12-10 09:04

  本文关键词：基于迭代前向搜索算法的高校排课问题研究

  更多相关文章： 排课问题 迭代前向搜索算法 约束条件

【摘要】：时间表问题(timetabling problem)是一类多元受限的资源调度组合优化问题,其拥有非常广泛的应用领域,像航班时刻表、市公路运营等等。到目前已经证明该类问题是一种NP完全问题,而NP完全问题不存在时间复杂度为多项式时间的算法。而排课问题是时间表问题的一个重要应用。随着国内教育事业的发展,国内高校对教学质量的要求越来越高,排课的规模越来越大,师生对于课表的需求也越来越多。同时课程的编排还是教学管理工作中关键的一环,在很大程度上影响着学生培养与教学质量的提高。然而国内现有的排课方式却越来越无法满足现有的需求。迭代前向搜索算法是近十年才提出来的一种新型启发式算法,在国外高校排课中得到了广泛的应用,但是国内相关研究却比较少。本文在详细剖析该种先进算法的基础上,提出了与国内高校相适应的改进。主要工作内容如下:①讨论了排课问题中的主要约束条件、影响因素、相关算法,并详细描述了排课问题所对应的数学模型。研究了迭代前向搜索算法的理论知识、数学模型以及设计思想。②结合国内高校的实际情况,提出了基于回溯弧相容维持的约束改进迭代前向搜索算法,既解决了在国内越来越多见的跨校区教师调度问题和教师对授课时间的个性化需求的问题,同时又提高了算法面对大规模排课的性能。③以约束逻辑程序设计为指导思想,设计了改进迭代前向搜索算法的基础架构,并做了具体实现。④以重庆大学的真实课程数据为数据集,对改进后的迭代前向搜索算法分两个步骤进行测试:第一步是排全校的所有公共课,第二步是排特定学院的专业课。并根据测试的结果对改进算法的性能以及对国内高校的适应度进行了分析和评估。
【学位授予单位】：重庆大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP301.6;G647.3

【相似文献】

中国期刊全文数据库 前10条

1 朱莉娟;李冬;;计算机排课问题中几种算法的探讨[J];新乡教育学院学报;2007年03期

2 韩晶;;排课问题的数学表示[J];长治学院学报;2008年02期

3 吴丰;;蚁群算法在解决排课问题中的应用[J];开封大学学报;2010年01期

4 刘楚玲;彭平;谢赞福;;基于不等式方法的排课问题分析与验证[J];广东技术师范学院学报;2010年03期

5 夏季;;排课问题的数学模型设计[J];信息与电脑(理论版);2014年02期

6 吴节间;毛力;;改进蚁群算法在大学排课问题中的研究与应用[J];中国科教创新导刊;2009年29期

7 张岩;;浅析蚁群算法在排课问题的应用[J];中国科教创新导刊;2009年05期

8 张献;;蚁群算法在排课问题中的应用研究[J];长春大学学报;2007年10期

9 衷田田;;高校排课问题与算法分析[J];科教文汇(上旬刊);2012年06期

10 张丽丽;许峰;;几种智能算法在排课问题中的比较[J];湖南理工学院学报(自然科学版);2014年02期

中国重要会议论文全文数据库 前1条

1 祝勇仁;邓劲莲;胡献华;张炜;;排课问题的一种遗传算法适应度求解方法[A];第四届中国软件工程大会论文集[C];2007年

中国硕士学位论文全文数据库 前10条

1 郭赛君;面向高校统一教学资源排课问题的一种人机协同方法[D];大连海事大学;2015年

2 刘骁;基于迭代前向搜索算法的高校排课问题研究[D];重庆大学;2015年

3 赵惠怡;基于蚁群算法的排课问题的研究[D];大连海事大学;2007年

4 姚建波;基于遗传算法的排课问题的研究[D];贵州大学;2008年

5 郭志伟;通用智能人性化排课问题的研究[D];西北大学;2010年

6 张秀平;基于改进遗传模拟退火算法的排课问题研究[D];天津师范大学;2011年

7 赵光哲;基于遗传算法的大学排课问题的研究[D];延边大学;2006年

8 梁丽业;改进的蜜蜂交配算法及其在排课问题中的应用[D];河北工业大学;2012年

9 于国莉;基于遗传算法的排课问题的研究[D];河北工业大学;2007年

10 王仲华;遗传算法求解排课问题的研究[D];太原理工大学;2006年

，

本文编号：1273881