大学课程表问题中的算法研究与应用

论文摘要

课程表问题(UTP)是一个应用广泛的、典型的组合优化和不确定性调度问题,并且已经被证明是NP完全问题。随着高校规模的不断扩大,和教学管理信息化的不断深入,传统的手工排课和计算机辅助排课已经越来越难以适应现实的需求,而自动化排课系统,因其固有的高难度和复杂性,它的研究与实现成为完善中南大学网络教学管理系统十分重要的一环。本文从实际应用出发,基于动态规划的思想,提出了一种解决大学课程表问题的混合算法,并基于此算法设计并实现了自动化排课系统。本文首先介绍了UTP问题的研究现状、涉及的因素、各种约束条件,及其数学模型,然后详细阐述了将课程表问题划分为时间片安排和场地安排两个阶段,分别采用智能算法和最佳适应算法逐段求解,并最终求得全局较优解的混合算法。然后,对混合算法与经典遗传算法进行了对比实验分析,结果表明这种分阶段决策的算法在保证课表质量的同时,能够有效的减小遗传算法在求解UTP问题中的复杂度,提高程序的运行速度,也有利于工程应用中对多目标优化的进一步扩展。随后,本文基于混合算法,根据项目的实际需求,并考虑到和网络教学管理系统中其它子系统的集成,设计了排课系统的数据库表和各个功能模块,结合图表和文字说明,给出了详细的系统实现过程,并对系统实现过程中的关键技术进行了说明。最后,总结了本文所做的工作,分析了当前工作的不足及需进一步研究的工作。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第一章 绪论
• 1.1 课题来源及应用背景
• 1.2 国内外研究动态
• 1.3 课题的研究内容及意义
• 1.4 论文的内容安排和组织结构
• 第二章 课程表问题
• 2.1 时间表问题概述
• 2.1.1 时间表问题及其分类
• 2.1.2 School Timetabling问题
• 2.1.3 Course Timetabling问题
• 2.2 课程表问题的因素及约束条件
• 2.3 课程表的编排原则
• 第三章 基于动态规划思想的混合算法
• 3.1 最优化原理和动态规划
• 3.1.1 多阶段决策最优化问题
• 3.1.2 最优化原理
• 3.1.3 动态规划理论
• 3.2 混合算法设计
• 3.2.1 算法的总体设计思想
• 3.2.2 算法描述
• 3.3 基于遗传算法分配时间
• 3.3.1 遗传算法概述
• 3.3.2 基因编码设计
• 3.3.3 初始化种群
• 3.3.4 遗传算子操作设计
• 3.3.5 冲突检测与消除
• 3.4 基于最佳适应算法分配场地
• 3.5 对比实验分析
• 3.5.1 算法比较
• 3.5.2 实验设计
• 3.5.3 实验结果及分析
• 第四章 基于混合算法的排课系统
• 4.1 系统需求分析
• 4.2 系统总体设计
• 4.2.1 与其它子系统的集成
• 4.2.2 系统架构设计
• 4.2.3 系统网络体系结构
• 4.2.4 系统功能模块划分
• 4.3 数据库设计
• 4.3.1 数据库设计方案
• 4.3.2 表的设计
• 4.4 系统实现
• 4.4.1 表示层的实现
• 4.4.2 服务层的实现
• 4.4.3 业务逻辑层的实现
• 4.4.4 数据访问层的实现
• 4.5 关键技术研究
• 4.5.1 系统性能优化
• 4.5.2 数据库安全机制
• 第五章 回顾与展望
• 5.1 全文总结和工作回顾
• 5.2 后续工作与展望
• 参考文献
• 致谢
• 攻读学位期间主要的研究成果