带时间窗的相控阵雷达实时任务调度方法

为了解决传统相控阵雷达任务调度中采用基于工作方式优先级的方法而存在忽略任务时间紧迫性和重要性的问题,提出了一种基于任务自身工作方式优先级、截止期和空闲时间3个特征参数的相控阵雷达任务调度方法,通过调整参数的权重来适应调度器不同的负载情况,并采用时间窗处理发生冲突的任务请求,确保更多的高优先级任务在调度间隔内被调度。仿真结果表明,所提出的方法能够有效提高任务的调度成功率,明显改善调度器性能。     

基于目标威胁度的相控阵雷达自适应调度方法

对时间资源的合理安排是相控阵雷达发挥自身优势的关键。将目标威胁度引入调度算法中,与工作方式和任务截止期共同进行综合优先级规划。通过构建目标威胁度的量化模型,使雷达在调度跟踪任务时依目标威胁度大小分配时间。提出了修正价值率和执行威胁率的概念,完善了性能评估指标。通过仿真,全面评价了新算法性能,验证了引入目标威胁度的合理性。结果表明,新算法可以有效提升相控阵雷达对高威胁度目标的处理能力。     

SpaceFibre星载数据网络低延时确定性调度算法

针对超高速SpaceFibre星载网络中多源数据传输的确定性和实时性应用需求,提出一种分类细粒度低延时确定性调度算法。该算法基于差异化调度策略的思想,将数据流划分为三类。为实现网络资源的细粒度分配,引入扩展时隙。该算法采用无冲突均匀调度方法,降低了数据包的平均排队延时。为适应有效载荷组网的航天应用场景,该算法兼顾网络拓扑结构生成调度方案。为验证算法有效性,在OPNET仿真平台下利用自定义建模技术搭建网络仿真模型。仿真结果表明:相比优先权调度和无冲突连续调度机制,该算法实现了时间敏感数据流的确定性传输;随着时隙数目的增加,网络的延时性能和抗抖动性能显著提升,吞吐量性能得到保证;该算法具有一定的航天工程实用价值。     

The cyclic separation scheduling problem

This paper deals with the problem of scheduling items (tasks, employees, equipment, etc.) over a finite time horizon so as to minimize total cost expenditures while maintaining a predefined separation between certain items. The problem is cyclic, because the same schedule will be repeated over several consecutive time periods of equal length. Thus, requirements are present to maintain the separation of items not only within the individual time periods considered, but also between items in adjoining periods. A special purpose branch-and-bound algorithm is developed to solve this scheduling problem by taking advantage of its cyclic nature. Computational results are given.     

Scheduling of stochastic tasks on two parallel processors

We consider the problem of scheduling n tasks on two identical parallel processors. We show both in the case when the processing times for the n tasks are independent exponential random variables, and when they are independent hyperexponentials which are mixtures of two fixed exponentials, that the policy of performing tasks with longest expected processing time (LEPT) first minimizes the expected makespan, and that in the hyperexponential case the policy of performing tasks with shortest expected processing time (SEPT) first minimizes the expected flow time. The approach is simpler than the dynamic programming approach recently employed by Bruno and Downey.     

云平台上基于关键路径截取的有向无环图应用调度算法

针对云平台上有向无环图科学应用执行容易产生虚拟机资源过剩、资源使用率低及费用虚高的问题,给出一种基于关键路径截取的有向无环图应用调度算法。该算法采取关键路径截取技术,循环找出最晚完成的未分配任务,从该任务出发,在所有未分配任务构成的图中找出最大连通子图,并计算该子图的关键路径,然后将关键路径上的任务集调度到性能匹配的虚拟机上执行;同时通过任务回填技术充分利用虚拟机的空闲时间槽,提高资源使用率。实验结果表明,在云计算平台上,该算法不仅能够在截止时间内完成有向无环图科学应用,而且可以提高资源使用率,有效减少完成该应用所需整体费用。     

Hu's precedence tree scheduling algorithm: A simple proof

This article presents a simple proof of Hu's algorithm for scheduling in minimum time a set of tasks constrained by precedence tree constraints, each task requiring a unit time to complete, and where m processors are available.     

The quay crane scheduling problem with time windows

