基于贪婪算法的排课系统的研究与实现

论文摘要

目前,随着计算机的广泛应用和互联网技术的高速发展,在全国高校中许多教学管理系统相继投入使用。然而,在实际项目的研发中,由于排课问题是一个NP完全问题,开发出符合要求的排课系统是一件难事。 针对排课系统研发和运行中存在的问题,尝试使用贪婪算法去研究和解决问题。贪婪算法是从问题的某一个初始解出发,通过一系列的贪婪选择——当前状态下的最优选择,逐步逼近给定的目标,以尽可能快的求得更好的解。当达到算法中的某一步不能再继续前进时,算法停止。在贪婪算法(greedy method)中采用逐步构造最优解的方法。在每个阶段,都作出一个看上去最优的决策(在一定的标准下)。 基于此,以广东工业大学计算机工程研发中心与深圳大学成人教育学院合作研发的排课系统为背景,在参照了排课算法的大量文献上,结合本系统的实现和现在的运行情况上的不足,根据项目中客户排课的实际需求,基于贪婪算法,以资源匹配为基础,用内存动态分区分配的最佳适应法为依托进行研发,最后设计和实现该排课系统,在实际运行测试中表明,该排课系统的响应时间和排课结果较满意,可以将此推广到其他教学管理系统的开发和实施上。 论文最后对论文本身做了总结,阐述了论文的工作,并指出进一步研究的方向。

论文目录

• 摘要
• ABSTRACT
• 目录
• CONTENTS
• 第一章 绪论
• 1.1 课题的来源
• 1.2 排课系统发展现状
• 1.3 本论文排课系统的解决方案
• 1.4 课题研究内容与意义
• 1.4.1 课题研究内容
• 1.4.2 课题研究意义
• 1.4.3 特色之处
• 1.5 论文内容组织
• 第二章 教学管理系统介绍
• 2.1 项目需求
• 2.2 网络拓扑
• 2.3 教学管理系统的体系结构
• 2.4 系统功能模块
• 2.5 数据库设计
• 2.6 排课概述
• 2.7 系统的运行情况和问题及论文研究对象的导出
• 2.8 本章小结
• 第三章 排课系统的相关技术
• 3.1 排课问题的求解技术综述
• 3.2 MULTIMAP关联容器
• 3.3 贪婪算法介绍
• 3.3.1 贪婪算法主要思想
• 3.3.2 贪婪算法的求解步骤
• 3.3.3 贪婪算法求解问题性质
• 3.3.4 贪婪算法的求解例子
• 3.4 本章小结
• 第四章 基于贪婪算法的排课系统的研究与设计
• 4.1 本排课系统采用贪婪算法的原因
• 4.2 排课情况分析
• 4.2.1 排课的要素
• 4.2.2 排课过程的约束条件
• 4.2.3 排课目标
• 4.3 排课系统分析
• 4.3.1 排课系统用例图
• 4.3.2 排课系统用例说明
• 4.4 系统的体系结构
• 4.5 类和数据库的设计
• 4.4.1 类设计
• 4.4.2 数据库设计
• 4.6 系统主要功能
• 4.6.1 预排课
• 4.6.2 最终排课
• 4.6.3 手动排课
• 4.6.4 合并班级
• 4.6.5 删除排课结果
• 4.7 排课系统中的贪婪准则
• 4.7.1 为有上课时间要求的课程安排教室的贪婪准则
• 4.7.2 为无上课时间要求的课程安排教室的贪婪准则
• 4.8 数据结构
• 4.8.1 教室信息数据结构及函数、链表
• 4.8.2 课程班信息数据结构及函数、链表
• 4.9 排课主要算法
• 4.9.1 排课主算法（0层图）
• 4.9.2 信息结点初始化（加工1子图）
• 4.9.3 安排教室（加工2子图）
• 4.9.4 分裂教室结点（加工3子图）
• 4.10 本章小结
• 第五章 基于贪婪算法的排课系统实现
• 5.1 预排课
• 5.2 最终排课
• 5.3 手动排课
• 5.4 合并班级
• 5.5 删除排课结果
• 5.6 保存排课结果
• 5.7 部分关键代码
• 5.7.1 总控程序关键代码
• 5.7.2 排课的关键代码
• 5.7.3 信息结点初始化的关键代码
• 5.7.4 分裂教室结点的关键代码
• 5.8 本章小结
• 第六章 系统运行情况分析及展望
• 6.1 系统运行情况
• 6.1.1 自动排课
• 6.1.2 手动排课
• 6.1.3 合并班级
• 6.1.4 打印课表
• 6.2 排课系统运行情况分析
• 6.3 展望和进一步的工作
• 6.3.1 展望
• 6.3.2 进一步的工作
• 6.4 本章小结
• 总结
• 参考文献
• 攻读学位期间发表的学术论文
• 独创性声明
• 致谢
• 附图表目录