A branch‐and‐cut algorithm for the nonpreemptive swapping problem

In the Swapping Problem (SP), we are given a complete graph, a set of object types, and a vehicle of unit capacity. An initial state specifies the object type currently located at each vertex (at most one type per vertex). A final state describes where these object types must be repositioned. In general, there exist several identical objects for a given object type, yielding multiple possible destinations for each object. The SP consists of finding a shortest vehicle route starting and ending at an arbitrary vertex, in such a way that each object is repositioned in its final state. This article exhibits some structural properties of optimal solutions and proposes a branch‐and‐cut algorithm based on a 0‐1 formulation of the problem. Computational results on random instances containing up to 200 vertices and eight object types are reported. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

On the exponentially weighted moving variance

MacGregor and Harris (J Quality Technol 25 (1993) 106–118) proposed the exponentially weighted mean squared deviation (EWMS) and the exponentially weighted moving variance (EWMV) charts as ways of monitoring process variability. These two charts are particularly useful for individual observations where no estimate of variability is available from replicates. However, the control charts derived by using the approximate distributions of the EWMS and EWMV statistics are difficult to interpret in terms of the average run length (ARL). Furthermore, both control charting schemes are biased procedures. In this article, we propose two new control charts by applying a normal approximation to the distributions of the logarithms of the weighted sum of chi squared random variables, which are respectively functions of the EWMS and EWMV statistics. These new control charts are easy to interpret in terms of the ARL. On the basis of the simulation studies, we demonstrate that the proposed charts are superior to the EWMS and EWMV charts and they both are nearly unbiased for the commonly used smoothing constants. We also compare the performance of the proposed charts with that of the change point (CP) CUSUM chart of Acosta‐Mejia (1995). The design of the proposed control charts is discussed. An example is also given to illustrate the applicability of the proposed control charts. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

一种传感器网络时空融合模型

针对多传感器间存在时空相关性和先验知识未知的情况,提出了一种基于核偏最小二乘最优加权的传感器网络时空融合模型。首先用核偏最小二乘法对每个传感器在不同时刻的测量值进行融合,然后将各个传感器同时刻的估计值进行空间最优融合,从而得到被测参量的最终融合估计。该模型还能排除那些取值远离样本点集合平均水平的奇异点。理论分析和融合实验表明,该模型能取得较高的融合精度,并能显著节省网络能量。     

基于MINE-FNA组合算法的防空体系指标网构建方法?

防空作战体系的武器装备组成结构和对抗信息交互具有网络化特征,其作战效能是通过对抗过程中各组分系统间复杂的网络化交互涌现出来的,因此描述体系作战效能的指标也应由各组分系统效能指标相互关联涌现出来,而传统防空体系指标选取方法无法准确描述防空体系内部复杂的关联关系和揭示体系能力的复杂涌现生成机理。因此将无参数探索最大交互信息算法（ MINE）和网络统计算法（ FNA）组合构建了MINE?FNA组合算法模型,对基于武器装备体系仿真试验床的防空体系仿真的全样本实验数据进行深度挖掘,构建了“底层基础指标→均一化指标→体系级指标”的三层防空体系指标网,为研究防空体系内部复杂关联关系和分析防空体系能力的生成机理提供了有效手段。     

基于复杂网络理论的C2组织结构

从复杂网络理论角度,构造出了C2组织结构的网络拓扑模型,并根据C2组织结构的网络特性提出了一个重要的统计特性——节点的重要度,说明节点与其他节点联系的紧密性和重要性,进而分析了C2组织结构网络中的各个统计参数在C2组织结构网络中所具有的现实意义,并基于某个作战想定构建出C2组织结构网络的动态演化过程,更深层次地分析C2组织结构的合理性和高效性,为优化C2组织结构奠定基础。     

基于贝叶斯网络的空中目标威胁估计算法

