A branch‐and‐bound‐based solution approach for dynamic rerouting of airborne platforms

This article is a sequel to a recent article that appeared in this journal, “An extensible modeling framework for dynamic reassignment and rerouting in cooperative airborne operations” [ 17 ], in which an integer programming formulation to the problem of rescheduling in‐flight assets due to changes in battlespace conditions was presented. The purpose of this article is to present an improved branch‐and‐bound procedure to solve the dynamic resource management problem in a timely fashion, as in‐flight assets must be quickly re‐tasked to respond to the changing environment. To facilitate the rapid generation of attractive updated mission plans, this procedure uses a technique for reducing the solution space, supports branching on multiple decision variables simultaneously, incorporates additional valid cuts to strengthen the minimal network constraints of the original mathematical model, and includes improved objective function bounds. An extensive numerical analysis indicates that the proposed approach significantly outperforms traditional branch‐and‐bound methodologies and is capable of providing improved feasible solutions in a limited time. Although inspired by the dynamic resource management problem in particular, this approach promises to be an effective tool for solving other general types of vehicle routing problems. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013     

Route optimization for multiple searchers

We consider a discrete time‐and‐space route‐optimization problem across a finite time horizon in which multiple searchers seek to detect one or more probabilistically moving targets. This article formulates a novel convex mixed‐integer nonlinear program for this problem that generalizes earlier models to situations with multiple targets, searcher deconfliction, and target‐ and location‐dependent search effectiveness. We present two solution approaches, one based on the cutting‐plane method and the other on linearization. These approaches result in the first practical exact algorithms for solving this important problem, which arises broadly in military, rescue, law enforcement, and border patrol operations. The cutting‐plane approach solves many realistically sized problem instances in a few minutes, while existing branch‐and‐bound algorithms fail. A specialized cut improves solution time by 50[percnt] in difficult problem instances. The approach based on linearization, which is applicable in important special cases, may further reduce solution time with one or two orders of magnitude. The solution time for the cutting‐plane approach tends to remain constant as the number of searchers grows. In part, then, we overcome the difficulty that earlier solution methods have with many searchers. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Path optimization for the resource‐constrained searcher

We formulate and solve a discrete‐time path‐optimization problem where a single searcher, operating in a discretized three‐dimensional airspace, looks for a moving target in a finite set of cells. The searcher is constrained by maximum limits on the consumption of one or more resources such as time, fuel, and risk along any path. We develop a specialized branch‐and‐bound algorithm for this problem that uses several network reduction procedures as well as a new bounding technique based on Lagrangian relaxation and network expansion. The resulting algorithm outperforms a state‐of‐the‐art algorithm for solving time‐constrained problems and also is the first algorithm to solve multi‐constrained problems. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Approximation results for min‐max path cover problems in vehicle routing

This article studies a min‐max path cover problem, which is to determine a set of paths for k capacitated vehicles to service all the customers in a given weighted graph so that the largest path cost is minimized. The problem has wide applications in vehicle routing, especially when the minimization of the latest service completion time is a critical performance measure. We have analyzed four typical variants of this problem, where the vehicles have either unlimited or limited capacities, and they start from either a given depot or any depot of a given depot set. We have developed approximation algorithms for these four variants, which achieve approximation ratios of max{3 ‐ 2/k,2}, 5, max{5 ‐ 2/k,4}, and 7, respectively. We have also analyzed the approximation hardness of these variants by showing that, unless P = NP , it is impossible for them to achieve approximation ratios less than 4/3, 3/2, 3/2, and 2, respectively. We have further extended the techniques and results developed for this problem to other min‐max vehicle routing problems.© 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

A balancing problem for mixed model assembly lines with a paced moving conveyor

We state a balancing problem for mixed model assembly lines with a paced moving conveyor as: Given the daily assembling sequence of the models, the tasks of each model, the precedence relations among the tasks, and the operations parameters of the assembly line, assign the tasks of the models to the workstations so as to minimize the total overload time. Several characteristics of the problem are investigated. A line‐balancing heuristic is proposed based on a lower bound of the total overload time. A practical procedure is provided for estimating the deviation of any given line‐balance solution from the theoretical optimum. Numerical examples are given to illustrate the methodology. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

Optimal resource allocation and redistribution strategy in military conflicts with Lanchester square law attrition

We address the problem of optimal decision‐making in conflicts based on Lanchester square law attrition model where a defending force needs to be partitioned optimally, and allocated to two different attacking forces of differing strengths and capabilities. We consider a resource allocation scheme called the Time Zero Allocation with Redistribution (TZAR) strategy, where allocation is followed by redistribution of defending forces, on the occurrence of certain decisive events. Unlike previous work on Lanchester attrition model based tactical decision‐making, which propose time sequential tactics through an optimal control approach, the present article focuses on obtaining simpler resource allocation tactics based on a static optimization framework, and demonstrates that the results obtained are similar to those obtained by the more complex dynamic optimal control solution. Complete solution for this strategy is obtained for optimal partitioning of resources of the defending forces. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

