Efficient multinomial selection in simulation

Consider a simulation experiment consisting of v independent vector replications across k systems, where in any given replication one system is selected as the best performer (i.e., it wins). Each system has an unknown constant probability of winning in any replication and the numbers of wins for the individual systems follow a multinomial distribution. The classical multinomial selection procedure of Bechhofer, Elmaghraby, and Morse (Procedure BEM) prescribes a minimum number of replications, denoted as v*, so that the probability of correctly selecting the true best system (PCS) meets or exceeds a prespecified probability. Assuming that larger is better, Procedure BEM selects as best the system having the largest value of the performance measure in more replications than any other system. We use these same v* replications across k systems to form (v*)^k pseudoreplications that contain one observation from each system, and develop Procedure AVC (All Vector Comparisons) to achieve a higher PCS than with Procedure BEM. For specific small-sample cases and via a large-sample approximation we show that the PCS with Procedure AVC exceeds the PCS with Procedure BEM. We also show that with Procedure AVC we achieve a given PCS with a smaller v than the v* required with Procedure BEM. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 459–482, 1998     

Efficient budget allocation strategies for elementary effects method in stochastic simulation

This paper focuses on extending the Morris' elementary effects method (MM) for sensitivity analysis/factor screening originated in the context of deterministic computer experiments to the stochastic simulation setting. Given a fixed simulation budget to expend, the main objective is to provide efficient and accurate estimates of main and interaction (or nonlinear) effects coined by the standard MM for characterizing the importance of each factor, despite the impact of simulation errors. Taking into account both the factor/input sampling uncertainty rooted in MM and the random errors inherent in a stochastic simulation, we develop efficient budget allocation strategies for implementing MM in this new context. Under each strategy proposed, we derive its corresponding optimal budget partition and optimal budget allocation rules. Numerical results corroborate the practical effectiveness of the proposed budget allocation strategies.     

Optimal sample size allocation for tests with multiple levels of stress with extreme value regression

In this article, we discuss the optimal allocation problem in a multiple stress levels life‐testing experiment when an extreme value regression model is used for statistical analysis. We derive the maximum likelihood estimators, the Fisher information, and the asymptotic variance–covariance matrix of the maximum likelihood estimators. Three optimality criteria are defined and the optimal allocation of units for two‐ and k‐stress level situations are determined. We demonstrate the efficiency of the optimal allocation of units in a multiple stress levels life‐testing experiment by using real experimental situations discussed earlier by McCool and Nelson and Meeker. Monte Carlo simulations are used to show that the optimality results hold for small sample sizes as well. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

非对称Colonel Blotto博弈模型下的多信道功率分配抗干扰

针对智能干扰条件下传输速率固定的通信系统多信道功率分配问题,建立了非对称Colonel Blotto博弈模型。在完全信息条件下,推导出了各种功率预算约束下通信方和干扰方的等效单信道最优功率分配策略,进而证明了通信方和干扰方存在唯一混合纳什均衡策略,并求得了纳什均衡收益。基于等效单信道最优功率分布,提出了一种多重扫描直接列元素交换算法,可以快速构建多信道混合功率分配矩阵,且相比于线性规划方法,可适应更多的信道数和更广的功率分布范围。通过数值仿真,验证了所提多信道混合功率分配矩阵构造算法的有效性及多信道功率分配策略的最优性。     

Optimal production and maintenance policy for imperfect production systems

A joint optimization of the production run length and preventive maintenance (PM) policy is studied for a deteriorating production system where the in‐control period follows a general probability distribution with non‐decreasing failure rate. In the literature, the sufficient conditions for the optimality of the equal‐interval PM schedule is explored to derive an optimal production run length and an optimal number of PM actions. Nevertheless, an exhaustive search may arise. In this study, based on the assumption that the conditions for the optimality of the equal‐interval PM schedule hold, we derive some structural properties for the optimal production/PM policy, which increases the efficiency of the solution procedure. These analyses have implications for the practical application of the production/PM model to be more available in practice. A numerical example of gamma shift distribution with non‐decreasing failure rates is used to illustrate the solution procedure, leading to some insight into the management process. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

跑道失效率的一种快速解析近似计算方法

针对现有的跑道失效率计算方法对数据的处理要求很复杂,并且计算效率较低,难以满足实时性要求的不足,提出一种快速的解析近似计算方法,通过有利弹着区的选取以及瞄准点的优化选择,将问题从搜索最小升降窗口转化为求解母弹对有利弹着区的命中概率,免去了搜索升降窗口的计算时间,从而大幅提高了计算效率。仿真结果表明,快速解析近似计算方法计算速度快且满足了精度要求。     

多机协同目标与火力资源分配