The quay crane scheduling problem consists of scheduling tasks for loading and unloading containers on cranes that are assigned to a vessel for its service. This article introduces a new approach for quay crane scheduling, where the availability of cranes at a vessel is restricted to certain time windows. The problem is of practical relevance, because container terminal operators frequently redeploy cranes among vessels to speed up the service of high‐priority vessels while serving low‐priority vessels casually. This article provides a mathematical formulation of the problem and a tree‐search‐based heuristic solution method. A computational investigation on a large set of test instances is used to evaluate the performance of the heuristic and to identify the impact of differently structured crane time windows on the achievable vessel handling time. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

卫星任务调度问题的约束规划模型

卫星任务规划与调度是空间资源管理的重要内容之一,其目的在于为卫星系统的任务计划编制提供科学合理的决策手段与依据。卫星任务调度问题的重要特点在于,调度任务存在可见时间窗口约束。只有在可见时间窗口内,调度任务才可能执行并完成。在进行合理假设的基础上,建立卫星任务调度问题的约束规划模型。对基本禁忌搜索算法进行改进,提出了模型求解的变邻域禁忌搜索算法。应用结果表明,约束规划模型的建立与求解是合理的。     

A non-myopic scheduling method of radar sensors for maneuvering target tracking and radiation control

In decades, the battlefield environment is becoming more and more complex with plenty of electronic equipments. Thus, in order to improve the survivability of radar sensors and satisfy the requirement of maneuvering target tracking with a low probability of intercept, a non-myopic scheduling is proposed to minimize the radiation cost with tracking accuracy constraint. At first, the scheduling problem is formulated as a partially observable Markov decision process (POMDP). Then the tracking accuracy and radiation cost over the future finite time horizon are predicted by the posterior carmér-rao lower bound (PCRLB) and the hidden Markov model filter, respectively. Finally, the proposed scheduling is implemented efficiently by utilizing the branch and bound (B&B) pruning algorithm. Simulation results show that the performance of maneuvering target tracking was improved by the improved interacting multiple model (IMM), and the scheduler time and maximum memory consumption were significant reduced by the present B&B pruning algorithm without losing the optimal solution.     

雷达装备战场抢修支援分队调度决策研究

针对雷达装备战场抢修支援分队支援抢修多个现场的损伤雷达装备,以及抢修过程中可能出现其它现场损伤雷达装备请求支援抢修的调度问题,以实现每次支援抢修损伤雷达装备都获得最大的战斗力恢复率为目标,提出了一种类似于计算机中断过程的调度决策方法。调度决策中的抢修中断优先级判定方法,也可作为抢修支援分队确定支援抢修多个现场损伤雷达装备初始次序的依据。最后,通过实例应用验证了调度决策方法的实用性和可行性。     

基于关键路径和任务复制的多核调度算法

针对目前大多数多核处理器任务分配优化算法没有考虑关键路径上节点对任务完成时间的重要影响,导致任务完成总时间延迟的问题,提出了基于关键路径和任务复制(CPTD)的单任务调度算法。CPTD算法通过复制任务图中fork节点的方式将任务图转化为与之相对应的产品加工树;再在生成的产品加工树中找到关键路径,并采取使关键路径上节点的紧前节点尽早调度的方式,使关键路径上节点尽早开始执行,进而使产品加工树中节点完成时间得以提前,达到缩短任务执行总时间的目的。理论分析表明,CPTD算法能够实现应用程序在多核上充分并行处理,并能缩短任务完成时间。     

Scheduling with earliest start and due date constraints

We consider the scheduling of n tasks on a single resource. Each task becomes available for processing at time a_i, must be completed by time b_i, and requires d_i time units for processing. The aim is to find a schedule that minimizes the elapsed time to complete all jobs. We present solution algorithms for this problem when job splitting is permitted and when job splitting is not permitted. Then we consider several scheduling situations which arise in practice where these models may apply.     

天基预警系统资源调度方法

对面向导弹预警任务的天基预警系统中的低轨卫星资源调度问题进行了研究.对预警任务的特性进行分析,提出了一种预警任务规划与分解方法以减少任务对资源占用时间的需求;在此基础上建立了该问题的约束满足CSP调度模型;针对该模型变量多、解空间规模庞大的特点以及对求解算法时效性的要求,设计了一种基于局部解空间跳出机制的改进型遗传算法MGA.仿真表明该模型与算法在给定时间内能够得到满意的调度方案.     

高频地波雷达作战效能评估分析方法