Rolling‐horizon replenishment: Policies and performance analysis

We consider a rolling‐horizon (RH) replenishment modeling framework under which a buyer can update demand information and inventory status, modify order quantities committed previously, place an advanced order for a new period at the end of the RH, and move along in time seamlessly. We show that the optimal order policy for the two‐period RH problem is a dual‐threshold type for updating period(s) plus a base‐stock type for the advanced order. We provide analytical formulas and algorithms to compute the optimal thresholds and the optimal base‐stock level exactly. With our analytical results and numerical procedures, we demonstrate the significant value of RH replenishment in matching supplies to demands more closely. We also show that with RH updating (flexibility), the value of additional demand information beyond the RH diminishes quickly. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Analysis of a new vehicle scheduling and location problem

We consider a container terminal discharging containers from a ship and locating them in the terminal yard. Each container has a number of potential locations in the yard where it can be stored. Containers are moved from the ship to the yard using a fleet of vehicles, each of which can carry one container at a time. The problem is to assign each container to a yard location and dispatch vehicles to the containers so as to minimize the time it takes to download all the containers from the ship. We show that the problem is NP‐hard and develop a heuristic algorithm based on formulating the problem as an assignment problem. The effectiveness of the heuristic is analyzed from both worst‐case and computational points of view. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 363–385, 2001     

Scheduling with centralized and decentralized batching policies in concurrent open shops

This article considers batch scheduling with centralized and decentralized decisions. The context of our study is concurrent open shop scheduling where the jobs are to be processed on a set of independent dedicated machines, which process designated operations of the jobs in batches. The batching policy across the machines can be centralized or decentralized. We study such scheduling problems with the objectives of minimizing the maximum lateness, weighted number of tardy jobs, and total weighted completion time, when the job sequence is determined in advance. We present polynomial time dynamic programming algorithms for some cases of these problems and pseudo‐polynomial time algorithms for some problems that are NP‐hard in the ordinary sense. © 2010 Wiley Periodicals, Inc. Naval Research Logistics 58: 17–27, 2011     

Capacitated selection problem

Optimizing the selection of resources to accomplish a set of tasks involves evaluating the tradeoffs between the cost of maintaining the resources necessary to accomplish the tasks and the penalty cost associated with unfinished tasks. We consider the case where resources are categorized into types, and limits (capacity) are imposed on the number of each type that can be selected. The objective is to minimize the sum of penalty costs and resource costs. This problem has several practical applications including production planning, new product design, menu selection and inventory management. We develop a branch‐and‐bound algorithm to find exact solutions to the problem. To generate bounds, we utilize a dual ascent procedure which exploits the special structure of the problem. Information from the dual and recovered primal solutions are used to select branching variables. We generate strong valid inequalities and use them to fix other variables at each branching step. Results of tests performed on reasonably sized problems are presented. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 19–37, 1999     

Military intelligence and the problem of legitimacy: Opening the model

This brief essay looks at some of the emerging dilemmas facing the Intelligence Community (IC), and suggests a model for action that is based on the growing importance of legitimization now evident in all phases of US military activity abroad. The challenge for the IC is to satisfy the needs of a demanding and highly varied set of consumers while maintaining a clear priority on missions of military concern. When the legitimization priorities of broadly varied mission tasks are disaggregated and linked with the intelligence cycle, we see that total war, limited war, and operations other than war (OOTW) have distinct and incompatible priorities. Rather than try to adapt the existing system to fish‐out‐of‐water applications, and in the process degrade the capabilities of the IC to conduct total warfare support operations effectively, it may be time to envision a new, parallel intelligence agency for the support of limited war and OOTW.     

战场自然环境对军事行动影响

战场自然环境是影响作战的重要因素,文章研究战场自然环境对军事行动影响,详细介绍了战场自然环境综合分析、高寒山地环境对军事行动影响分析、海洋环境对军事行动影响分析等方面研究内容,并在此基础上给出了动态战场自然环境对军事行动影响分析评估框架。     

Resourcing for defense: Solving the roles and missions puzzle

One of the most important issues facing the post‐Cold War U.S. defense establishment concerns the future allocation of combat tasks and responsibilities among different branches of the armed forces. The challenge is to reduce unnecessary redundancy across roles and missions when resources are highly constrained, without compromising military effectiveness. Defining the policy problem as one of resource allocation rather than operational effectiveness, we develop a methodology for allocating roles and missions. Our methodology focuses at the highest level of force aggregation and uses a mathematical programming model to produce cross‐service cross‐mission trade‐offs that will yield the best total force combat and non‐combat potential within resource consumption constraints.     

