中文摘要：

智能规划和调度中的许多时态（或时序）问题可以表达为析取时态问题（DTP）．目前，多数析取时态问题求解器将析取时态问题看作约束可满足问题（CSP）或可满足问题（SAT），并使用标准的CSP（或SAT）技术来求解DTP．虽然这些技术在求解DTP时已经可以达到较好的效率，然而，文献中极少研究者关注利用DTP本身特殊的结构中隐舍的信息来帮助DTP求解．尝试从DTP的拓扑结构中提取出一种启发式策略．这种启发式策略试图从DTP的结构中提取出定性和定量的标准（TVS）来选择优先赋给当前变量的值，同时基于这种定量值选择标准设计了一个动态变量选择策略（TVO）．这种技术基于定义的一种DTP的图模型——析取时态网络（DTN）．实验结果显示TVS和TVO策略均可以有效减小搜索中节点访问次数；同时它与已有的RSV值选择策略效果相当，而TVO优于最少剩余值（MRV）方法（节省一个数量级以上的访问节点数）；此外，配合其他CSP启发技术，可以得到一个高效的DTP求解算法DTN—DTP．

英文摘要：

Many temporal problems arising in intelligent planning and scheduling can be expressed as disjunctive temporal problems （DTPs）. Most of DTP solvers in the literature treat DTPs as constraint satisfaction problems （CSPs） or satisfiability problems （SATs）, and solve them using standard CSP （SAT） techniques. They are proved to be very powerful in solving DTPs, however, unfortunately little work has been done on utilizing topological information encoded in DTPs to guide the search for solutions. Presented in this paper is a heuristics which is extracted via the analysis of DTP＇s topological structure. The heuristics tries to design qualitative and quantitative criteria for selecting those ＂best＂ values for current variables, and based on that a dynamic variable ordering heuristics is obtained for selecting the next ＂best＂ variable to try. The proposed strategy can be called ＂topology based value selection＂ strategy （TVS for short） for value selection and ＂topology based variable ordering＂ （TVO） for variable ordering. The approach is implemented based on a graphical model of DTPs defined in this paper, the disjunctive temporal network （DTN）. Experimental results show that the both TVS and TVO strategy can effectively reduce the visited nodes for DTP solving. Compared with similar techniques in the literature, TVS behaves comparatively to removal of subsumed variable （RSV）, and TVO performs usually better than minimal remaining values （MRV） heuristics even by one order-of-magnitude. Moreover, experimental results reveal that an efficient DTP solver--DTN- DTP can be obtained which incorporates other CSP techniques with TVO and TVS.