Optimal divisible job load sharing for bus networks

Optimal load allocation for load sharing a divisible job over N processors interconnected in bus-oriented network is considered. The processors are equipped with front-end processors. It is analytically proved, for the first time, that a minimal solution time is achieved when the computation by each processor finishes at the same time. Closed form solutions for the minimum finish time and the optimal data allocation for each processor are also obtained     

Optimal time-varying load sharing for divisible loads

A load sharing problem involving the optimal load allocation of divisible loads in a distributed computing system consisting of N processors interconnected through a bus-oriented network is investigated. For a divisible lend, the workload is infinitely divisible so that each fraction of the workload can be distributed and independently computed on each processor. For the first time in divisible load theory, an analysis is provided in the case when the processor speed and the channel speed are time varying due to background jobs submitted to the distributed system with nonnegligible communication delays. A numerical method to calculate the average of the time-varying processor speed and the channel speed and an algorithm to find the optimal allocation of the workload to minimize the total processing finish time are proposed via a deterministic analysis. A stochastic analysis which makes use of Markovian queueing theory is introduced for the case when arrival and departure times of the background jobs are not known     

Task allocation and reallocation for fault tolerance inmulticomputer systems

The goal of task allocation in a set of interconnected processors (computers) is to maximize the efficient use of resources and thus reduce the job turnaround time. Proposed is a simple yet effective method to allocate the tasks in multicomputer systems for minimizing the interprocessor communication cost subject to resource limitations defined by the system and designer. The limitations can be viewed as results from the load balancing since the execution time of each task, the number of available processors, processor speed, and memory capacity are known to the system or designer. As the number of processors increases, the probability of a failure existing somewhere in the systems at any time also increases. Very few established task allocation models have considered the reliability property. In multicomputer systems, we define system reliability as the probability that the system can run the tasks successfully. After the (nonredundant) task scheduling strategy is defined, tasks are then reallocated to processors statically and redundantly. This is a form of time redundancy, in which if some processors fail during the execution, all tasks can be completed on the remaining processors (but at a longer time). Due to static preallocation of tasks this method is simpler and thus more practical than well-known dynamic reconfiguration and rollback recovery techniques in multicomputer systems. We demonstrate the effectiveness of the task allocation and reallocation for hardware fault tolerance by illustrations of applying the methods to different examples and practical communications network multiprocessor system     

Signature search time evaluation in flat file databases

For the first time, divisible load scheduling theory is used to solve for the expected time for searching for both single and multiple signatures in certain multiple processor database architectures. The target architectures examined for illustrative purposes are linear daisy chains and single level tree networks with single and multiple installment load distribution. The use of divisible load modeling and analysis yields elegant expressions for expected search time.     

实时测控分布式系统的容错调度算法研究

根据目标系统的体系结构和功能分布特性以及实时性要求,文章提出了一种混合式实时容错调度算法,该算法对系统中服务器机组和工作站机组的任务分别实施对称式调度和以处理机负载平衡为目标的调度。当系统执行过程中检测到处理机故障,通过双机切换和冗余任务动态唤醒的办法进行系统重构,实现了目标系统硬实时和软实时共存的容错需求。     

Optimal scheduling of parallel tasks of tracking problem ontomultiprocessors

The optimal scheduling of the tasks of a multitarget tracking problem onto multiprocessors to minimize the schedule length is considered. The main impediments of the recent A* algorithm for optimal scheduling of the tasks of this problem, the space and time requirements, are reduced using three new techniques, viz. processor isomorphism, duplicated node deletion, and lower bound on completion time. The effectiveness of these techniques is analyzed and demonstrated with the above real-time critical problem     

面向无人机蜂群的航电云多层任务调度模型

在航空作战体系中，基于航电云的无人机（UAV）蜂群作战是提高未来无人机综合作战能力的一种新模式。针对无人机蜂群作战的航电云架构，如何将云端作战任务派发到无人机且保证作战任务完成时间是其中关键。在无人机蜂群分层分簇网络结构和模块级资源虚拟化的基础上，对传统单层平台级任务调度模型进行改进，提出了一种细化到模块级的多层任务调度模型，将作战任务从云端逐层调度到无人机功能模块上执行。利用OMNeT++对无人机蜂群多层任务调度模型以及传统的单层任务调度模型分别进行仿真，云端以攻击使命组为例构建使命组集进行分配，并对任务吞吐量、消息平均端到端延时和任务完成时间进行性能对比。仿真结果表明：与平台级单层任务调度相比，在执行任务方面，模块级多层任务调度模型将单个任务平均完成时间降低了46.2%，将使命组完成时间降低了52.1%，在保证任务吞吐量的基础上具有对复杂任务更稳定的调度能力；在网络性能方面，模块级多层任务调度模型消息端到端延时更低，延时分布更集中，提高了网络消息传输的实时性。     

