双舰编队协同制导防空作战的动态拦截排序问题

针对双舰编队协同制导作战条件下如何对空袭目标进行排序这一问题,依据作战时间给出了排序算法。首先对平台的作战时间进行分析和求解,将射击周期分成了2段,把静态拦截排序问题转化为了2台处理机的同顺序作业排序问题,然后根据输入信息的改变而不断调整空袭目标的顺序以解决动态拦截排序问题,最后在想定条件下仿真计算,结果表明该算法具有较好的适用性。     

多计算机系统中的容错任务分配和再分配

在一组互连处理机(计算机)中任务分配的目的是使资源的有效使用最大化,并由此而减少作业的解题周期。本文提出的在多计算机系统中分配任务的简单而有效的方法旨在系统和设计者确定的资源限制条件下,使处理机间的通信成本最小。因为每个任务的执行时间、可用处理机数目、处理机速度和存储容量对系统或设计者来说是已知的,因此,限制可看作为是由负载平衡引起的。随着处理机数目的增加,在任何时间在系统某处出现故障的概率也随之增加。几乎没有已建立的任务分配模型考虑了可靠性性质。在多计算机系统中,我们定义系统可靠性为系统可成功地运行任务的概率。在确定(非冗余)任务调度策略以后,任务静态和冗余地再分配给处理机。这是一种时间冗余形式,在这种形式中,如果在执行期间某些处理机故障,那么所有任务可以在剩余的处理机上(但以更长的时间)完成。由于是任务的静态预分配,这种方法比众所周知的多计算机系统中的动态再配置和滚回恢复技术更简单,因此也更实际。通过把该方法应用于不同的例子和实际的通信网络多处理机系统,我们验证了硬件容错任务分配和再分配的有效性。     

一种稳健的特征空间线性约束波束形成器

基于特征空间的线性约束最小方差(eigenspace-based linearly constrained minimum variance,ELCMV)算法是一种稳健的波束形成方法,但其性能只能在一定的指向误差范围内保持稳定,当指向误差较大而使期望信号落在预设波束主瓣边缘时,其性能会严重恶化。对ELCMV算法进行改进,提出一种对零点约束方向和指向误差都具有稳健性的波束形成方法。该方法首先利用矢量旋转对预设导向矢量进行校正,再将校正后的导向矢量向信号子空间投影,最后结合线性约束用线性约束最小方差(linearly constrained minimum variance,LCMV)算法来求解权矢量。计算机仿真证实了该方法的有效性。     

航天器调度中的资源约束推理方法

资源水平边界的估计是构建资源利用可行计划中的一个基础问题。通过分析航天器资源约束的共享与分离并存、累积与瞬时消耗并存、过度订阅与区间调度并存等特点,提出了资源时间网络、时间约束网络和约束网络相结合的资源约束描述方法;构建了增量式基于包络的资源约束算法和最早开始时间链展开资源约束算法,以快速获取资源一致的柔性解。实例证明,该方法较好地解决了航天器调度的资源约束推理问题。     

多约束多关联条件下的目标选择

处理了如何从具有复杂关联和多种约束的目标集中选择目标的问题。首先,对目标集的组成结构和目标间的相互关联关系进行了描述,并分析了目标选择的两种约束类型,建立了多约束多关联条件下的目标选择模型。然后使用惩罚函数将多约束目标选择问题转化为无约束问题,给出了用遗传算法求解模型的方法步骤。最后通过案例表明,该方法结果稳定,优化效果好,能够在目标间具有复杂关联的条件下为军事人员进行目标选择决策提供有效的辅助。     

基于弹药挂载工作的舰载机保障作业调度

针对弹药挂载工作下舰载机保障作业问题,分析了弹药挂载作业与舰载机其他保障作业的约束关系,并基于保障资源约束,以舰载机保障作业完成时间和负载方差最小化为优化目标,建立了考虑弹药挂载工作下的保障作业调度模型。通过设计基于保障工序优先级的染色体片段编码方式,避免了大量不可行解的产生,提出了一种改进的NSGA-Ⅱ算法。以国外某型航母为例进行仿真分析,验证了模型与算法所得调度方案的可行性。     

