What you should know about approximate dynamic programming

Approximate dynamic programming (ADP) is a broad umbrella for a modeling and algorithmic strategy for solving problems that are sometimes large and complex, and are usually (but not always) stochastic. It is most often presented as a method for overcoming the classic curse of dimensionality that is well‐known to plague the use of Bellman's equation. For many problems, there are actually up to three curses of dimensionality. But the richer message of approximate dynamic programming is learning what to learn, and how to learn it, to make better decisions over time. This article provides a brief review of approximate dynamic programming, without intending to be a complete tutorial. Instead, our goal is to provide a broader perspective of ADP and how it should be approached from the perspective of different problem classes. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

Approximation algorithms for general one‐warehouse multi‐retailer systems

Logistical planning problems are complicated in practice because planners have to deal with the challenges of demand planning and supply replenishment, while taking into account the issues of (i) inventory perishability and storage charges, (ii) management of backlog and/or lost sales, and (iii) cost saving opportunities due to economies of scale in order replenishment and transportation. It is therefore not surprising that many logistical planning problems are computationally difficult, and finding a good solution to these problems necessitates the development of many ad hoc algorithmic procedures to address various features of the planning problems. In this article, we identify simple conditions and structural properties associated with these logistical planning problems in which the warehouse is managed as a cross‐docking facility. Despite the nonlinear cost structures in the problems, we show that a solution that is within ε‐optimality can be obtained by solving a related piece‐wise linear concave cost multi‐commodity network flow problem. An immediate consequence of this result is that certain classes of logistical planning problems can be approximated by a factor of (1 + ε) in polynomial time. This significantly improves upon the results found in literature for these classes of problems. We also show that the piece‐wise linear concave cost network flow problem can be approximated to within a logarithmic factor via a large scale linear programming relaxation. We use polymatroidal constraints to capture the piece‐wise concavity feature of the cost functions. This gives rise to a unified and generic LP‐based approach for a large class of complicated logistical planning problems. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

基于任意分布随机Petri网的装备维修保障建模与分析

通过将任意分布随机Petri网的基本理论和算法应用到装备维修保障的建模与分析,建立了维修保障系统的任意随机Petri网模型,实现了随机Petri网中变换概率服从指数分布的限制.根据实际系统中相关数据的统计分析和经验估计,以便为利用矩姆函数分析方法对维修保障系统的性能进行分析,为维修保障决策层提供参考,获得了一些有价值的性能指标信息.     

自行火炮扭力轴载荷谱的测量及疲劳寿命预测

为预测自行火炮扭力轴寿命,对某型自行火炮在不同工况下进行实车试验,获得了多工况下扭力轴的载荷谱。受力分析表明,表面最大拉应力是扭力轴的破坏应力;提出基于随机响应面对扭力轴寿命进行预测的方法,将低周疲劳寿命表达式中的随机参数表示为标准随机变量,引人随机响应的Hermite多项展开式进行拟合,建立了扭力轴疲劳寿命的显式函数。通过对实测载荷谱进行统计分析,依据寿命表达式可以预测扭力轴疲劳寿命,并给出概率分布。该方法弥补了传统响应面法以一般多项式拟合时不能保证收敛性的缺陷。     

采用SHLPN分析特种车载总线网络可靠性

针对特种车载总线网络可靠性难以评估的问题,提出采用随机高级Petri网(Stochastic High-level Petri Net,SHLPN)分析特种车载总线网络可靠性。深入分析特种车载总线网络故障模式的基础上,将其等效为冗余总线控制器模块、远程终端模块和冗余链路模块的串联,分别建立各个模块的SHLPN模型,得到了各个模块的稳态可用度计算式,进而综合得到特种车载总线网络的稳态可用度计算式。最后,实例分析验证了所提方法的有效性。     

The probability of the existence of a feasible flow in a stochastic transportation network

