基于优先级和多目标决策算法求解时间表问题的研究

论文摘要

时间表问题（TTP）是一个典型的组合优化和不确定性调度问题,并且已经被证明是NP完全问题,广泛应用于学校课程安排,会议日程安排、体育比赛和航班时刻表的制定等。高校课程表的编排问题是时间表问题的一种典型实例,实质上就是要求将学校开设的所有课程在满足一定的约束条件下,合理地安排到有限的课时和教室资源上。课表的编排工作是教学活动中必不可少的一个重要环节,对提高教学质量和节约教学资源起着非常关键的作用。因此,无论是从实际应用还是从理论意义的角度考虑,课表编排问题都具有很大的研究价值。通过结合本人在北京邮电大学经济管理学院教务科的排课经验,本文旨在设计简单、实用和高效的算法来研究解决高校排课问题。本文首先详细分析了高校排课问题中的各个要素、约束条件和衡量标准,并建立了排课问题的数学模型。在介绍了目前在排课问题中主流的各个算法和解决方案之后,本文提出了基于优先级和多目标决策算法（Priority-based Algorithm with Multi-Objective Decision, PAMOD）来解决排课问题。PAMOD算法分为两个阶段：第一阶段通过优先级思想来构建课程的所有可行解,在第二阶段算法采用多目标决策的方法来衡量可行解中的最优解。之后,本文在满足3NF、无损连接、保持依赖的SQL Server 2005数据库中实现了算法,最终的实验结果表明,本文提出的PAMOD算法是排课问题可行的和优良的解决方案。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 研究背景和意义
• 1.3 国内外研究现状
• 1.4 主要研究内容
• 1.5 论文组织结构
• 第二章 排课问题分析
• 2.1 排课问题概述
• 2.2 排课问题的要素
• 2.2.1 时间
• 2.2.2 教室
• 2.2.3 教师
• 2.2.4 班级
• 2.2.5 课程
• 2.3 排课问题的约束
• 2.4 排课结果的衡量标准
• 2.5 排课问题的数学模型
• 2.5.1 排课问题中要素
• 2.5.2 排课问题的约束
• 2.5.3 排课问题的优化求解模型
• 2.6 排课问题研究综述
• 2.6.1 排课问题的求解方案
• 2.6.2 求解方案的分类
• 2.6.3 总结
• 2.7 本章小结
• 第三章 排课算法的设计
• 3.1 算法概述
• 3.2 算法的基本思想
• 3.3 优先级
• 3.4 偏好度
• 3.4.1 教师偏好度
• 3.4.2 学生偏好度
• 3.4.3 教室利用率
• 3.4.4 资源偏好度
• 3.4.5 基于熵权的理想点法
• 3.5 算法流程
• 3.5.1 输入数据,设置参数
• 3.5.2 初始化算法
• 3.5.3 循环迭代
• 3.6 本章小结
• 第四章 排课算法的实现
• 4.1 开发工具和环境
• 4.2 数据库设计
• 4.3 主函数
• 4.4 本章小结
• 第五章 实验结果及分析
• 5.1 实验设计
• 5.2 实验结果分析
• 5.2.1 性能分析
• 5.2.2 合理性分析
• 5.3 算法数据分析
• 5.4 算法扩展分析
• 5.5 本章小结
• 第六章 总结与展望
• 6.1 研究工作总结
• 6.2 研究工作展望
• 参考文献
• 致谢
• 作者攻读学位期间发表的学术论文目录