Decomposing inventory routing problems with approximate value functions

We present a time decomposition for inventory routing problems. The methodology is based on valuing inventory with a concave piecewise linear function and then combining solutions to single‐period subproblems using dynamic programming techniques. Computational experiments show that the resulting value function accurately captures the inventory's value, and solving the multiperiod problem as a sequence of single‐period subproblems drastically decreases computational time without sacrificing solution quality. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

军事云环境下基于动态博弈的资源调度方法

针对军事云环境下联合指挥资源调度优化问题,综合考虑了多部队任务需求,多目标优化,多部队资源竞争等约束条件,运用动态博弈理论及方法,建立并提出了一种基于完全信息扩展博弈的资源调度模型及方法,提高了资源调度效率,兼顾了多部队利益,增加了联合作战效益。最后通过实验验证了其有效性及准确性。     

低慢小无人机对军事区域的安全威胁及其应对方法

低慢小无人机具有小型化、红外与雷达暴露征候小、飞行高度低、飞行轨迹不定以及购买使用几乎无门槛等特征,给当前全球军事区域和军事行动安全带来了新的挑战。本文首先分析了世界主要国家对低慢小无人机的界定、国内外管控情况和相关威胁事件;然后,从低慢小无人机的侦察袭击能力、军事区域现有安防措施和低慢小无人机对军事区域进行侦察的相关案例入手,讨论了低慢小无人机对军事区域的侦察袭击的威胁;最后从政策制度、营区部署与隐蔽伪装以及反制措施配置三方面对军事区域防低慢小无人机侦察袭击的手段与措施进行了分析和研究,重点就机动性、经济性、技术难度、可操作性、反应速度、打击效果、能否对抗集群目标以及适用场合等方面对当前各种反无人机的干扰、驱离、毁坏措施进行了对比。     

面向作战任务的作战系统冲突检测与消解研究

以作战任务为中心,动态集成作战系统是当前军事领域研究的新课题,从多个作战任务的时间冲突和作战系统状态能力有限性出发,研究作战系统在执行作战任务过程中存在冲突的问题,给出冲突规则的形式化描述,提出了冲突检测与消解的算法,最后通过实例对算法进行了验证。     

Helping hands: civil–military cooperation and Italy's military operation abroad

In the Post-Bipolar Era the growing complexity of the military operations requires a new approach for the resolution of international crises. Since the end of the Cold War, peace support operations (PSO) have become the mainstay and principal occupation of most Western armies. At the same time, Italy has been one of the most important actors in such an area. The article focuses on the cooperation between military and civil components (a process called CIMIC) as a key variable in the Italian PSOs. We will analyse in detail the main lessons learned from past military interventions as well as the general context in which new tendencies are taking place. The maintaining of a minimum security frame becomes essential to fulfil activities ‘collateral’ to the mission: reconstructing services and infrastructure, food distribution, water and medication, law and order, de-mining, training of local forces, and supporting local institutions. These are the main tasks to obtain thrust and support from the population.     

An efficient metaheuristic for integrated scheduling and staffing IT projects based on a generalized minimum cost flow network

Scheduling IT projects and assigning the project work to human resources are an important and common tasks in almost any IT service company. It is particularly complex because human resources usually have multiple skills. Up to now only little work has considered IT‐specific properties of the project structure and human resources. In this article, we present an optimization model that simultaneously schedules the activities of multiple IT projects with serial network structures and assigns the project work to multiskilled internal and external human resources with different efficiencies. The goal is to minimize costs. We introduce a metaheuristic that decomposes the problem into a binary scheduling problem and a continuous staffing problem where the latter is solved efficiently by exploiting its underlying network structure. For comparison, we solve the mixed–binary linear program with a state–of–the–art commercial solver. The impacts of problem parameters on computation time and solution gaps between the metaheuristic and the solver are assessed in an experimental study. Our results show that the metaheuristic provides very favorable results in considerable less time than the solver for midsize problems. For larger problems, it shows a similar performance while the solver fails to return feasible solutions. © 2012 Wiley Periodicals, Inc. Naval Research Logistics 59: 111–127, 2012     

基于多栅格的基建营房保障信息耦合研究

合理利用军地资源实施一体化保障是现代战争或非战争军事行动基建营房保障的重要内容，然而，包含大量此类信息的商用网络、行业网络和平时基建营房业务管理网络的信息如何能被有效利用却是一个令人头疼的问题。依托军事信息栅格和地方多个行业信息网络，研究、设计缓冲数据库和数据订制服务软件，安全可靠地将分布在多个信息栅格中的基建营房保障所需信息耦合到军事后勤信息网络中，为快速、科学制定基建营房保障计划和实施战时基建营房一体化保障提供强有力的信息支持。