622机的微程序设计

一、概述 622集成电路电子计算机(以下简称622机),是一台字长为16位的定点小型多功能通用机。 622机指令系统和DJS—130机具有兼容性,130机的所有程序系统均能在622机上运行。不同的是,622机具有乘除法指令,并且增加了六种控制台指令。这六种指令用来逐门诊断运算器的故障,检测内存,自动输入十四条二进制初始引导程序,以及用来调试机器指令。中央处理机由微程序控制器和运算器组成。它通过存贮器总线与存贮器连接,通过输入——输出总线与外部设备连接。处理机中有四个通用累加器,其中两个可做变址寄存器用。     

短波自动链路建立性能分析与优化设计

文章在分析2G-ALE建链流程的基础上,建立了平均建链概率和平均建链时间性能指标数学模型,依据此模型分析了信道扫描速率以及引导呼叫的长度对平均建链时间的影响。通过仿真比较了两种信道驻留时间的优化方案,结果表明在差信道条件下适当降低信道扫描速率可以减少平均建链时间。指标模型和仿真分析对于ALE系统的设计优化具有一定的参考意义。     

自适应光学波前实时处理机结构设计

本文介绍的波前处理机是１．２ｍ望远镜自适应光学系统的关键部件之一,吞吐率高,延时小,是具有高速数据处理能力的实时处理系统。为满足系统的高速度性能,系统设计在实时性、并发性的基础上,将图象数据采集加入流水线,并对波前处理中自然存在的子任务作“去相关”’处理,建立了图象采集、斜率计算、波前复原间流水线操作。图象读出时间的利用及流水线的建立,大大减少了时延,降低了系统实时性要求。流水线处理与高度并行处理相结合,也是本处理机设计的一大特色。     

分类的向量化算法

本文讨论在具有K台处理机的并行计算机上分类N个元素的一种并行算法,如果K=[N/2]台处理,则需要0((log_2N)~2)步,并且给出一个(1/2(log_2N)~2 1/2log_2N)步的算法。     

Open shop scheduling to minimize the number of late jobs

We develop polynomial algorithms for several cases of the NP-hard open shop scheduling problem of minimizing the number of late jobs by utilizing some recent results for the open shop makespan problem. For the two machine common due date problem, we assume that either the machines or the jobs are ordered. For the m machine common due date problem, we assume that one machine is maximal and impose a restriction on its load. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 525–532, 1998     

Flow‐shop batch scheduling with identical processing‐time jobs

In many practical situations of production scheduling, it is either necessary or recommended to group a large number of jobs into a relatively small number of batches. A decision needs to be made regarding both the batching (i.e., determining the number and the size of the batches) and the sequencing (of batches and of jobs within batches). A setup cost is incurred whenever a batch begins processing on a given machine. This paper focuses on batch scheduling of identical processing‐time jobs, and machine‐ and sequence‐independent setup times on an m‐machine flow‐shop. The objective is to find an allocation to batches and their schedule in order to minimize flow‐time. We introduce a surprising and nonintuitive solution for the problem. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004     

Scheduling target illuminators in naval battle-group anti-air warfare

We schedule a set of illuminators (homing devices) to strike a set of targets using surface-to-air missiles in a naval battle. The task is viewed as a production floor shop scheduling problem of minimizing the total weighted flow time, subject to time-window job availability and machine downtime side constraints. A simple algorithm based on solving assignment problems is developed for the case when all the job processing times are equal and the data are all integer. For the general case of scheduling jobs with unequal processing times, we develop two alternate formulations and analyze their relative strengths by comparing their respective linear programming relaxations. We select the better formulation in this comparison and exploit its special structures to develop several effective heuristic algorithms that provide good-quality solutions in real time; this is an essential element for use by the Navy. © 1995 John Wiley & Sons, Inc.     

