图论中独立支配集的最佳求解算法研究

通过对图论中独立集和支配集的深入研究,提出了独立支配集的概念,论证了独立支配集同极大独立集及极小支配集之间的内在联系,并在此基础上给出了独立支配集的最佳求解算法,从而圆满地解决了图论中独立集及支配集的求解问题,对图的着色及匹配等问题的研究均有相当重要的借鉴意义。     

Stochastic regret minimization for revenue management problems with nonstationary demands

We study an admission control model in revenue management with nonstationary and correlated demands over a finite discrete time horizon. The arrival probabilities are updated by current available information, that is, past customer arrivals and some other exogenous information. We develop a regret‐based framework, which measures the difference in revenue between a clairvoyant optimal policy that has access to all realizations of randomness a priori and a given feasible policy which does not have access to this future information. This regret minimization framework better spells out the trade‐offs of each accept/reject decision. We proceed using the lens of approximation algorithms to devise a conceptually simple regret‐parity policy. We show the proposed policy achieves 2‐approximation of the optimal policy in terms of total regret for a two‐class problem, and then extend our results to a multiclass problem with a fairness constraint. Our goal in this article is to make progress toward understanding the marriage between stochastic regret minimization and approximation algorithms in the realm of revenue management and dynamic resource allocation. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 433–448, 2016     

New purification algorithms for linear programming

Two new algorithms are presented for solving linear programs which employ the opposite-sign property defined for a set of vectors in m space. The first algorithm begins with a strictly positive feasible solution and purifies it to a basic feasible solution having objective function value no less under maximization. If this solution is not optimal, then it is drawn back into the interior with the same objective function value, and a restart begins. The second algorithm can begin with any arbitrary feasible point. If necessary this point is purified to a basic feasible solution by dual-feasibility–seeking directions. Should dual feasibility be attained, then a duality value interval is available for estimating the unknown objective function value. If at this juncture the working basis is not primal feasible, then further purification steps are taken tending to increase the current objective function value, while simultaneously seeking another dual feasible solution. Both algorithms terminate with an optimal basic solution in a finite number of steps.     

Luenberger观测器与LADRC在稳瞄系统中的应用

针对稳瞄系统的性能有一定改进空间,而对象机械特性又改善受限的问题,试图从电气控制角度寻求更好的解决方法。为此,以某上反稳瞄系统为平台,对Luenberger观测器和LADRC(线性自抗扰控制器)两种能提高系统性能的先进控制算法进行了半实物仿真研究。首先,介绍了Luenberger观测器和LADRC的基本原理。其次,对某上反稳瞄系统的对象特性进行了分析,设计了基于两种控制模型的控制器参数。然后,运用MATLAB/Simulink工具和d SPACE半实物仿真系统,对某上反稳瞄系统进行了两种控制算法的对比研究。Luenberger观测器的控制性能相对较好,受噪声的影响,离工程实现还有一段距离。如何有效抑制噪声有待进一步研究。     

A new polynomial algorithm for maximum value flow with an efficient parallel implementation

A new algorithm is presented for finding maximal and maximum value flows in directed single-commodity networks. Commonly algorithms developed for this problem find a maximal flow by gradually augmenting (increasing) a feasible flow to a maximal flow. In the presented algorithm, at the beginning of each step or iteration, the flow on arcs is assigned to flow capacity. This may lead to an infeasible flow violating flow conservation at some nodes. During two passes of a MAIN step, consisting of a forward pass and a backward pass, the flow is reduced on some arcs to regain feasibility. The network is then pruned by omitting saturated arcs, and the process is repeated. The parallel implementation of the algorithm applies the two main steps at the same time to the same network. The outputs of the two steps are compared and the processing continues with the higher feasible flow. The algorithm is simple, intuitive, and efficient. © 1993 John Wiley & Sons, Inc.     

面向多最优解组合优化问题的决策求解算法

针对具有固定物品总和、多最优解特征的组合优化问题,以固定总和实数子集问题和购买鸡翅问题为例,给出了这类多最优解组合优化问题的形式化表示。在分析枚举等经典算法基础上,提出了基于整数状态表示和实数状态表示的0-1决策递归搜索多最优解动态规划算法。针对该算法在最优解数量较大时,时间复杂度趋向O(mⁿ)的问题,提出了基于相同决策路径合并和基于0-x决策的两种改进算法。实验中两种改进算法的计算时间基本符合与O(nb+nm)的正比关系,表明对于这类多最优解组合优化问题具有良好的求解性能。     

