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

时间表问题(TTP)是一个典型的组合优化和不确定性调度问题,并且已经被证实是NP完全问题,广泛应用于学校课程安排,会议日程安排、体育比赛和航班时刻表的制定等。高校课程表的编排问题是时间表问题的一种典型实例,实质上就是要求将学校开设的所有课程在满足一定的约束条件下,公道地安排到有限的课时和教室资源上。课表的编排工作是教学活动中必不可少的一个重要环节,对提高教学质量和节约教学资源起着非常关键的作用。因此,无论是从实际应用还是从理论意义的角度考虑,课表编排问题都具有很大的研究价值。通过结合本人在北京邮电大学经济管理学院教务科的排课经验,本文旨在设计简单、实用和高效的算法来研究解决高校排课问题。本文首先具体分析了高校排课问题中的各个要素、约束条件和衡量标准,并建立了排课问题的数学模型。在先容了目前在排课问题中主流的各个算法和解决方案之后,本文提出了基于优先级和多目标决策算法(Priority-basedAlgorithmwithMulti-ObjectiveDecision,PAMOD)来解决排课问题。PAMOD算法分为两个阶段：第一阶段通过优先级思想来构建课程的所有可行解,在第二阶段算法采用多目标决策的方法来衡量可行解中的最优解。之后,本文在满足3NF、无损连接、保持依靠的SQLServer2005数据库中实现了算法,终极的实验结果表明,本文提出的PAMOD算法是排课问题可行的和优良的解决方案。【关键词】：时间表问题高校课表编排问题优先级多目标决策
【论文提纲】：摘要4-5ABSTRACT5-9第一章绪论9-141.1引言91.2研究背景和意义9-111.3国内外研究现状11-121.4主要研究内容121.5论文组织结构12-14第二章排课问题分析14-262.1排课问题概述14-152.2排课问题的要素15-172.2.1时间15-162.2.2教室162.2.3教师162.2.4班级16-172.2.5课程172.3排课问题的约束17-182.4排课结果的衡量标准18-192.5排课问题的数学模型19-202.5.1排课问题中要素192.5.2排课问题的约束19-202.5.3排课问题的优化求解模型202.6排课问题研究综述20-252.6.1排课问题的求解方案20-242.6.2求解方案的分类24-252.6.3总结252.7本章小结25-26第三章排课算法的设计26-373.1算法概述263.2算法的基本思想26-273.3优先级27-283.4偏好度28-333.4.1教师偏好度283.4.2学生偏好度28-293.4.3教室利用率293.4.4资源偏好度29-313.4.5基于熵权的理想点法31-333.5算法流程33-363.5.1输入数据,设置参数33-343.5.2初始化算法343.5.3循环迭代34-363.6本章小结36-37第四章排课算法的实现37-464.1开发工具和环境374.2数据库设计37-444.3主函数44-454.4本章小结45-46第五章实验结果及分析46-535.1实验设计46-475.2实验结果分析47-495.2.1性能分析47-485.2.2公道性分析48-495.3算法数据分析49-515.4算法扩展分析51-525.5本章小结52-53第六章总结与展望53-556.1研究工作总结53-546.2研究工作展望54-55参考文献55-58致谢58-59作者攻读学位期间发表的学术论文目录59