时间自动机上邮递员问题：理论、模型、算法及应用研究

Cyber-Physical Systems (CPS) were recently named the first research priority in networking and information technology in China by the state council of advisors on science and technology. They offer new research challenges that stem from the integrations of computation with physical processes, and the traditional foundations of computing built over the last serveral decades are not adequate for CPS. Growing challenges span a large spectrum ranging from new models of compuation for systems that combine discrete and contineous variables, especailly, Hybrid Automata (HA), to the certain key problems incudling modeling, analysis, synthesize and optimization associated with the new models. This research focuses on the challenges in the compuation model and theory for CPS, more specifically, a special linear HA model, namely, Timed Automaton (TA), and the associated optimization theory are investigated. In this subject, two new kinds of Chinese Postman Problems (CPP) defined on TA are studied intensively for the first time. There are three main contributions in the subject: (1)The computational complexity theorems of the new problems, such as NP-hard and PSPACE perpoerties, are discussed; (2)Several mathematical models including linear relax model, partial order covering set model and arc dependent flow over time model are proposed, and the associated polyhedral theory is analysed; (3)The approaximation and heristic algorithms are designed for solving the new problems. Moreover, it can also develop the study of a key problem in real-time system software testing, and provide new technical methods to the test generation of real-time system. This subject is a hotspot of the cross discipline of many science branches including computer science, operational research and communication engineering, which can come together, penetrate and affect each other to promote new theories and methods. Thus, it has essential theoretical meaning and application value.

研究表明计算模式的变革遵循"十五年周期定律"，信息物理系统(CPS)的兴起恰好符合这一定律。CPS的基本科学问题是连续量与离散量共存，需要建立动态系统计算理论。近年来，科学家们一直在逻辑与物理交叉前沿领域探索新的计算模型，其中混合自动机是代表性方法之一。时间自动机(TA)是一种线性混合自动机，TA的建模、分析、综合和最优化这四大基本问题开辟了TA的理论研究课题。本课题针对TA上最优化问题开展探索性、创新性研究，首次提出了TA上两类邮递员问题的理论、模型和算法研究，分析了新问题的强NP困难性质和PSPACE完全性质等若干计算复杂性理论，建立了新问题的线性松弛、偏序覆盖和弧依赖动态流等松弛模型及其相关的多面体理论，并基于此提出了近似算法、启发式算法等一整套求解方法。本课题不仅在理论上具有挑战性，而且对应用研究有重要影响，其研究成果为实时通信系统一致性协议测试序列生成与优化提供了新的理论和方法。

研究表明计算模式的变革遵循“十五年周期定律”，信息物理系统(Cyber Physical System: CPS)的兴起恰好符合这一定律。CPS 的基本科学问题是连续量与离散量共存，需要建立动态系统计算理论。近年来，科学家们一直在逻辑与物理交叉前沿领域探索新的计算模型，其中时间自动机(Timed Automata: TA)是代表性方法之一。TA 的建模、分析、综合和最优化这四大基本问题开辟了TA 的理论研究课题。本课题针对TA 上最优化问题开展探索性、创新性研究。主要研究内容包括：(1)提出TA上邮递员问题，建立整数规划模型，分析了解空间的多面体理论，并开展割平面算法研究；(2)研究TA上中国邮递员和乡村邮递员问题的统一求解框架，应用模型验证算法同时求解TA上的多类邮递员问题。(3)针对可替代TA的易解模型Fork-Join有向图(DRT)模型及带时间约束的DRT模型，开展可调度性分析(问题本质上属于一类多邮递员问题)研究，证明了问题的强co-NP困难性质，并结合实时任务调度理论，为一些问题特例设计了伪多项式时间可调度性分析算法。(4)将Fork-Join的DRT图(及相关的多邮递员问题)应用于OpenMP并行程序设计语言的建模和理论分析，为OpenMP程序在实时多核平台上的可调度性分析提供了常数近似度的近似算法，并给出了OpenMP任务响应时间的安全上界。(5)将本课题的理论和算法应用于实时和多核平台的任务调度，为考虑通信时间的多核平台上任务调度问题设计了近似度为3的近似算法；应用整数规划方法为周期性实时任务调度问题进行多面体理论分析，并设计了高效的割平面算法。(6)探索了TA模型之外的实时计算模型：实时演算(Real Time Calculus: RTC)模型，并将其应用于智能城市交通信号系统的实时性能评估。. 在本项目的支持下，出版专著1部(科学出版社)，以第一作者在《ACM Trans on ECS》等国内外知名期刊上发表论文8篇,其中,SCI检索4篇,《软件学报》3篇,《计算机学报》1篇。另有新完成论文5篇，其中，DAC会议在投论文1篇，其他4篇拟向顶级国际会议RTSS、ECRTS、RTAS及知名国际期刊ACM Trans on ECS 投稿。. 本课题是计算机学科、通信、交通和管理综合交叉研究领域，是共性问题，具有重要的理论价值和应用价值。