投掷式通信干扰机的战斗任务级效能评估模型

针对投掷式通信干扰机战斗任务级效能评估不足的问题,在分析其典型作战任务的基础上,提出了战斗任务级效能指标——压制概率,依据对空域、频域、时域的覆盖要求,建立了压制概率的评估数学模型,进行了典型作战任务下压制概率的实例分析,分析结果表明:该指标及模型能比较准确地反应通信发射机与任务区域的相对位置、干扰机排布样式、干扰机数量等因素对投掷式通信干扰机战斗任务级效能的影响.     

被动声纳浮标目标运动分析及其仿真计算

针对直升机搜索潜艇的特点,研究了被动声纳浮标目标运动分析问题。对固定目标和匀速直线运动目标,分别应用确定性计算和线性最小二乘法进行数学建模及其仿真。仿真结果表明该模型可行,能对被动式声纳浮标搜潜的目标定位提供算法依据。     

Hyperbolic integer programming

The hyperbolic integer program is treated as a special case of a hyperbolic program with a finite number of feasible points. The continuous hyperbolic program also belongs to this class since its solution can be obtained by considering only the extreme points of the feasible set. A general algorithm for solving the hyperbolic integer program which reduces to solving a sequence of linear integer problems is proposed. When the integer restriction is removed, this algorithm is similar to the Isbell-Marlow procedure. The geometrical aspects of the hyperbolic problem are also discussed and several cutting plane algorithms are given.     

Short‐term capacity allocation problem with tool and setup constraints

We consider a short‐term capacity allocation problem with tool and setup constraints that arises in the context of operational planning in a semiconductor wafer fabrication facility. The problem is that of allocating the available capacity of parallel nonidentical machines to available work‐in‐process (WIP) inventory of operations. Each machine can process a subset of the operations and a tool setup is required on a machine to change processing from one operation to another. Both the number of tools available for an operation and the number of setups that can be performed on a machine during a specified time horizon are limited. We formulate this problem as a degree‐constrained network flow problem on a bipartite graph, show that the problem is NP‐hard, and propose constant factor approximation algorithms. We also develop constructive heuristics and a greedy randomized adaptive search procedure for the problem. Our computational experiments demonstrate that our solution procedures solve the problem efficiently, rendering the use of our algorithms in real environment feasible. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Relaxation method for the solution of the minimax location-allocation problem in euclidean space

A method previously devised for the solution of the p-center problem on a network has now been extended to solve the analogous minimax location-allocation problem in continuous space. The essence of the method is that we choose a subset of the n points to be served and consider the circles based on one, two, or three points. Using a set-covering algorithm we find a set of p such circles which cover the points in the relaxed problem (the one with m < n points). If this is possible, we check whether the n original points are covered by the solution; if so, we have a feasible solution to the problem. We now delete the largest circle with radius r_p (which is currently an upper limit to the optimal solution) and try to find a better feasible solution. If we have a feasible solution to the relaxed problem which is not feasible to the original, we augment the relaxed problem by adding a point, preferably the one which is farthest from its nearest center. If we have a feasible solution to the original problem and we delete the largest circle and find that the relaxed problem cannot be covered by p circles, we conclude that the latest feasible solution to the original problem is optimal. An example of the solution of a problem with ten demand points and two and three service points is given in some detail. Computational data for problems of 30 demand points and 1–30 service points, and 100, 200, and 300 demand points and 1–3 service points are reported.     

Scheduling with centralized and decentralized batching policies in concurrent open shops

This article considers batch scheduling with centralized and decentralized decisions. The context of our study is concurrent open shop scheduling where the jobs are to be processed on a set of independent dedicated machines, which process designated operations of the jobs in batches. The batching policy across the machines can be centralized or decentralized. We study such scheduling problems with the objectives of minimizing the maximum lateness, weighted number of tardy jobs, and total weighted completion time, when the job sequence is determined in advance. We present polynomial time dynamic programming algorithms for some cases of these problems and pseudo‐polynomial time algorithms for some problems that are NP‐hard in the ordinary sense. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 58: 17–27, 2011     

Capacity expansion and cost efficiency improvement in the warehouse problem