基于二维资源管理的多功能雷达任务调度算法

动态孔径分割技术为相控阵雷达针对不同任务灵活分配孔径资源提供了可能,而传统的资源调度方法仅基于单一孔径条件研究了时间资源的优化分配问题。针对雷达搜索、跟踪与成像任务的自适应调度问题,提出了一种基于时间-孔径二维资源管理的雷达资源调度算法。该算法建立了雷达孔径分割条件下的二维资源调度模型,确立了能量资源约束条件;利用基于压缩感知的稀疏孔径逆合成孔径雷达（ISAR）成像技术,使雷达在完成目标搜索和跟踪任务的同时实现对目标的成像;定义了调度算法性能的评价指标。在仿真实验中将该算法与另外2种算法进行对比,验证了所提算法在高度成功率、二维资源利用率与任务并行度这3种性能指标上具有优越性。     

Wireless sensor networks: scheduling for measurement and data reporting

An optimal load allocation approach is presented for measurement and data reporting in wireless sensor networks with a single level tree network topology. The measurement problem investigated involves a measurement space, part of which can be sampled by each sensor. We seek to optimally assign sensors part of the measurement space to minimize reporting time and energy usage. Three representative measurement and reporting strategies are studied. This work is novel as it considers, for the first time, the measurement capacity of processors and assumes negligible computation time which is radically different from the traditional divisible load scheduling research to date. Aerospace applications include satellite remote sensing and monitoring and sensor networks deployed and monitored from the air.     

基于Transformer层次预测的多星应急观测任务规划方法

应急观测任务规划是一个强时效性的复杂组合优化问题,必须在规定的时限内完成相应的计算。采用机器学习的方法对规划问题进行初始规划方案预测,可以有效地简化计算复杂度。为此,提出一种基于Transformer层次预测的多星应急观测任务规划方法,将多星任务规划的求解过程分解为3个步骤：首先,利用基于Transformer的任务可调度性预测模型预测待规划任务是否执行,得到预执行任务集合;然后,基于Transformer的任务分配模型对预执行任务集合分配卫星,得到初始规划方案;最后,利用基于随机爬山的约束修正算法对初始规划方案进行优化调整,得到可行规划方案。为验证所提方法的有效性,通过大量仿真实验与CPLEX优化器、标准遗传算法、长短期记忆网络等方法模型进行比较,实验结果表明所提方法计算耗时短,规划收益高,适用于多星观测任务快速规划。     

一类适用于多星测控调度问题的模型及求解算法

多星测控调度是一个复杂的NP—hard问题,其模型和算法的研究一直是求解的关键和难点。本文从组合优化角度对问题进行描述,建立了多星测控调度问题的数学模型,并利用启发式调度算法予以求解。最后,将算法应用于一个6站10星的调度问题,进行了数值仿真研究。仿真表明,算法能在较短时间内求得任务支持率高且资源使用相对均衡的解,具有较好的寻优能力。     

串件拼修对策下两级备件维修供应系统动态管理模型

 在备件维修供应系统日常运作中,通过对库存和维修资源分配进行动态管理,能够在现有库存配置方案下提高保障效能。针对串件拼修对策下两级维修供应系统,分别建立了有限维修资源约束下多维修渠道故障件的送修和库存分配动态管理模型。根据备件库存动态分析模型(Dyna-METRIC)原理,建立了保障系统的蒙特卡罗仿真模型,并将动态管理模型嵌入其中。使用传统先到先服务(FCFS)原则和指定可用度目标确定不同初始库存配置方案,将这些方案作为仿真模型输入进行仿真试验。结果表明,采用本文模型后保障系统效能相比传统FCFS原则有了明显提高,证明了模型的正确性。     

Brazil uses fuel cells to supplement utility power

Growing electric loads and the dearth of new power plants have created severe worldwide power shortages, as well as a crisis in the nation of Brazil. Analysis and modeling has shown that the crisis could be relieved in a fast and practical manner by placing fuel cells at optimum locations and carefully scheduling their operation. Acquiring the needed data for the model and optimizing the model took a lot of effort. For example, the time when the peak load occurs varies among the types of power consumers. In some residential neighborhoods of Brazil, the peak load occurs when people shower with electrically-heated water. There the fuel cells can be best located where their heat losses can be used to heat water.     

基于基排序的推力矢量飞机控制分配方法

