切换到高一层路网最近四个点的最短路算法

针对基于大规模图的最短路问题求解速度慢的问题,提出了一个基于路网等级的求最短路的快速近似算法。该算法首先求出高一层路网到起点的4个最近点和到终点的4个最近点及最短路径,由高一层路网形成的子图T再加上这8个最短路径形成图T',在T'上求起点到终点的最短路。这种设计使得该算法适合在超大规模图上求解,理论上也证明了精度可控,同时预处理数据也是可行的,从而使两点间最短路的求解速度大大提高。在纽约公路网上的测试结果说明了该算法的有效性和合理性。     

便携式时域反射仪硬件系统设计

介绍了用于土壤参数测量的时域反射仪硬件系统的设计与实现方案,并研制出样机TDR-I。该样机使用DSP做主控板,利用阶跃恢复二极管(SRD)产生140ps上升沿的快沿发射脉冲,采用快慢斜波比较法获得等效采样步进精度为8.7ps的取样脉冲。经过实验数据获取验证,该系统测量效果良好。     

纯滞后环对数字电源环路影响的研究

研究了滞后环对数字电源的影响和滞后环的等效简化模型,给出了基于Matlab数字电源补偿器的设计步骤。仿真和实验表明,通过该方法设计的数字电源环路稳定性得到了有效保证。     

Cops and Robbers from a distance

Cops and Robbers is a pursuit and evasion game played on graphs that has received much attention. We consider an extension of Cops and Robbers, distance k Cops and Robbers, where the cops win if at least one of them is of distance at most k from the robber in G. The cop number of a graph G is the minimum number of cops needed to capture the robber in G. The distance k analogue of the cop number, written c_k(G), equals the minimum number of cops needed to win at a given distance k. We study the parameter c_k from algorithmic, structural, and probabilistic perspectives. We supply a classification result for graphs with bounded c_k(G) values and develop an O(n^2s+3) algorithm for determining if c_k(G)≤s for s fixed. We prove that if s is not fixed, then computing c_k(G) is NP-hard. Upper and lower bounds are found for c_k(G) in terms of the order of G. We prove that

     

Heuristics for the multi-period orienteering problem with multiple time windows

We present the multi-period orienteering problem with multiple time windows (MuPOPTW), a new routing problem combining objective and constraints of the orienteering problem (OP) and team orienteering problem (TOP), constraints from standard vehicle routing problems, and original constraints from a real-world application. The problem itself comes from a real industrial case. Specific route duration constraints result in a route feasibility subproblem. We propose an exact algorithm for this subproblem, and we embed it in a variable neighborhood search method to solve the whole routing problem. We then provide experimental results for this method. We compare them to a commercial solver. We also adapt our method to standard benchmark OP and TOP instances, and provide comparative tables with state-of-the-art algorithms.     

Multi-item inventory model of breakable items with stock-dependent demand under stock and time dependent breakability rate

Items made of glass, ceramic, etc. are normally stored in stacks and get damaged during the storage due to the accumulated stress of heaped stock. These items are known as breakable items. Here a multi-item inventory model of breakable items is developed, where demands of the items are stock dependent, breakability rates increase linearly with stock and nonlinearly with time. Due to non-linearity and complexity of the problem, the model is solved numerically and final decisions are made using Genetic Algorithm (GA). In a particular case, model is solved analytically as well as numerically and results are compared. Models are developed with both crisp and uncertain inventory costs. For uncertain inventory costs both fuzzy and stochastic parameters are considered. A chance constrained approach is followed to deal with simultaneous presence of stochastic and fuzzy parameters. Different numerical examples are used to illustrate the problem for different cases.     

Improved results for scheduling batched parallel jobs by using a generalized analysis framework

We present two improved results for scheduling batched parallel jobs on multiprocessors with mean response time as the performance metric. These results are obtained by using a generalized analysis framework where the response time of the jobs is expressed in two contributing factors that directly impact a scheduler’s competitive ratio. Specifically, we show that the scheduler IGDEQ is 3-competitive against the optimal while AGDEQ is 5.24-competitive. These results improve the known competitive ratios of 4 and 10, obtained by Deng et al. and by He et al., respectively. For the common case where no fractional allotments are allowed, we show that slightly larger competitive ratios can be obtained by augmenting the schedulers with the round-robin strategy.     

Dynamic slack allocation algorithms for energy minimization on parallel machines

We explore novel algorithms for DVS (Dynamic Voltage Scaling) based energy minimization of DAG (Directed Acyclic Graph) based applications on parallel and distributed machines in dynamic environments. Static DVS algorithms for DAG execution use the estimated execution time. The estimated time in practice is overestimated or underestimated. Therefore, many tasks may be completed earlier or later than expected during the actual execution. For overestimation, the extra available slack can be added to future tasks so that energy requirements can be reduced. For underestimation, the increased time may cause the application to miss the deadline. Slack can be reduced for future tasks to reduce the possibility of not missing the deadline. In this paper, we present novel dynamic scheduling algorithms for reallocating the slack for future tasks to reduce energy and/or satisfy deadline constraints. Experimental results show that our algorithms are comparable to static algorithms applied at runtime in terms of energy minimization and deadline satisfaction, but require considerably smaller computational overhead.     

Partition oriented frame based fair scheduler

Proportionate fair schedulers provide an effective methodology for scheduling recurrent real-time tasks on multiprocessors. However, a drawback in these schedulers is that they ignore a task’s affinity towards the processor where it was executed last, causing frequent inter-processor task migrations which ultimately results in increased execution times. This paper presents Partition Oriented Frame Based Fair Scheduler (POFBFS), an efficient proportional fair scheduler for periodic firm and soft real-time tasks that ensures a bounded number of task migrations. Experimental results reveal that POFBFS can achieve 3 to 100 times reduction in the number of migrations suffered with respect to the General-ERfair algorithm (for a set of 25 to 100 tasks running on 2 to 8 processors) while simultaneously maintaining high fairness accuracy.     

有时态本体模型及其管理原型系统

为使本体能够方便地表达、处理与时间相关的信息,将有效时间概念引入本体模型,介绍有时态本体模型定义及相关定理,在此基础上,实现有时态本体管理原型系统,并将该原型系统应用于存在时态冲突的信息集成系统中进行实验。实验结果证明了将本体用有效时间进行扩展,从而形成有时态本体模型,并对其进行存储管理的必要性,同时也显示了该原型系统对时态查询的支持能力。