联合作战条件下,指挥决策人员在海量描述战场态势的数据和信息面前往往会束手无策,无法快速作出正确的决策。贝叶斯网络模型是一种基于概率推理的网络化数学模型,能够通过一些变量的信息来获取其他的概率信息,从而解决不定性和不完整性问题。提出了一种基于贝叶斯网络的空中目标威胁估计算法,用空中威胁网络模型找到空中威胁目标各属性之间的潜在关系,并建立空中目标威胁估计算法,最后以一个实例来验证该空中目标威胁估计的计算过程和有效性。     

On the polyhedral structure of two‐level lot‐sizing problems with supplier selection

In this article, we study a two‐level lot‐sizing problem with supplier selection (LSS), which is an NP‐hard problem arising in different production planning and supply chain management applications. After presenting various formulations for LSS, and computationally comparing their strengths, we explore the polyhedral structure of one of these formulations. For this formulation, we derive several families of strong valid inequalities, and provide conditions under which they are facet‐defining. We show numerically that incorporating these valid inequalities within a branch‐and‐cut framework leads to significant improvements in computation. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 647–666, 2017     

Column generation for stochastic green telecommunication network planning with switchable base stations

We present the green telecommunication network planning problem with switchable base stations, where the location and configuration of the base stations are optimized, while taking into account uncertainty and variability of demand. The problem is formulated as a two‐stage stochastic program under demand uncertainty with integers in both stages. Since solving the presented problem is computationally challenging, we develop the corresponding Dantzig‐Wolfe reformulation and propose a solution approach based on column generation. Comprehensive computational results are provided for instances of varying characteristics. The results show that the joint location and dynamic switching of base stations leads to significant savings in terms of energy cost. Up to 30% reduction in power consumption cost is achieved while still serving all users. In certain cases, allowing dynamic configurations leads to more installed base stations and higher user coverage, while having lower total energy consumption. The Dantzig‐Wolfe reformulation provides solutions with a tight LP‐gap eliminating the need for a full branch‐and‐price scheme. Furthermore, the proposed column generation solution approach is computationally efficient and outperforms CPLEX on the majority of the tested instances. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 351–366, 2016     

Capacity investment decisions under risk aversion

This article studies the optimal capacity investment problem for a risk‐averse decision maker. The capacity can be either purchased or salvaged, whereas both involve a fixed cost and a proportional cost/revenue. We incorporate risk preference and use a consumption model to capture the decision maker's risk sensitivity in a multiperiod capacity investment model. We show that, in each period, capacity and consumption decisions can be separately determined. In addition, we characterize the structure of the optimal capacity strategy. When the parameters are stationary, we present certain conditions under which the optimal capacity strategy could be easily characterized by a static two‐sided (s, S) policy, whereby, the capacity is determined only at the beginning of period one, and held constant during the entire planning horizon. It is purchased up to B when the initial capacity is below b, salvaged down to Σ when it is above σ, and remains constant otherwise. Numerical tests are presented to investigate the impact of demand volatility on the optimal capacity strategy. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 218–235, 2016     

Scheduling parallel machines with inclusive processing set restrictions and job rejection

In this article, we study a parallel machine scheduling problem with inclusive processing set restrictions and the option of job rejection. In the problem, each job is compatible to a subset of machines, and machines are linearly ordered such that a higher‐indexed machine can process all those jobs that a lower‐indexed machine can process (but not conversely). To achieve a tight production due date, some of the jobs might be rejected at certain penalty. We first study the problem of minimizing the makespan of all accepted jobs plus the total penalty cost of all rejected jobs, where we develop a ‐approximation algorithm with a time complexity of . We then study two bicriteria variants of the problem. For the variant problem of minimizing the makespan subject to a given bound on the total rejection cost, we develop a ‐approximation algorithm with a time complexity of . For the variant problem of maximizing the total rejection cost of the accepted jobs subject to a given bound on the makespan, we present a 0.5‐approximation algorithm with a time complexity of . © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 667–681, 2017