卫星任务调度问题的约束规划模型

卫星任务规划与调度是空间资源管理的重要内容之一,其目的在于为卫星系统的任务计划编制提供科学合理的决策手段与依据。卫星任务调度问题的重要特点在于,调度任务存在可见时间窗口约束。只有在可见时间窗口内,调度任务才可能执行并完成。在进行合理假设的基础上,建立卫星任务调度问题的约束规划模型。对基本禁忌搜索算法进行改进,提出了模型求解的变邻域禁忌搜索算法。应用结果表明,约束规划模型的建立与求解是合理的。     

Integrating decisions with advance supply information in an assemble-to-order system

We study a periodic-review assemble-to-order (ATO) system with multiple components and multiple products, in which the inventory replenishment for each component follows an independent base-stock policy and stochastic product demands are satisfied according to a First-Come-First-Served rule. We assume that the replenishment for various component suffers from lead time uncertainty. However, the decision maker has the so-called advance supply information (ASI) associated with the lead times and thus can take advantage of the information for system optimization. We propose a multistage stochastic integer program that incorporates ASI to address the joint optimization of inventory replenishment and component allocation. The optimal base-stock policy for the inventory replenishment is determined using the sample average approximation algorithm. Also, we provide a modified order-based component allocation (MOBCA) heuristic for the component allocation. We additionally consider a special case of the variable lead times where the resulting two-stage stochastic programming model can be characterized as a single-scenario case of the proposed multistage model. We carry out extensive computational studies to quantify the benefits of integrating ASI into joint optimization and to explore the possibility of employing the two-stage model as a relatively efficient approximation scheme for the multistage model.     

On efficient algorithms for finding efficient salvo policies

We consider the salvo policy problem, in which there are k moments, called salvos, at which we can fire multiple missiles simultaneously at an incoming object. Each salvo is characterized by a probability p_i: the hit probability of a single missile. After each salvo, we can assess whether the incoming object is still active. If it is, we fire the missiles assigned to the next salvo. In the salvo policy problem, the goal is to assign at most n missiles to salvos in order to minimize the expected number of missiles used. We consider three problem versions. In Gould's version, we have to assign all n missiles to salvos. In the Big Bomb version, a cost of B is incurred when all salvo's are unsuccessful. Finally, we consider the Quota version in which the kill probability should exceed some quota Q. We discuss the computational complexity and the approximability of these problem versions. In particular, we show that Gould's version and the Big Bomb version admit pseudopolynomial time exact algorithms and fully polynomial time approximation schemes. We also present an iterative approximation algorithm for the Quota version, and show that a related problem is NP-complete.     

Application of Markov renewal theory and semi-Markov decision processes in maintenance modeling and optimization of multi-unit systems

In this paper, a condition-based maintenance model for a multi-unit production system is proposed and analyzed using Markov renewal theory. The units of the system are subject to gradual deterioration, and the gradual deterioration process of each unit is described by a three-state continuous time homogeneous Markov chain with two working states and a failure state. The production rate of the system is influenced by the deterioration process and the demand is constant. The states of the units are observable through regular inspections and the decision to perform maintenance depends on the number of units in each state. The objective is to obtain the steady-state characteristics and the formula for the long-run average cost for the controlled system. The optimal policy is obtained using a dynamic programming algorithm. The result is validated using a semi-Markov decision process formulation and the policy iteration algorithm. Moreover, an analytical expression is obtained for the calculation of the mean time to initiate maintenance using the first passage time theory.     

信息中心网络缓存节点位置选择算法

信息中心网络（Information-Centric Networking, ICN）“泛在缓存”的特性,引发数据副本率过高、缓存空间不能充分利用等问题。为了解决上述问题,分别从用户、服务提供商和网络运营商的角度出发,以最小化网络流量与网络费用开销为优化目标建立两个单目标优化模型,并将二者结合为帕累托模型;基于帕累托求解方法中数学规划法的思想,详细描述缓存节点位置选择算法。仿真结果表明：在流量性价比方面,所提缓存节点选择算法优于ICN的默认缓存机制;在网络费用开销方面,所提算法更适用于只有少数内容较为流行的网络中,而在所有内容都流行的情况下,ICN中默认的“遍地缓存”机制更为适宜。     

Adjacency‐based local top‐down search method for finding maximal efficient faces in multiple objective linear programming

It is well‐known that the efficient set of a multiobjective linear programming (MOLP) problem can be represented as a union of the maximal efficient faces of the feasible region. In this paper, we propose a method for finding all maximal efficient faces for an MOLP. The new method is based on a condition that all efficient vertices (short for the efficient extreme points and rays) for the MOLP have been found and it relies on the adjacency, affine independence and convexity results of efficient sets. The method uses a local top‐down search strategy to determine maximal efficient faces incident to every efficient vertex for finding maximal efficient faces of an MOLP problem. To our knowledge, the proposed method is the first top‐down search method that uses the adjacency property of the efficient set to find all maximal efficient faces. We discuss this and other advantages and disadvantages of the algorithm. We also discuss some computational experience we have had with our computer code for implementing the algorithm. This computational experience involved solving several MOLP problems with the code.     

A multi‐stage stochastic programming approach for network capacity expansion with multiple sources of capacity

In networks, there are often more than one sources of capacity. The capacities can be permanently or temporarily owned by the decision maker. Depending on the nature of sources, we identify the permanent capacity, spot market capacity, and contract capacity. We use a scenario tree to model the uncertainty, and build a multi‐stage stochastic integer program that can incorporate multiple sources and multiple types of capacities in a general network. We propose two solution methodologies for the problem. Firstly, we design an asymptotically convergent approximation algorithm. Secondly, we design a cutting plane algorithm based on Benders decomposition to find tight bounds for the problem. The numerical experiments show superb performance of the proposed algorithms compared with commercial software. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 600–614, 2017     

基于双层规划的通信干扰兵力部署优化

投掷式通信干扰机是未来通信对抗装备发展的一种趋势,针对其压制无线战术通信的兵力部署优化问题,引入"通信干扰压制概率"和"通信干扰效益"两个指标,建立了基于双层规划的兵力部署优化模型,上层规划以整体通信干扰效益最大化为目标,下层为随机机会约束规划,以通信干扰压制概率满足一定置信水平为约束,以干扰机需求量最小化为目标。采用随机模拟、遗传算法和动态规划相结合的混合智能算法求解双层规划模型,并通过算例分析验证了模型的有效性。     

带优先级的单类型航空弹药转运多目标规划模型

针对航母航空弹药转运过程非常复杂、涉及设备多、要求高的特点,在对其流程进行细致分析的基础上,将其抽象为一个两阶段多目标规划问题。同时,深入分析了转运过程中的各种约束条件、构建了该问题的两阶段优化模型。建模时,不仅考虑了武器升降机的有效利用、弹药量的合理分配等因素,还考虑了转运时对于不同类型弹药转运优先级与停机区弹药需求优先级的要求。通过模型优化,在满足转运优先级要求的基础上,能有效提高航空弹药的转运效率。     

基于多Agent无人机协同侦察任务规划模型

建立了多无人机协同侦察任务规划模型,在考虑侦察时间间隔约束和目标载荷需求基础上,给出了位于不同基地的无人机优化部署和调度策略,并提出了基于多Agent的优化搜索仿真算法,利用Matlab实现了无人机优化配置和任务规划模型,得出了无人机优化配置和任务规划方案,最后分析了模型算法存在的某些不足,提出了模型改进的方向。