Scheduling for parallel dedicated machines with a single server

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule is N P‐hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst‐case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two‐machine flow shop and the open shop problems with a single server are also shown to be N P‐hard in the strong sense. However, we reduce the two‐machine flow shop no‐wait problem with a single server to the Gilmore—Gomory traveling salesman problem and solve it in polynomial time. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 304–328, 2000     

On equivalence between the proportionate flow shop and single‐machine scheduling problems

We derive sufficient conditions which, when satisfied, guarantee that an optimal solution for a single‐machine scheduling problem is also optimal for the corresponding proportionate flow shop scheduling problem. We then utilize these sufficient conditions to show the solvability in polynomial time of numerous proportionate flow shop scheduling problems with fixed job processing times, position‐dependent job processing times, controllable job processing times, and also problems with job rejection. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 595–603, 2015     

Transporting jobs through a two‐machine open shop

We consider the two‐machine open shop scheduling problem in which the jobs are brought to the system by a single transporter and moved between the processing machines by the same transporter. The purpose is to split the jobs into batches and to find the sequence of moves of the transporter so that the time by which the completed jobs are collected together on board the transporter is minimal. We present a ‐approximation algorithm. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Efficient algorithms for flexible job shop scheduling with parallel machines

Job shop scheduling with a bank of machines in parallel is important from both theoretical and practical points of view. Herein we focus on the scheduling problem of minimizing the makespan in a flexible two-center job shop. The first center consists of one machine and the second has k parallel machines. An easy-to-perform approximate algorithm for minimizing the makespan with one-unit-time operations in the first center and k-unit-time operations in the second center is proposed. The algorithm has the absolute worst-case error bound of k − 1 , and thus for k = 1 it is optimal. Importantly, it runs in linear time and its error bound is independent of the number of jobs to be processed. Moreover, the algorithm can be modified to give an optimal schedule for k = 2 .     

Scheduling jobs,with exponentially distributed processing times,on two machines of a flow shop

This paper treats the problem of sequencing n jobs on two machines in a “flow shop.” (That is, each job in the shop is required to flow through the same sequence of the machines.) The processing time of a given job on a given machine is assumed to be distributed exponentially, with a known mean. The objective is to minimize the expected job completion time. This paper proves an optimal ordering rule, previously conjectured by Talwar [10]. A formula is also derived through Markov Chain analysis, which evaluates the expected job completion time for any given sequence of the jobs. In addition, the performance of a heuristic rule is discussed in the light of the optimal solution.     

Two machine flow shop scheduling problems with sequence dependent setup times: A dynamic programming approach

This paper considers the two different flow shop scheduling problems that arise when, in a two machine problem, one machine is characterized by sequence dependent setup times. The objective is to determine a schedule that minimizes makespan. After establishing the optimally of permutation schedules for both of these problems, an efficient dynamic programming formulation is developed for each of them. Each of these formulations is shown to be comparable, from a computational standpoint, to the corresponding formulation of the traveling salesman problem. Then, the relative merits of the dynamic programming and branch and bound approaches to these two scheduling problems are discussed.     

The two-machine permutation flow shop with state-dependent processing times

If the processing time of each job in a flow shop also depends on the time spent prior to processing, then the choice of a sequence influences processing times. This nonstandard scheduling problem is studied here for the minimum makespan schedule in a flow shop with two machines. The problem is NP-hard in the strong sense and already contains the main features of the general case [10]. Restricting to the case of permutation schedules, we first determine the optimal release times of the jobs for a given sequence. Permutation schedules are evaluated for this optimal policy, and the scheduling problem is solved using branch-and-bound techniques. We also show the surprising result that the optimal schedule may not be a permutation schedule. Numerical results on randomly generated data are provided for permutation schedules. Our numerical results confirm our preliminary study [10] that fairly good approximate solutions can efficiently be obtained in the case of limited computing time using the heuristics due to Gilmore and Gomory [7]. © 1993 John Wiley & Sons, Inc.