The joint signature of coherent systems

We investigate the joint signature of $m$ coherent systems, under the assumption that the components have independent and identically distributed lifetimes. The joint signature, for a particular ordering of failure times, is an $m$‐dimensional matrix depending solely on the composition of the systems and independent of the underlying distribution function of the component lifetimes. The elements of the $m$‐dimensional matrix are formulated based on the joint signatures of numerous series of parallel systems. The number of the joint signatures involved is an exponential function of the number of the minimal cut sets of each original system and may, therefore, be significantly large. We prove that although this number is typically large, a great number of the joint signatures are repeated, or removed by negative signs. We determine the maximum number of different joint signatures based on the number of systems and components. It is independent of the number of the minimal cut sets of each system and is polynomial in the number of components. Moreover, we consider all permutations of failure times and demonstrate that the results for one permutation can be of use for the others. Our theorems are applied to various examples. The main conclusion is that the joint signature can be computed much faster than expected.     

I.I.D.并行分布式检测网相同门限假定的合理性条件

并行分布式检测网最优设计是复杂难解的,相同门限假定使Ｉ．Ｉ．Ｄ．网的设计极度简化,并在实际工程中广泛使用。本文研究了相同门限假定的合理性条件,为合理采用习惯性处理方法提供了理论依据。     

The parallel replacement problem with demand and capital budgeting constraints

A generalized parallel replacement problem is considered with both fixed and variable replacement costs, capital budgeting, and demand constraints. The demand constraints specify that a number of assets, which may vary over time, are required each period over a finite horizon. A deterministic, integer programming formulation is presented as replacement decisions must be integer. However, the linear programming relaxation is shown to have integer extreme points if the economies of scale binary variables are fixed. This allows for the efficient computation of large parallel replacement problems as only a limited number of 0–1 variables are required. Examples are presented to provide insight into replacement rules, such as the “no‐splitting‐rule” from previous research, under various demand scenarios. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 40–56, 2000     

Scheduling a maintenance activity on parallel identical machines

We study a problem of scheduling a maintenance activity on parallel identical machines, under the assumption that all the machines must be maintained simultaneously. One example for this setting is a situation where the entire system must be stopped for maintenance because of a required electricity shut‐down. The objective is minimum flow‐time. The problem is shown to be NP‐hard, and moreover impossible to approximate unless P = NP. We introduce a pseudo‐polynomial dynamic programming algorithm, and show how to convert it into a bicriteria FPTAS for this problem. We also present an efficient heuristic and a lower bound. Our numerical tests indicate that the heuristic provides in most cases very close‐to‐optimal schedules. © 2008 Wiley Periodicals, Inc. Naval Research Logistics 2009     

基于内外子区域划分的高阶精度CFD程序异构并行算法

对计算流体力学(CFD)程序CNS提出一种Offload模式下基于内外子区域划分的异构并行算法,结合结构化网格下有限差分计算和四阶龙格库塔方法的特点,引入ghost网格点区域,设计了一种ghost区域收缩计算策略,显著降低了异构计算资源之间的数据传输开销,负载均衡时CPU端的计算与MPI通信完全和加速器端的计算重叠,提高了异构协同并行性。推导了保证计算正确性的ghost区域的参数,分析了负载均衡的条件。在“CPU(Intel Haswell Xeon E5-2670 12 cores ×2)＋加速器(Xeon Phi 7120A ×2)”的服务器上测得该算法较直接将任务子块整体迁至加速器端计算的异构算法性能平均提升5.9倍,较MPI/OpenMP两级并行算法使用24个纯CPU核的性能,该算法使用单加速器时加速1.27倍,使用双加速器加速1.45倍。讨论和分析了性能瓶颈与存在的问题。     

海洋环境监测平行系统优化融合

多个海洋环境监测系统之间存在的功能冗余导致资源浪费和不必要的资金投入,因此应将各个系统优化融合成有机整体来节约海洋环境监测的资源和成本。将海洋环境监测系统按照功能划分为不同的模块,在线性规划融合的基础上引入熵方法,以成本和效能指标为主要对象,通过合理分配,在确保系统优化融合后监测能力不降低的同时,尽量减少建设成本。     

On competitive analysis for polling systems

Polling systems have been widely studied, however most of these studies focus on polling systems with renewal processes for arrivals and random variables for service times. There is a need driven by practical applications to study polling systems with arbitrary arrivals (not restricted to time-varying or in batches) and revealed service time upon a job's arrival. To address that need, our work considers a polling system with generic setting and for the first time provides the worst-case analysis for online scheduling policies in this system. We provide conditions for the existence of constant competitive ratios, and competitive lower bounds for general scheduling policies in polling systems. Our work also bridges the queueing and scheduling communities by proving the competitive ratios for several well-studied policies in the queueing literature, such as cyclic policies with exhaustive, gated or l-limited service disciplines for polling systems.     

Scheduling parallel dedicated machines with the speeding‐up resource

We consider a problem of scheduling jobs on m parallel machines. The machines are dedicated, i.e., for each job the processing machine is known in advance. We mainly concentrate on the model in which at any time there is one unit of an additional resource. Any job may be assigned the resource and this reduces its processing time. A job that is given the resource uses it at each time of its processing. No two jobs are allowed to use the resource simultaneously. The objective is to minimize the makespan. We prove that the two‐machine problem is NP‐hard in the ordinary sense, describe a pseudopolynomial dynamic programming algorithm and convert it into an FPTAS. For the problem with an arbitrary number of machines we present an algorithm with a worst‐case ratio close to 3/2, and close to 3, if a job can be given several units of the resource. For the problem with a fixed number of machines we give a PTAS. Virtually all algorithms rely on a certain variant of the linear knapsack problem (maximization, minimization, multiple‐choice, bicriteria). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

JPEG2000遥感图像实时压缩系统中基于并行机制的“零时间”数据搬移策略

为了满足JPEG2000遥感图像实时压缩设备的实时性要求,提出了一种基于并行机制的“零时间”数据搬移策略。通过对EBC算法结构进行拆分,并采用EDMA方式进行数据搬移,使得算法运算与数据搬移过程完全并行,搬移时间等效为零。实验结果表明,采用新的数据搬移策略后,编码效率可以提升到100％,EBC算法实现的总时间可缩短46％以上。该搬移机制已成功应用于JPEG2000星载遥感图像实时压缩系统中,系统的实时性达到了设计要求。     

中远距协同空战多目标攻击决策

根据先进战斗机的技术特点和中远距协同空战发展方向,提出一种基于先敌发现、先敌发射、先敌摧毁能力的空战态势分析模型。同时,将并行遗传算法与分布估计算法相结合的并行分布遗传算法应用于上述模型,给出了求解多目标攻击决策问题的算法。最后利用具体算例进行仿真验证。结果表明空战态势分析模型能够较为准确地描述中远距多机协同空战,采用的算法具有较好的可行性和实时性,为中远距多机协同空战的多目标攻击决策提供了新的思路和方法。