为了解决推力矢量战机存在的执行机构冗余和气动/矢量操纵面协调控制问题,基于过驱动控制理论及控制分配理论, 提出一种基于基排序的操纵面调度管理分配算法。综合推力矢量飞机各型操纵面的物理特性差异、转矩可达集大小、推力矢量工 作时间限制等因素,划分基控制组。采用优先级为主气动控制组、辅助气动控制组、推力矢量控制组的3级串接链分配构型,按指 令幅值依序调度各级操纵面。结果表明：算法分配过程清晰灵活,飞行控制品质优良,对飞行任务与操纵面故障适应性强,可保证 战机高效完成各项任务。相较于传统伪逆方案,新算法在典型“眼镜蛇”机动过程中,削减矢量偏转工作时长超50%,降低最大偏 转角超3°。该算法可规避传统分配方法无差别调度气动/矢量操纵面的缺陷,优化推力矢量启用时间,有效解决飞机操纵能力扩 展与矢量装置寿命平衡的矛盾。     

基于多分区操作系统的多核确定性调度方法设计

为提高多分区操作系统环境下多核处理器的应用带来的操作系统任务调度的确定性,研究了多分环境下多核操作系统结构,从处理器核心和分区的资源分配和分区调度表的时间同步角度出发,采用了静态配置、处理器绑定和时间窗口调度方法,实现了处理器资源的确定性分配,解决了调度表之间的时间同步问题。测试结果表明,方法有效提高了分区环境下多核操作系统任务调度的确定性。     

一种新的并行测试任务调度算法

 并行测试的任务优化调度是并行测试技术的核心问题。为了解决现有调度方法耗时、实际应用范围有限以及缺少对资源冲突和系统死锁的形式化分析等问题,采用赋时有色Petri网(TCPN)建立并行测试任务调度的TCPN模型,基于TCPN模型的可达标识图利用改进蚁群算法求解最优任务调度序列。算法搜索过程中,采用多目标优化,目标函数综合了测试时间、仪器成本和负载平衡度,使得算法更符合工程应用。采用动态标注方法在搜索过程中加大可行解间的信息素差别,避免算法早熟。仿真实例证明该算法是有效的。     

Processor equivalence for daisy chain load sharing processors

A linear daisy chain of processors in which processor load is divisible and shared among the processors is examined. It is shown that two or more processors can be collapsed into a single equivalent processor. This equivalence allows a characterization of the nature of the minimal time solution, a simple method to determine when to distribute load for linear daisy chain networks of processors without front end communication subprocessors and closed form expressions for the equivalent processing speed of infinitely large daisy chains of processors     

片间综合化互连时间触发通信调度方法

未来先进的分布式综合化航空电子系统需要实现跨越计算体系结构的信息综合,对微小型智能器件间的综合化互连提出要求。通过构建一种具有开放式接口的芯片间综合化互连结构,提出一种相应的时间触发（TT）通信调度方法。首先建立片间综合化互连模型和时间触发流量传输模型,给出负载均衡的选径方法;随后依据传输路径中各级节点各流量的发送时间偏移量计算流量传输的等待时间可行值,利用遗传算法优化调整各芯片发送端口的调度表相位,更新各流量在发送端口的时间偏移量,缩短最坏情况下的最大等待时间,得到具有全局优化意义的时间触发调度表。与使用Yices等SMT形式化求解器的TT调度表生成方法相比,本方法不会出现长时间不停机而无法判定的问题,且不论对于对称或非对称结构,案例研究表明本方法的可调度规模至少增加30%。此外,以流量传输等待时间占周期的比例作为归一化的传输延迟度量,与既有的基于特征任务的调度方法相比,案例研究表明本方法得到的传输延迟最多仅为后者的2%。     

考虑优先级的交叉口航班汇聚排序问题研究

为了有效地利用航路资源,减少飞行延误总成本,建立了改进的航路交叉口汇聚排序模型。为加快求解速度,分析了影响航班延误成本的因素,给出了权重赋值表,改进了现有算法,并用FCFS算法与改进算法进行了算例分析。仿真结果表明,改进算法通过对交叉口航班各属性赋权值可有效进行优先等级划分,完成时隙分配和航班排序的快速计算。采用改进给出的优化排序策略可减少延误飞行的总成本,具有一定的实用性。     

基于BP神经网络的机场安检旅客流量预测模型

机场安检服务资源智能分配及调度是提高机场旅客服务水平及运营效率的有效途径之一,而准确的机场安检旅客流量预测则是实现机场安检服务资源动态分配及调度的前提。以天津机场安检旅客流量的历史数据为研究对象,利用BP神经网络算法建立机场安检旅客流量预测模型,并将该预测模型通过天津机场实际旅客流量进行验证。结果表明:该基于BP神经网络的机场安检旅客流量预测模型的预测精度可达90%以上,证明其具有较高的预测精度,能很好地应用到机场安检流量预测中,为机场运营者动态调度安检服务资源提供高效的解决方案。