基于贪心算法的时间片优先级排课算法的研究与应用

摘要

随着信息技术的不断发展,计算机的应用领域越来越广。作为高校最重要的教学调度工作,排课工作也从传统的手工排课转向了利用计算机进行排课。但目前计算机排课的成功率并不高。如何提高排课软件的成功率,正受到国内外学者及软件技术人员的普遍关注。
　　课表编排问题实质上是时间、教师、班级、教室、课程这五维关系的冲突NP完全问题。本文首先从解决排课问题的近似算法入手进行分析,如动态规划法、回溯法、贪心算法等,找到了解决排课问题的算法基础,创新性地提出了将贪心算法和时间片优先级算法相融合的基于贪心算法的时间片优先级排课算法。重点描述和比较了目前流行的基于动态规划法的自动排课算法,基于回溯法的优先级排课算法,以及本文所提出和研究的基于贪心算法的时间片优先级排课算法。自动排课算法是以课程为中心进行搜索匹配,取最先匹配的值,未对数据进行择优选取,所以不能对教学资源合理分配,也不能满足一些特殊要求(比如有些老师偏向于集中式上课,有些课程安排到上午会更合适些等)。优先级排课算法主要从解决时间、教师、班级、教室这四维关系之间的冲突入手,按班级和教室分类,根据时间数组来编排教师、教室、班级课表,对于课程的一些特殊要求无法体现。而基于贪心算法的时间片优先级排课算法针对时间、教师、教室、班级、课程这五维关系间的冲突,按时间片优先级来解决教师、班级、教室、课程间的冲突,不但对教学资源能进行合理分配,而且也能满足排课时的一些特殊要求,排出的课表比较合理。从排课的成功率、准确率以及算法的效率来分析,基于贪心算法的时间优先级排课算法明显优于其他排课算法。
　　本文最后以作者所在工作单位湖南工程职业技术学院为例,将本文所研究和提出的基于贪心算法的时间片优先级排课算法应用到具体实例---实训资源管理系统,详细描述了该系统从算法分析到系统设计,再到功能模块实现的设计和开发过程,为基于贪心算法的时间片优先级排课算法在排课问题的应用上提供了有力的案例支持。

目录

封面

声明

中文摘要

英文摘要

目录

插图索引

附表索引

第1章 绪 论

1.1 研究背景及意义

1.2 国内外研究现状

1.3 目前存在的问题

1.4 本文主要研究内容

1.5 论文章节安排

第2章 排课问题算法分析

2.1 回溯法

2.2 动态规划法

2.3 贪心算法

2.4 两种排课算法分析

2.5 小结

第3章 基于贪心算法的时间片优先级算法

3.1 贪心算法

3.2 时间片优先级算法

3.3 基于贪心算法的时间片优先级算法

3.4 小结

第4章 应用实例—实训资源管理系统

4.1 应用背景

4.2 应用算法设计思想

4.3 系统设计

4.4 系统实现

4.5 小结

结论

参考文献

致谢