R_时刻表求解时间规划问题

论文摘要

本文通过对时间规划中R_时刻表这个主题的深入探讨，以时间关系矩阵为基础，给出了R_时刻表算法的详细步骤，并设计了一个通用的时间规划系统，将时间规划应用于大学课程和田径运动会竞赛项目安排中，从中我们学习并了解了时间规划的原理和机制。时间规划是以时间关系约束作为推理的依据，给出各事件发生、结束时间的时刻表。现实世界是个时空的世界，现实生活中的许多问题都属于时间规划问题。R_时刻表是时间规划算法的一种，它可以在若干存在关系约束的时间区间中找到同时满足所有关系约束的规划方案。本论文主要工作是。▲在算法的实现过程中发现了算法一些不完善的地方，通过实践给算法加入一些功能对其进行了完善，给出了完善后的算法。在矩阵化简中，通过线性表记录了简化时间矩阵和原时间关系矩阵的行列对应关系，在主算法中，通过线性表记录了哪些区间端点对应同一个相容子集，以便在输出R_时刻表时查找。▲在完善的算法基础上，设计并实现了一个通用的时间规划系统，该系统可以很好的完成关系矩阵构造、关系矩阵的简化和R_时刻表的求解，说明了改进后算法是有效可行的。▲利用集合的性质，将多成份关系约束看成几个单成份时间关系约束并集，我们给出了多成份关系约束的最优分解。在此基础上，给出了关系矩阵的构造、关系矩阵的化简和求解R_时刻表的算法，该算法能给出R_时刻表或判断无解但计算量未必一定收敛。▲遗传算法是一种将生物进化原理应用到计算机上，用来寻找难解问题近似解的一种全局优化搜索算法。我们尝试使用遗传算法来求解多成份时间关系下R_时刻表，并给出了相应的算法，大大降低了多成份下求解R_时刻表的复杂度。

论文目录

• 摘要
• Abstract
• 目录
• 第一章 绪论
• 1.1 时间规划概述
• 1.2 时间规划问题研究的意义
• 1.3 时间规划的表示方法
• 1.4 本论文的内容安排
• 第二章 时间规划的关系矩阵表示法
• 2.1 基于区间的逻辑结构
• 2.2 基于点关系的时间逻辑
• 2.3 时间关系的关系矩阵表示法
• 2.4 本章小结
• 时刻表算法'>第三章 R_时刻表算法
• 3.1 相关概念
• 时刻表算法'>3.2 R_时刻表算法
• 3.2.1 主算法
• 3.2.2 构造关系矩阵
• 3.2.3 简化矩阵算法
• 3.2.4 求相容子集的算法
• 3.3 简化矩阵算法的完善
• 3.4 主算法完善
• 3.5 本章小结
• 时刻表的设计'>第四章 时间规划R_时刻表的设计
• 4.1 系统需求
• 4.1.1 数据流图
• 4.1.2 功能模块
• 4.1.3 数据需求
• 4.2 详细设计
• 时刻表生成向导'>4.2.1 R_时刻表生成向导
• 4.2.2 关系矩阵的化简
• 时刻表'>4.2.3 求 R_时刻表
• 4.2.4 结果显示
• 4.3 开发平台及关键技术
• 时刻表应用实例'>4.4 R_时刻表应用实例
• 4.4.1 简化的大学课程安排
• 4.4.2 简化的运动会比赛项目的编排
• 4.5 本章小结
• 时刻表算法'>第五章 多成份下 R_时刻表算法
• 5.1 多成份下关系矩阵的构造
• 时刻表'>5.2 求解R_时刻表
• 5.3 利用遗传算法求解多成份问题
• 5.3.1 遗传算法概述
• 5.3.2 遗传算法的基本步骤
• 时刻表'>5.3.3 利用遗传算法求解多成份R_时刻表
• 5.4 本章小结
• 第六章 总结和展望
• 参考文献
• 致谢
• 攻读硕士期间科研和发表论文情况