二层SA/GA算法解决时间依赖中国邮路问题

中国邮路问题是图论中的经典问题,得到了深入研究和广泛应用。近年来,由于计算机网络与通信、智能交通系统等复杂应用领域的需求,研究时间依赖网络中的问题具有更为重要的现实应用意义。首先给出了时间依赖中国邮路问题的定义,然后证明了传统中国邮路问题的定理在时间依赖中国邮路问题中不成立,最后设计了二层SA/GA算法(模拟退火/遗传算法)来解决该问题,对随机产生的实例进行了测试,并根据问题下界对算法结果进行了分析。     

城市交通网络信号控制系统的实时演算模型

基于实时演算(Real-Time Calculus: RTC)理论,为单/双行道两类城市交通网络的定时和自适应两类信号控制系统建立了统一的形式化模型.首先,将车流和交叉路口分别建模为RTC的到达曲线和资源曲线.然后,根据不同信号控制策略,将紧邻路口间的曲线进行综合计算,得到整个交通网络的RTC模型.应用最小加代数方法,RTC模型能够计算车辆在路口的最长等待时间D和路口拥堵车队的最大长度B.基于RTC模型,应用MATLAB对8组不同规模的城市交通网格进行仿真,实验结果表明:1）与双行道网络相比,单行道网络更能有效处理较稀疏的交通流.以定时控制为例,在车流频率u≤1/2时,单行道网络能够将交通拥堵指标D和B分别降低至少2.66倍和3倍.2)双行道网络中,车流频率u存在一个临界区域.在临界域内,拥堵指标随车流频率递增变化;一旦u低于或超出临界域,拥堵指标则分别保持稳定不变或不可控.3)自适应策略优于定时控制策略.例如在双行道网络中,自适应控制策略对应的拥塞指标D和B比定时控制策略分别降低1.68倍和1.26倍.     

时间依赖无向中国邮路问题的分支限界算法

时间依赖网络相比传统网络模型有更广泛的应用领域,比如会交网络和通信网络都可以抽象成为时间依赖的网络模型。当模型中弧的访问代价为时间依赖的变量时,中国邮路问题的求解将变得非常困难。首先分析了传统的中国邮路问题求解算法,如奇偶图上作业法和Edmonds& Johnson算法,以及不能有效求解时间依赖中国邮路问题的根本原因;其次给出了一般时变无向中国邮路问题的特性,并在此基础上设计了该问题的分支限界最优化算法;然后针对FIFO(First In First Out)这一类特殊时变网络,设计了新的剪枝条件,从而得到了更有效求解FIFO网络的时变无向中国邮路问题的分支限界最优化算法;最后对算法进行了实验,算法实验结果正确。     

GPU上两阶段负载调度问题的建模与近似算法

随着硬件功能的不断丰富和软件开发环境的逐渐成熟,GPU(graphics processing unit)越来越多地被应用到通用计算领域,并对诸多计算系统(尤其是嵌入式系统)性能的显著提升起到了至关重要的作用.在基于GPU的计算系统中,大规模并行负载同时进行数据传输和加载的情况时常发生,数据传输延时在系统性能全局最优化中变得不容忽视.综合考虑负载的传输时间和执行时间,以总负载makespan最小化作为系统性能的全局优化目标,研究了GPU上负载“传输-执行”联合调度问题.首先,将负载的时间信息和并行任务数与矩形域的二维空间联系起来,建立了负载的2D双层矩形域模型;然后,将GPU上负载调度问题归结为一类Strip-Packing问题;最后,基于贪婪策略给出了近似度为3的多项式时间近似算法,算法复杂度为O(nlogn).该近似算法的核心是对数据传输阶段进行负载排序调度.这从理论层面上证明了GPU系统采取“传输-执行”两阶段调度的有效性,即,在数据传输阶段采取负载排序调度,在负载执行阶段采取先来先服务(first-come-first-serve,简称FCFS)调度,能够使GPU 性能达到全局最优或近似最优.     

重载列车上人员攀车行为感知及其时间自动机模型