在协同空战中,快速正确的空战决策是己方战机少受敌方伤害并取得战争胜利的前提。目标与火力资源分配是决策过程的重要部分。多机空战与单机空战相比有明显的不同,不同之处是面临多个敌方目标,根据我方资源最优分配作战对象和火力,基于遗传算法实现了两种算法的有人无人目标与火力资源分配。仿真结果表明,带有毁伤概率门限的算法既节省火力资源又快速有效。     

弹道导弹防御中拦截弹最优分层配置

多层弹道导弹防御系统在助推段、飞行中段或再入段不同阶段实施拦截,可有效提高系统拦截概率,不同拦截阶段存在拦截弹最优配比问题。为了解决拦截弹道导弹过程中的最优分层配置的问题,本文分别以单层、双层、三层这三种拦截系统为例,通过公式演算和计算机仿真,得出了分段拦截弹道导弹时、不同拦截阶段的拦截弹之间的数量比与整体拦截成功率之间的关系;并提出了整体拦截成功率的概念。经仿真表明,在整体拦截成功率给定的情况下,使用本文所得出的不同拦截段之间所需拦截弹数目之间的最优比,可以最大限度地降低弹道导弹的拦截成本。     

无人机飞行训练资源配置效率的AHP-Arena综合评价方法

为降低传统层次分析法(analytic hierarchy process,AHP)赋权过程主观片面性影响,提出了一种综合AHP与Arena仿真建模技术的无人机训练资源配置效率评价方法。基于飞行训练流程分析,确定了训练资源配置效率影响因素和效率评价指标,建立了层次型综合评价体系,概括了AHP-Arena综合评价步骤。利用Arena建模软件构建训练流程动态仿真系统并验证有效性,采用单变量数值仿真法、均方差决策法完成了影响因素客观赋权,通过线性加权综合法得出综合评价系数,实现资源配置效率评价与方案优选。实例应用说明了该方法的有效性,同时,该方法可推广至其他类似的训练过程中,亦可为其他多因素、多指标评价决策过程提供借鉴。     

Acceleration of the HAP approach for the multifacility location problem

This article considers the problem of locating multiple new facilities to minimize the cost function consisting of the sum of weighted distances among new facilities and between new and existing facilities. The hyperboloid approximate procedure (HAP) is probably the most widely used approach for solving this problem. In this article, an optimality condition for this problem is derived and a method to accelerate the convergence rate of the HAP for the case of Euclidean distances is presented. From the numerical results presented in this article, it can be concluded that the performance of the new algorithm is superior to the performance of the original HAP.     

基于改进蚁群算法的云计算任务调度研究

把改进的蚁群算法应用到云计算任务调度中,通过将任务在虚拟机上的一次分配作为蚂蚁的一次成功搜索,实现了虚拟机的负载均衡和调度时间的优化,提高云计算资源分配的效率。通过在Cloud Sim平台下进行仿真测试,结果显示,改进蚁群算法在负载均衡性能和总的任务调度时间方面均优于基本的蚁群算法。     

Target selection in Lanchester combat: Linear-law attrition process

We develop the solution to a simple problem of target selection in Lanchester combat against two enemy force types each of which undergoes a “linear-law” attrition process. In addition to the Pontryagin maximum principle, the theory of singular extremals is required to solve this problem. Our major contribution is to show how to synthesize the optimal target selection policies from the basic optimality conditions. This solution synthesis methodology is applicable to more general dynamic (tactical) allocation problems. For constant attrition-rate coefficients we show that whether or not changes can occur in target priorities depends solely on how survivors are valued and is independent of the type of attrition process.     

Optimal service‐capacity allocation in a loss system

We consider a loss system with a fixed budget for servers. The system owner's problem is choosing the price, and selecting the number and quality of the servers, in order to maximize profits, subject to a budget constraint. We solve the problem with identical and different service rates as well as with preemptive and nonpreemptive policies. In addition, when the policy is preemptive, we prove the following conservation law: the distribution of the total service time for a customer entering the slowest server is hyperexponential with expectation equal to the average service rate independent of the allocation of the capacity. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 81–97, 2015     

Combined variance reduction techniques in fully sequential selection procedures

In the past several decades, many ranking‐and‐selection (R&S) procedures have been developed to select the best simulated system with the largest (or smallest) mean performance measure from a finite number of alternatives. A major issue to address in these R&S problems is to balance the trade‐off between the effectiveness (ie, making a correct selection with a high probability) and the efficiency (ie, using a small total number of observations). In this paper, we take a frequentist's point of view by setting a predetermined probability of correct selection while trying to reduce the total sample size, that is, to improve the efficiency but also maintain the effectiveness. In particular, in order to achieve this goal, we investigate combining various variance reduction techniques into the fully sequential framework, resulting in different R&S procedures with either finite‐time or asymptotic statistical validity. Extensive numerical experiments show great improvement in the efficiency of our proposed procedures as compared with several existing procedures.     

