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

作     者：殷世民 

作者单位：安徽大学 

学位级别：硕士

导师姓名：程家兴

授予年度：2007年

学科分类：08[工学] 081104[工学-模式识别与智能系统] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

主      题：时间规划 R时刻表 时间矩阵 遗传算法 

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