An approximate dynamic programing approach to the development of heuristics for the scheduling of impatient jobs in a clearing system

A single server is faced with a collection of jobs of varying duration and urgency. Each job has a random lifetime during which it is available for nonpreemptive service. Should a job's lifetime expire before its service begins then it is lost from the system unserved. The goal is to schedule the jobs for service to maximize the expected number served to completion. Two heuristics have been proposed in the literature. One (labeled π^S) operates a static priority among the job classes and works well in a “no premature job loss” limit, whereas the second (π^M) is a myopic heuristic which works well when lifetimes are short. Both can exhibit poor performance for problems at some distance from the regimes for which they were designed. We develop a robustly good heuristic by an approximative approach to the application of a policy improvement step to the asymptotically optimal heuristic π^S, in which we use a fluid model to obtain an approximation for the value function of π^S. The performance of the proposed heuristic is investigated in an extensive numerical study. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 2010     

A stochastic approximation algorithm to compute bid prices for joint capacity allocation and overbooking over an airline network

In this article, we develop a stochastic approximation algorithm to find good bid price policies for the joint capacity allocation and overbooking problem over an airline network. Our approach is based on visualizing the total expected profit as a function of the bid prices and searching for a good set of bid prices by using the stochastic gradients of the total expected profit function. We show that the total expected profit function that we use is differentiable with respect to the bid prices and derive a simple expression that can be used to compute its stochastic gradients. We show that the iterates of our stochastic approximation algorithm converge to a stationary point of the total expected profit function with probability 1. Our computational experiments indicate that the bid prices computed by our approach perform significantly better than those computed by standard benchmark strategies and the performance of our approach is relatively insensitive to the frequency with which we recompute the bid prices over the planning horizon. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Signature based analysis of m‐Consecutive‐k‐out‐of‐n: F systems with exchangeable components

In this article, we study reliability properties of m‐consecutive‐k‐out‐of‐n: F systems with exchangeable components. We deduce exact formulae and recurrence relations for the signature of the system. Closed form expressions for the survival function and the lifetime distribution as a mixture of the distribution of order statistics are established as well. These representations facilitate the computation of several reliability characteristics of the system for a given exchangeable joint distribution or survival function. Finally, we provide signature‐based stochastic ordering results for the system's lifetime and investigate the IFR preservation property under the formulation of m‐consecutive‐k‐out‐of‐n: F systems. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Improving series and parallel systems through mixtures of duplicated dependent components

We discuss suitable conditions such that the lifetime of a series or of a parallel system formed by two components having nonindependent lifetimes may be stochastically improved by replacing the lifetimes of each of the components by an independent mixture of the individual components' lifetimes. We also characterize the classes of bivariate distributions where this phenomenon arises through a new weak dependence notion. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Annealing adaptive search,cross‐entropy,and stochastic approximation in global optimization

The Annealing Adaptive Search (AAS) algorithm for global optimization searches the solution space by sampling from a sequence of Boltzmann distributions. For a class of optimization problems, it has been shown that the complexity of AAS increases at most linearly in the problem dimension. However, despite its desirable property, sampling from a Boltzmann distribution at each iteration of the algorithm remains a practical challenge. Prior work to address this issue has focused on embedding Markov chain‐based sampling techniques within the AAS framework. In this article, based on ideas from the recent Cross‐Entropy method and Model Reference Adaptive Search, we propose an algorithm, called Model‐based Annealing Random Search (MARS), that complements prior work by sampling solutions from a sequence of surrogate distributions that iteratively approximate the target Boltzmann distributions. We establish a novel connection between MARS and the well‐known Stochastic Approximation method. By exploiting this connection, we prove the global convergence of MARS and characterize its asymptotic convergence rate behavior. Our empirical results indicate promising performance of the algorithm in comparison with some of the existing methods. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

云模型和混合Petri网相结合的系统可靠性评价

针对复杂系统可靠性评价中工作环境可变的情形,提出基于云模型和混合Petri网相结合的可靠性评价方法。首先采用云模型描述系统的环境适应能力指数,并将其作为混合Petri模型中连续库所的托肯值来控制该模型中变迁的变迁率,然后采用基于Petri网的蒙特卡罗方法对不同环境下的系统可靠性进行仿真求解,得到系统在不同时刻下的失效率。最后以一个C4ISR系统为例,验证了该方法在解决可变工作环境下的系统可靠性评估是可行的。     

低信噪比下融合随机共振的运动目标检测算法

为提高智能视频监控系统中运动目标检测算法在低信噪比条件下的鲁棒性,结合混合高斯背景建模算法和随机共振原理实现一种低信噪比下的运动目标检测算法。算法根据混合高斯背景模型对当前帧生成目标概率灰度图,在本文定义的性能评价函数下,通过向该概率灰度图添加噪声使得评价函数最优化从而达到随机共振,对该随机共振灰度图进行阈值分割得到输出的检测目标。针对昏暗、大雾和红外视频分别进行了实验,证实了本文算法的有效性同时也显示本文算法相对于普通背景差算法性能获得了明显提升。     

基于Monte Carlo方法的一对二马尔可夫随机格斗模型

讨论了一对二马尔可夫随机格斗双方获胜概率计算问题。提出了一种新颖的一对二马尔可夫随机格斗任意对抗回合双方获胜概率的计算方法,该方法首先基于Monte Carlo仿真计算各个对抗回合中双方发射次序的概率分布,再利用全概率公式确定马尔可夫链的状态转移概率矩阵,从而克服了马尔可夫随机格斗模型往往只能提供无限对抗回合之后格斗双方获胜概率的缺点,为运用马尔可夫随机格斗研究火力运用和弹药分配提供了新途径,并用实例说明了该方法的有效性。     

基于GERT的武器装备维修备件订货间隔期预测

由于武器装备维修备件的需求是随机波动的,订货间隔期的准确预测就成为了一个难点。针对这样一个随机波动的需求系统,提出了利用GERT随机网络模型对其进行描述,进而求出随机波动需求的订货间隔期的解析表达式,解决了不确定性需求的订货间隔期的预测问题,为武器装备维修备件的科学管理提供数据支持。通过实例验证表明,GERT随机网络模型是解决武器装备维修备件订货间隔期的一种有效手段和方法。     

基于GSPN的编队网络化防空指挥流程研究

为了提高编队指挥员在信息化海战中的作战指挥效率和应变能力,利用广义随机Petri网与马尔可夫链的等价关系,得到一种Petri网与马尔可夫链理论相结合的指挥流程时间性能分析的新方法,通过对模型进行分析与求解,得出了舰艇编队网络化防空作战指挥流程活动的准确作战周期,从而为指挥流程的优化提供有力的支撑,对评估系统效能水平也具有重要指导意义。