重载列车进港安全监测是我国港口信息化建设中的重点和难点问题。实现列车运行过程追踪自动化对于保证安全高效完成列车进港监测具有十分重要的作用。在速度触发的条件下,设计了能够实时感知人员攀车行为的低功耗信息物理系统,并基于时间自动机理论给出了该系统的实时行为模型。应用UppAal工具仿真了系统的运行轨迹,并验证了系统可达性、安全性、活性和实时性等系统关键性质。实验结果表明,系统不仅在逻辑上满足正确性,而且在任何系统状态上都不会对时间约束发生偏移性错误。     

时间依赖网络中国邮路问题

中国邮路问题是图论中的经典问题,得到了深入的研究和广泛应用。近年来,由于计算机网络与通信、智能交通系统等复杂应用领域的需求,时间依赖网络问题的研究具有更为重要的现实应用意义。本文首次提出了时间依赖网络中的中国邮路问题,建立了该问题的整数线性规划模型,并对该模型的上界进行了分析,最后给出了网络应用实例。     

偶发实时系统可调度性分析问题的整数规划方法

偶发实时任务最早截止期优先（earliest deadline first,简称EDF）可调度分析是实时系统领域经典的NP困难问题.现有的伪多项式时间判定算法（pseudo-polynomail time decision algorithm,简称PTDA）均局限于利用率U严格小于1的同步任务系统.对于U≤1的同步系统或更加困难的异步系统,现有PTDA则不再适用.针对以上问题,为同步和异步两类实时系统建立了统一的整数规划模型,其规模并不依赖于利用率U的取值.基于多面体理论证明了模型维数和极大诱导不等式,进而提出了同/异步系统上EDF可调度性分析问题统一的多项式时间线性松弛求解方法.实验结果表明,该方法能够获得较紧的问题解下界,在异步和同步系统中,线性松弛解与最优解之间的平均百分界差gap分别为0.78%和1.27%.另外,随机生成了大量同步和异步系统的算例,用于该算法和传统算法进行性能比较.对于同步算例,实验结果表明,在U>0.99时,该算法能够对70%的算例给出判定结果,算法性能与QPA算法相比有指数级提升.对于异步算例,实验结果表明,该算法能够对近96%的算例给出可调度性判定.与传统算法相比,该方法将不能判定可调度性的算例比例平均降低了29.27%.对于剩余的4%的算例,该算法将可调度上界的值平均降低了近10⁴倍.     

时变网络中国邮路问题的时间自动机模型

基于时间自动机理论,提出了时间窗、时间依赖服务代价以及时间依赖旅行时间这3类时变网络中国邮路问题的统一建模的语义模型和求解方法.首先,将中国邮路问题可行解条件和时变参数与时间自动机联系起来,建立了3类问题的统一时间自动机系统(timed automata system,简称TAS)模型;然后,将时变网络中国邮路问题归结为TAS模型上的一系列可达性判定问题,并利用形式化验证算法给出了有效的求解方法.由于TAS模型中存在O(|A|+|AR|+1)个时间自动机,限制了问题求解规模.为此,通过扩展时间自动机语义,提出了TAS模型中的时间自动机合并策略,进而将TAS模型转换为一个广义时间自动机(GTA)模型.基于GTA模型,利用UPPAAL工具对9组、共54个随机算例进行实验.实验结果表明,该方法在求解精度上明显优于运筹学领域的方法.     

时间窗-时间依赖中国邮路问题的图转换算法

研究时间依赖网络上带时间窗的中国邮路问题（TDCPPTW）,该问题是对中国邮路问题的扩展,它考虑了时间因素,在实时软件测试等当前许多具有时间依赖性质的热门问题中更具优势。首先提出了一个新的图转换算法;然后,从理论上证明了该转换算法能够在伪多项式时间内将TDCPPTW转换为相应的广义乡村邮路问题（GRPP）;最后,建立了一个0/1线性整数规划模型用于求解转换后的问题,并对随机生成的12个实例进行了求解实验。