A worst‐case formulation for constrained ranking and selection with input uncertainty

In this research, we consider robust simulation optimization with stochastic constraints. In particular, we focus on the ranking and selection problem in which the computing time is sufficient to evaluate all the designs (solutions) under consideration. Given a fixed simulation budget, we aim at maximizing the probability of correct selection (PCS) for the best feasible design, where the objective and constraint measures are assessed by their worst‐case performances. To simplify the complexity of PCS, we develop an approximated probability measure and derive the asymptotic optimality condition (optimality condition as the simulation budget goes to infinity) of the resulting problem. A sequential selection procedure is then designed within the optimal computing budget allocation framework. The high efficiency of the proposed procedure is tested via a number of numerical examples. In addition, we provide some useful insights into the efficiency of a budget allocation procedure.     

Capacitated lot‐sizing and scheduling with parallel machines,back‐orders,and setup carry‐over

We address the capacitated lot‐sizing and scheduling problem with setup times, setup carry‐over, back‐orders, and parallel machines as it appears in a semiconductor assembly facility. The problem can be formulated as an extension of the capacitated lot‐sizing problem with linked lot‐sizes (CLSPL). We present a mixed integer (MIP) formulation of the problem and a new solution procedure. The solution procedure is based on a novel “aggregate model,” which uses integer instead of binary variables. The model is embedded in a period‐by‐period heuristic and is solved to optimality or near‐optimality in each iteration using standard procedures (CPLEX). A subsequent scheduling routine loads and sequences the products on the parallel machines. Six variants of the heuristic are presented and tested in an extensive computational study. © 2009 Wiley Periodicals, Inc. Naval Research Logistics 2009     

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     

基于微惯导随机误差时间序列建模的改进组合导航方法

针对低精度、低成本微机电惯性测量单元随机误差建模效果不理想会极大影响组合导航性能的难题,采用时间序列分析方法建立了微机电惯性测量单元随机误差的自回归滑动平均模型,通过对卡尔曼滤波器的状态变量进行增广,建立系统动力学方程和观测方程,实现对零偏误差的在线估计。实测数据分析验证了该随机误差建模的有效性。实测数据处理结果表明,该方法能够显著提高低成本微惯性解算外推精度,增强微惯性/卫星组合导航可靠性。     

面向点及区域目标的遥感卫星任务调度

遥感应用需求中存在点目标和区域目标两类任务,遥感卫星对两类任务的调度方式存在很大区别,将二者统一调度困难.本文将点目标视为特殊的区域目标,将它们按照卫星观测机会分解,构建元任务,将两类目标在元任务层次进行统一;根据任务类型分别构建收益函数,兼顾了二者在收益计算上的差异,并建立了面向点及区域目标的遥感卫星任务调度模型,实现了对两类任务的综合调度.仿真实例证明,此方法能够提高卫星的观测效率.     

支持并行工程的造船分段作业计划系统

针对传统造船模式下,车间作业计划与工艺设计串行工作方式的缺点,基于并行工程的原理,提出了分段作业计划与工艺设计的集成运行模式,为实现造船CAPP系统与PPC系统的集成化和并行化提供了实现的基础。针对集成模式的特点,建立了分段作业计划系统资源优化的数学模型,应用遗传算法解决了针对任意分段装配工艺方案的多资源平衡优化问题,可以得到每项作业最优的开工时间,同时能够给出多种资源的最优分布结果,满足了多工艺方案之间资源利用率的比较。最后,给出了计算实例,计算机模拟结果说明了这一方法的有效性。     

带时间窗的相控阵雷达实时任务调度方法

为了解决传统相控阵雷达任务调度中采用基于工作方式优先级的方法而存在忽略任务时间紧迫性和重要性的问题,提出了一种基于任务自身工作方式优先级、截止期和空闲时间3个特征参数的相控阵雷达任务调度方法,通过调整参数的权重来适应调度器不同的负载情况,并采用时间窗处理发生冲突的任务请求,确保更多的高优先级任务在调度间隔内被调度。仿真结果表明,所提出的方法能够有效提高任务的调度成功率,明显改善调度器性能。     

Solving partially observable agent‐intruder games with an application to border security problems

In this paper, we introduce partially observable agent‐intruder games (POAIGs). These games model dynamic search games on graphs between security forces (an agent) and an intruder given possible (border) entry points and high value assets that require protection. The agent faces situations with dynamically changing, partially observable information about the state of the intruder and vice versa. The agent may place sensors at selected locations, while the intruder may recruit partners to observe the agent's movement. We formulate the problem as a two‐person zero‐sum game, and develop efficient algorithms to compute each player's optimal strategy. The solution to the game will help the agent choose sensor locations and design patrol routes that can handle imperfect information. First, we prove the existence of ?‐optimal strategies for POAIGs with an infinite time horizon. Second, we introduce a Bayesian approximation algorithm to identify these ?‐optimal strategies using belief functions that incorporate the imperfect information that becomes available during the game. For the solutions of large POAIGs with a finite time horizon, we use a solution method common to extensive form games, namely, the sequence form representation. To illustrate the POAIGs, we present several examples and numerical results.     

Inventory policies for a make‐to‐order system with a perishable component and fixed ordering cost

We consider a make‐to‐order production system where two major components, one nonperishable (referred to as part 1) and one perishable (part 2), are needed to fulfill a customer order. In each period, replenishment decisions for both parts need to be made jointly before demand is realized and a fixed ordering cost is incurred for the nonperishable part. We show that a simple (s_n,S,S) policy is optimal. Under this policy, S along with the number of backorders at the beginning of a period if any and the availability of the nonperishable part (part 1) determines the optimal order quantity of the perishable part (part 2), while (s_n,S) guide when and how much of part 1 to order at each state. Numerical study demonstrates that the benefits of using the joint replenishment policy can be substantial, especially when the unit costs are high and/or the profit margin is low. © 2009 Wiley Periodicals, Inc. Naval Research Logistics, 2009     

匈牙利算法在多目标分配中的应用

在多目标攻击决策中 ,根据 Harold提出的目标优势函数 ,分析了使所有目标机的总优势函数为指派问题 ,运用匈牙利算法对 n对 n的最优目标分配指派问题进行求解 ,并把它推广至 n对 m的多目标分配中。仿真结果表明匈牙利算法对于此类多目标分配指派问题的求解是十分有效的。