Continuous-time markov decision processes with nonzero terminal reward

In this article we consider a continuous-time Markov decision process with a denumerable state space and nonzero terminal rewards. We first establish the necessary and sufficient optimality condition without any restriction on the cost functions. The necessary condition is derived through the Pontryagin maximum principle and the sufficient condition, by the inherent structure of the problem. We introduce a dynamic programming approximation algorithm for the finite-horizon problem. As the time between discrete points decreases, the optimal policy of the discretized problem converges to that of the continuous-time problem in the sense of weak convergence. For the infinite-horizon problem, a successive approximation method is introduced as an alternative to a policy iteration method.     

An efficient heuristic for the multi-item newsboy problem with a single constraint

This article treats the problem of determining optimal and approximately optimal order quantities for a multiple-item inventory system subject to a single constraint on space or budget. Although this problem can be solved by the usual method of Lagrange multipliers, we wish to consider a more efficient scheme that requires fewer computations. We provide calculations that compare and contrast four approximation techniques. In particular, we have discovered a method that yields a direct algebraic expression of the problem parameters for allocation and achieves an expected profit within 90% of the optimal in about 90% of the cases tested.     

Allocation of resources of modular sizes with an application to Internet Protocol (IP) address allocation

We consider a resource allocation problem, where resources of different capacities must satisfy multiple demands. The demand sizes and the resource capacities are limited to sizes that are power‐of‐two integers (i.e., 1, 2, 4, 8, …). The cost of the resources exhibit economies‐of‐scale savings, i.e., the cost per capacity unit is smaller for resources with larger capacity. The problem is to select the minimum‐cost set of resources that satisfies the demands, while each of the demands must be assigned to a single resource and the number of selected resources does not exceed a specified upper bound. We present algorithms that take advantage of the special structure of the problem and provide optimal solutions in a negligible computing effort. This problem is important for the allocation of blocks of Internet Protocol (IP) addresses, referred to as subnets. In typical IP networks, subnets are allocated at a large number of nodes. An effective allocation attempts to balance the volume of excess addresses that are not used versus fragmentation of addresses at nodes to too many subnets with a discontinuous range of addresses. Due to the efficiency of the algorithms, they can readily be used as valuable modules in IP address management systems. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Integrated scheduling of loading and transportation with tractors and semitrailers separated

Motivated by some practical applications, we study a new integrated loading and transportation scheduling problem. Given a set of jobs, a single crane is available to load jobs, one by one, onto semitrailers with a given capacity. Loaded semitrailers are assigned to tractors for transportation tasks. Subject to limited resources (crane, semitrailers, and tractors), the problem is to determine (1) an assignment of jobs to semitrailers for loading tasks, (2) a sequence for the crane to load jobs onto semitrailers, (3) an assignment of loaded semitrailers to tractors for transportation tasks, and (4) a transportation schedule of assigned tractors such that the completion time of the last transportation task is minimized. We first formulate the problem as a mixed integer linear programming model (MILPM) and prove that the problem is strongly NP‐hard. Then, optimality properties are provided which are useful in establishing an improved MILPM and designing solution algorithms. We develop a constructive heuristic, two LP‐based heuristics, and a recovering beam search heuristic to solve this problem. An improved procedure for solutions by heuristics is also presented. Furthermore, two branch‐and‐bound (B&B) algorithms with two different lower bounds are developed to solve the problem to optimality. Finally, computational experiments using both real data and randomly generated data demonstrate that our heuristics are highly efficient and effective. In terms of computational time and the number of instances solved to optimality in a time limit, the B&B algorithms are better than solving the MILPM. © 2015 Wiley Periodicals, Inc. Naval Research Logistics 62: 416–433, 2015     

基于理想解法的空中加油机驻地分配选择

一体化联合作战条件下,跨战区、跨军兵种实施空中加油将更加频繁,空中加油机驻地分配选择对空中加油任务的实施有重要影响。分析了影响空中加油机驻地分配选择的主要因素,以此确定决策指标,这是一个多指标综合评价问题。基于理想解法的原理和方法,构建了空中加油机驻地分配选择决策的数学模型。通过示例分析表明,该方法计算简单,较好地解决了空中加油机驻地分配选择问题,并可在此基础上做进一步研究,为实际应用中解决类似问题提供了一种新思路。     

协同通信中的基于信道统计信息的联合中继选择的功率分配

分析Rayleigh信道下分集/无分集的AF( Amplify and Forward)和DF( Decode and Forward)模式单中继传输的平均中断概率,给出解析表达式.在总功率约束下推导了4种模式下的统计最优功率分配的解析表达式来最小化系统的平均中断概率,并提出通过最佳中继选择进一步降低系统的平均中断概率...