Stochastic transportation networks arise in various real world applications, for which the probability of the existence of a feasible flow is regarded as an important performance measure. Although the necessary and sufficient condition for the existence of a feasible flow represented by an exponential number of inequalities is a well‐known result in the literature, the computation of the probability of all such inequalities being satisfied jointly is a daunting challenge. The state‐of‐the‐art approach of Prékopa and Boros, Operat Res 39 (1991) 119–129 approximates this probability by giving its lower and upper bounds using a two‐part procedure. The first part eliminates all redundant inequalities and the second gives the lower and upper bounds of the probability by solving two well‐defined linear programs with the inputs obtained from the first part. Unfortunately, the first part may still leave many non‐redundant inequalities. In this case, it would be very time consuming to compute the inputs for the second part even for small‐sized networks. In this paper, we first present a model that can be used to eliminate all redundant inequalities and give the corresponding computational results for the same numerical examples used in Prékopa and Boros, Operat Res 39 (1991) 119–129. We also show how to improve the lower and upper bounds of the probability using the multitree and hypermultitree, respectively. Furthermore, we propose an exact solution approach based on the state space decomposition to compute the probability. We derive a feasible state from a state space and then decompose the space into several disjoint subspaces iteratively. The probability is equal to the sum of the probabilities in these subspaces. We use the 8‐node and 15‐node network examples in Prékopa and Boros, Operat Res 39 (1991) 119–129 and the Sioux‐Falls network with 24 nodes to show that the space decomposition algorithm can obtain the exact probability of these classical examples efficiently. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 479–491, 2016     

On the application and extension of system signatures in engineering reliability

Following a review of the basic ideas in structural reliability, including signature‐based representation and preservation theorems for systems whose components have independent and identically distributed (i.i.d.) lifetimes, extensions that apply to the comparison of coherent systems of different sizes, and stochastic mixtures of them, are obtained. It is then shown that these results may be extended to vectors of exchangeable random lifetimes. In particular, for arbitrary systems of sizes m < n with exchangeable component lifetimes, it is shown that the distribution of an m‐component system's lifetime can be written as a mixture of the distributions of k‐out‐of‐n systems. When the system has n components, the vector of coefficients in this mixture representation is precisely the signature of the system defined in Samaniego, IEEE Trans Reliabil R–34 (1985) 69–72. These mixture representations are then used to obtain new stochastic ordering properties for coherent or mixed systems of different sizes. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Scheduling parallel machines with inclusive processing set restrictions

We consider the problem of assigning a set of jobs to different parallel machines of the same processing speed, where each job is compatible to only a subset of those machines. The machines can be linearly ordered such that a higher‐indexed machine can process all those jobs that a lower‐indexed machine can process. The objective is to minimize the makespan of the schedule. This problem is motivated by industrial applications such as cargo handling by cranes with nonidentical weight capacities, computer processor scheduling with memory constraints, and grades of service provision by parallel servers. We develop an efficient algorithm for this problem with a worst‐case performance ratio of + ε, where ε is a positive constant which may be set arbitrarily close to zero. We also present a polynomial time approximation scheme for this problem, which answers an open question in the literature. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

微弱正弦信号在有噪声的FN神经元模型中的传输特性研究

长期以来弄清神经系统中的信号是如何传输的一直是广大研究人员努力的目标.针对一种被普遍研究的神经元简化模型--FitzHugh-nagumo(FN)模型,采用二阶随机龙格-库塔算法分析了该模型对加性噪声和微弱正弦信号的响应特性.时域和频域的统计参数表明适当强度的噪声有利于信号的传输,存在随机共振现象,即与噪声强度关联的输出信噪比曲线为倒钟形;另外值得关注的是,与正弦信号频率关联的输出信噪比曲线也为倒钟形,分析可见正弦信号的无量纲频率在区间0.2～0.8时模型的输出信噪比最大,表明该神经元模型有频率敏感性,即更易于检测到该范围内的弱信号.上述结果与生物学的发现是一致的,将有助于进一步揭示周期信号在神经元中的传输方法,建立更加准确的神经元数学模型.     

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