The warehouse problem with deterministic production cost, selling prices, and demand was introduced in the 1950s and there is a renewed interest recently due to its applications in energy storage and arbitrage. In this paper, we consider two extensions of the warehouse problem and develop efficient computational algorithms for finding their optimal solutions. First, we consider a model where the firm can invest in capacity expansion projects for the warehouse while simultaneously making production and sales decisions in each period. We show that this problem can be solved with a computational complexity that is linear in the product of the length of the planning horizon and the number of capacity expansion projects. We then consider a problem in which the firm can invest to improve production cost efficiency while simultaneously making production and sales decisions in each period. The resulting optimization problem is non‐convex with integer decision variables. We show that, under some mild conditions on the cost data, the problem can be solved in linear computational time. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 367–373, 2016     

An improved algorithm for the dynamic lot-sizing problem with learning effect in setups

The dynamic lot-sizing problem with learning in setups is a variation of the Wagner-Whitin lot-sizing problem where the setup costs are a concave, nondecreasing function of the cumulative number of setups. This problem has been a subject of some recent research. We extend the previously studied model to include nonstationary production costs and present an O(T²) algorithm to solve this problem. The worst-case complexity of our algorithm improves the worst-case behavior of the algorithms presently known in the literature. © 1993 John Wiley & Sons, Inc.     

反导指挥决策的拦截可行性建模

反导已成为现代防空作战的首要任务,而拦截可行性分析是反导指挥决策的重要环节。对弹道导弹目标与飞机目标不同点进行了分析,针对弹道导弹目标的弹道特点深入研究了反导拦截的空间、时间、武器约束条件,建立了反导拦截可行性的数学模型,并给出了实现反导拦截可行性模型的软件算法。通过实际应用表明此方法是切实可行的。     

改进遗传算法在传声器阵列优化中的应用

规则平面阵列因其结构周期性,在进行波束综合时存在主瓣宽、旁瓣电平高等问题。对此,提出一种基于改进遗传算法的阵列优化方法。设计平面栅格传声器阵列,以满足阵元间距的要求,并构造以主瓣宽度为约束条件、以全局旁瓣电平为适应度的目标函数,对常规遗传算法进行改进,采取个体间自由交叉、随机的阵元数量强制变异的策略来增大种群的搜索范围。通过仿真,得到多个优化阵列,与几种规则平面阵列相比,在不同的信噪比输入下,经过改进遗传算法优化得到的随机阵列均有更好的表现。而相比于几种常规的优化算法,改进的遗传算法具有更强的搜索能力,得到数量更多、性能更优的随机阵列,由此证明了所提方法的可行性。     

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     

Hybrid heuristics for minimum cardinality set covering problems

Minimum cardinality set covering problems (MCSCP) tend to be more difficult to solve than weighted set covering problems because the cost or weight associated with each variable is the same. Since MCSCP is NP-complete, large problem instances are commonly solved using some form of a greedy heuristic. In this paper hybrid algorithms are developed and tested against two common forms of the greedy heuristic. Although all the algorithms tested have the same worst case bounds provided by Ho [7], empirical results for 60 large randomly generated problems indicate that one algorithm performed better than the others.     

基于脊线相似性的指纹三角形匹配算法

指纹匹配算法是指纹准确识别的关键算法之一。在常见的三角形匹配算法的基础上,提出了一种改进的基于脊线相似性的三角形匹配算法。在对指纹预处理图像进行八邻域特征提取后,利用脊线的相似性选择特征点进行三角形匹配,在一定程度上减少了相似三角形的个数,提高了匹配速度与精度。实验证明,本算法取得了良好的识别效果。     

Maintenance scheduling for modular systems: Modeling and algorithms

We study new models of scheduled maintenance management for modular systems, consisting of multiple components with respective cycle limits. The cycle limit of each component specifies the time interval in which this component must be repaired or replaced. The goal is to compute a feasible maintenance schedule that minimizes the cost associated with component maintenance. Applications of these models arise in Air Force aircraft maintenance as well as in other arenas with required preventive maintenance. The typical cost structures that arise in practical settings are submodular, which make the resulting models computationally challenging. We develop two efficient and operationally tenable approximation algorithms. We prove constant factor worst‐case guarantees for both algorithms, and present computational experiments showing that these algorithms perform within a few percent of optimality on operationally relevant instances. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 472–488, 2014