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

发布时间：2017-06-04 12:19

  本文关键词：基于优先级和多目标决策算法求解时间表问题的研究，，由笔耕文化传播整理发布。

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

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

【参考文献】

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

1 陈谊,杨怡,张国龙,王尚忠;基于优先级自动排课算法PCSA的设计与实现方案[J];北京工商大学学报(自然科学版);2002年02期

2 陈本庆,马永强,何虎;改进型回溯法在高校排课中的应用[J];成都信息工程学院学报;2003年02期

3 胡顺仁,邓毅,王铮;基于高校排课系统中的图论问题研究[J];计算机工程与应用;2002年04期

4 段琢华,姜云飞;基于扩展知识结构图的智能教学规划[J];计算机工程与应用;2005年17期

5 唐勇,唐雪飞,王玲;基于遗传算法的排课系统[J];计算机应用;2002年10期

6 王家华,金祥意,张宏霞,姚天顺;一类递归查询问题的快速求解算法[J];控制与决策;1999年02期

7 刘继清,陈传波;模拟退火算法在排课中的应用[J];武汉船舶职业技术学院学报;2003年03期

8 黄干平,姚自珍,张轶静;使用模拟退火算法解课表问题[J];武汉大学学报(自然科学版);2000年05期

9 聂小东;李振坤;陈平华;;基于贪婪算法的排课系统的探讨与实现[J];现代计算机(专业版);2007年11期

10 董艳云,钱晓群,张宇舒;基于课元相关运算的高校排课算法[J];西南交通大学学报;1998年06期

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

1 刘永凯;课表安排问题的启发式算法研究[D];厦门大学;2009年

2 叶碧虾;基于遗传和禁忌搜索算法的排课系统研究与实现[D];厦门大学;2009年

3 王海涛;基于整数规划的混沌遗传排课算法研究[D];北京化工大学;2009年

4 陈远;基于遗传算法的排课系统的设计[D];苏州大学;2009年

  本文关键词：基于优先级和多目标决策算法求解时间表问题的研究，由笔耕文化传播整理发布。

本文编号：420977