根据高频地波雷达的特点和作战任务,采用层次分析法,从探测能力、情报质量和生存能力三个指标层给出了高频地波雷达作战效能评估的层次结构体系,并确定了各效能指标及相对权重的计算方法,最后得出了高频地波雷达作战效能评估的定量分析方法,解决了雷达系统作为非直接杀伤性武器而无法评价其在作战背景下的作战效能的问题,为该雷达的作战使用提供了辅助决策的依据.     

面向两类典型分析仿真的多样本任务调度工具的设计

当在多台计算机上调度很多样本并行运行时,采用手工操作效率低且极易出错。设计一个自动化的任务分发与调度工具可以有效地提高仿真运行效率。蒙特卡罗仿真和粒子群优化算法仿真是两类典型的分析仿真,介绍了面向这两类仿真的多样本任务调度工具的实现原理和关键技术,这些方法具有很好的通用性和可扩展性,可以广泛应用于解决各类仿真任务的自动分发与调度问题。     

Feasibility analysis of WDM links for radar applications

Active phased array antennas enhances the performance of modern radars by using multiple low power transmit/receive modules in place of a high power transmitter in conventional radars. Fully distributed phased array radars demand the distribution of various signals in radio frequency(RF) and digital domain for real time operation. This is normally achieved through complex and bulky coaxial distribution networks. In this work, we intend to tap the inherent advantages of fiber links with wavelength division multiplexed(WDM) technology and a feasibility study to adapt these links for radar applications is carried out. This is done by analysing various parameters like amplitude, delay, frequency and phase variation response of various radar waveforms over WDM links. This also includes performance evaluation of non-linear frequency modulation(NLFM) signals, known for better signal to noise ratio(SNR) to specific side lobe levels. NLFM waveforms are further analysed using pulse compression(PC) technique. Link evaluation is also carried out using a standard simulation environment and is then experimentally verified with other waveforms like RF continuous wave(CW), pulsed RF and digital signals. Synchronization signals are generated from this variable duty cycle digital signals during real time radar operation. During evaluation of digital signals, variable transient effects for different duty cycles are observed from an amplifier configuration. A suppression method is proposed to eliminate this transient effects. Further, the link delay response is investigated using different lengths of fiber spools. It can be inferred from the experimental results that WDM links are capable of handling various signals significant to radar applications.     

基于共进化的多任务分配与调度

在考虑多种约束关系基础上 ,提出一种并行与分布式系统中多约束关系的任务分配与调度的共同进化遗传算法。仿真试验结果表明所给算法比传统单种遗传算法更能有效地进行多任务分配与调度 ,具有一定的工程价值     

Integrated scheduling of loading and transportation with tractors and semitrailers separated

Motivated by some practical applications, we study a new integrated loading and transportation scheduling problem. Given a set of jobs, a single crane is available to load jobs, one by one, onto semitrailers with a given capacity. Loaded semitrailers are assigned to tractors for transportation tasks. Subject to limited resources (crane, semitrailers, and tractors), the problem is to determine (1) an assignment of jobs to semitrailers for loading tasks, (2) a sequence for the crane to load jobs onto semitrailers, (3) an assignment of loaded semitrailers to tractors for transportation tasks, and (4) a transportation schedule of assigned tractors such that the completion time of the last transportation task is minimized. We first formulate the problem as a mixed integer linear programming model (MILPM) and prove that the problem is strongly NP‐hard. Then, optimality properties are provided which are useful in establishing an improved MILPM and designing solution algorithms. We develop a constructive heuristic, two LP‐based heuristics, and a recovering beam search heuristic to solve this problem. An improved procedure for solutions by heuristics is also presented. Furthermore, two branch‐and‐bound (B&B) algorithms with two different lower bounds are developed to solve the problem to optimality. Finally, computational experiments using both real data and randomly generated data demonstrate that our heuristics are highly efficient and effective. In terms of computational time and the number of instances solved to optimality in a time limit, the B&B algorithms are better than solving the MILPM. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 416–433, 2015     

网格环境下基于任务的虚拟物流资源匹配策略

网格环境下的虚拟物流资源调度问题，实质就是资源与任务如何匹配的问题。以首先满足任务需求为前提，综合考虑任务以及资源两方面的匹配要求，建立了资源任务一对一匹配模型，通过量化任务（资源）各条件因素基准值及其所占权重比率，结合循环匹配算法，提出了一种基于任务的资源任务匹配策略，有效避免多任务对资源的争抢，实现了资源任务匹配的准确性和有效性。