Minimum-cost mixtures of area and point defenses assuming simultaneous attack

It is desired to select numbers of area and point interceptors that minimize the cost of such defensive missiles under the condition that the maximum total expected damage produced by an unknown number of attacking missiles A be bounded above by a given function of A. Area coverages may overlap. The attacker is assumed to know the numbers of area and point interceptors and to launch a simultaneous attack (of arbitrary size A) against all targets, which is optimal against the given defenses. The defender is assumed to observe the attack and then allocate his area and point interceptors against attacking missiles so as to minimize the total expected damage. Upper and lower bounds on the minimal cost are obtained by solving integer programming problems.     

Scheduling target illuminators in naval battle-group anti-air warfare

We schedule a set of illuminators (homing devices) to strike a set of targets using surface-to-air missiles in a naval battle. The task is viewed as a production floor shop scheduling problem of minimizing the total weighted flow time, subject to time-window job availability and machine downtime side constraints. A simple algorithm based on solving assignment problems is developed for the case when all the job processing times are equal and the data are all integer. For the general case of scheduling jobs with unequal processing times, we develop two alternate formulations and analyze their relative strengths by comparing their respective linear programming relaxations. We select the better formulation in this comparison and exploit its special structures to develop several effective heuristic algorithms that provide good-quality solutions in real time; this is an essential element for use by the Navy. © 1995 John Wiley & Sons, Inc.     

弹着时间可控的机动目标多弹协同制导律

针对机动目标的多导弹齐射攻击,运用最优控制和卡尔曼滤波理论探索机动目标下弹着时间可控制导律问题。设计了一种最优弹着时间可控的制导律,它由指定弹着时间和预计弹着时间的误差作为反馈信号与传统比例制导律结合推导得出,称之为弹着时间可控制导律（Impact-time-control Guidance Law,简称ITCG）,同时利用卡尔曼滤波估计了目标加速度。通过对作战模型情况的仿真,可以看出这种新型的制导律应用于引导多发导弹以指定时间同时攻击目标时的有效性和可行性。     

Single machine just‐in‐time scheduling problems with two competing agents

In scheduling problems with two competing agents, each one of the agents has his own set of jobs to be processed and his own objective function, and both share a common processor. In the single‐machine problem studied in this article, the goal is to find a joint schedule that minimizes the total deviation of the job completion times of the first agent from a common due‐date, subject to an upper bound on the maximum deviation of job completion times of the second agent. The problem is shown to be NP‐hard even for a nonrestrictive due‐date, and a pseudopolynomial dynamic program is introduced and tested numerically. For the case of a restrictive due‐date (a sufficiently small due‐date that may restrict the number of early jobs), a faster pseudopolynomial dynamic program is presented. We also study the multiagent case, which is proved to be strongly NP‐hard. A simple heuristic for this case is introduced, which is tested numerically against a lower bound, obtained by extending the dynamic programming algorithm. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 61: 1–16, 2014     

A dual criteria sequencing problem with earliness and tardiness penalties

We consider the problem of sequencing n jobs on a single machine, with each job having a processing time and a common due date. The common due date is assumed to be so large that all jobs can complete by the due date. It is known that there is an O(n log n)‐time algorithm for finding a schedule with minimum total earliness and tardiness. In this article, we consider finding a schedule with dual criteria. The primary goal is to minimize the total earliness and tardiness. The secondary goals are to minimize: (1) the maximum earliness and tardiness; (2) the sum of the maximum of the squares of earliness and tardiness; (3) the sum of the squares of earliness and tardiness. For the first two criteria, we show that the problems are NP‐hard and we give a fully polynomial time approximation scheme for both of them. For the last two criteria, we show that the ratio of the worst schedule versus the best schedule is no more than . © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 422–431, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10020     

Sequencing with setup time and order tardiness trade-offs

We consider the problem of scheduling customer orders on a single facility where each order consists of several jobs that can be clustered into several groups. When a facility is changed over to another group, a setup time associated with the new group is required. Two particular problems are considered in this context. One is to consider the total setup time and the number of tardy orders jointly. The other is to consider the total setup time and the maximum tardiness jointly. The total setup time in both problems represents a measure of internal efficiency, whereas the number of tardy orders and the maximum tardiness represent a measure of external efficiency. In any shop, the decision maker must consider the tradeoffs between large setup costs associated with a more frequent changeover schedule versus the cost of tardy orders that might be induced by a less-frequent changeover schedule. In this article branch-and-bound algorithms are proposed to identify the set of nondominated schedules for the two bicriteria problems. © 1996 John Wiley & Sons, Inc.     

Single machine scheduling with a restricted rate‐modifying activity

In this paper we consider the problem of scheduling a set of jobs on a single machine on which a rate‐modifying activity may be performed. The rate‐modifying activity is an activity that changes the production rate of the machine. So the processing time of a job is a variable, which depends on whether it is scheduled before or after the rate‐modifying activity. We assume that the rate‐modifying activity can take place only at certain predetermined time points, which is a constrained case of a similar problem discussed in the literature. The decisions under consideration are whether and when to schedule the rate‐modifying activity, and how to sequence the jobs in order to minimize some objectives. We study the problems of minimizing makespan and total completion time. We first analyze the computational complexity of both problems for most of the possible versions. The analysis shows that the problems are NP‐hard even for some special cases. Furthermore, for the NP‐hard cases of the makespan problem, we present a pseudo‐polynomial time optimal algorithm and a fully polynomial time approximation scheme. For the total completion time problem, we provide a pseudo‐polynomial time optimal algorithm for the case with agreeable modifying rates. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

超视距反舰导弹射击方式优化选择

射击方式的选择是反舰导弹作战使用的重要内容。在超视距作战需求的牵引下,传统视距反舰导弹的射击方式受到了巨大挑战。为优化选择超视距反舰导弹的射击方式,建立了两种常用射击方式的导弹捕捉概率模型和目标机动模型,给出一种典型条件不同目标机动航向的导弹捕捉概率,结果表明采用有前置量方式射击无法有效提高超视距导弹的捕捉概率,甚至在某些典型条件下还低于无前置量方式射击的捕捉概率,指出无前置方式是超视距反舰导弹射击的优选方式。     

Capacity improvement,penalties, and the fixed charge transportation problem

Capacity improvement and conditional penalties are two computational aides for fathoming subproblems in a branch‐and‐bound procedure. In this paper, we apply these techniques to the fixed charge transportation problem (FCTP) and show how relaxations of the FCTP subproblems can be posed as concave minimization problems (rather than LP relaxations). Using the concave relaxations, we propose a new conditional penalty and three new types of capacity improvement techniques for the FCTP. Based on computational experiments using a standard set of FCTP test problems, the new capacity improvement and penalty techniques are responsible for a three‐fold reduction in the CPU time for the branch‐and‐bound algorithm and nearly a tenfold reduction in the number of subproblems that need to be evaluated in the branch‐and‐bound enumeration tree. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 341–355, 1999     

Scheduling for parallel dedicated machines with a single server

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule is N P‐hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst‐case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two‐machine flow shop and the open shop problems with a single server are also shown to be N P‐hard in the strong sense. However, we reduce the two‐machine flow shop no‐wait problem with a single server to the Gilmore—Gomory traveling salesman problem and solve it in polynomial time. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 304–328, 2000     

Effective attacks in the salvo combat model: Salvo sizes and quantities of targets

This article considers two related questions of tactics in the context of the salvo model for naval missile combat. For a given set of targets, how many missiles should be fired to produce an effective attack? For a given available salvo size, how many enemy targets should be fired at? In the deterministic version of the model I derive a simple optimality relationship between the number of missiles to fire and the number of targets to engage. In the stochastic model I employ the expected loss inflicted and the probability of enemy elimination as the main performance measures and use these to derive salvo sizes that are in some sense “optimal.” I find that the offensive firepower needed for an effective attack depends not only on a target's total strength but also on the relative balance between its active defensive power and passive staying power. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

The one‐warehouse multiretailer problem with an order‐up‐to level inventory policy

We consider a two‐level system in which a warehouse manages the inventories of multiple retailers. Each retailer employs an order‐up‐to level inventory policy over T periods and faces an external demand which is dynamic and known. A retailer's inventory should be raised to its maximum limit when replenished. The problem is to jointly decide on replenishment times and quantities of warehouse and retailers so as to minimize the total costs in the system. Unlike the case in the single level lot‐sizing problem, we cannot assume that the initial inventory will be zero without loss of generality. We propose a strong mixed integer program formulation for the problem with zero and nonzero initial inventories at the warehouse. The strong formulation for the zero initial inventory case has only T binary variables and represents the convex hull of the feasible region of the problem when there is only one retailer. Computational results with a state‐of‐the art solver reveal that our formulations are very effective in solving large‐size instances to optimality. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010     

Optimal assignment of high multiplicity flight plans to dispatchers

This paper addresses the problem of finding a feasible schedule of n jobs on m parallel machines, where each job has a deadline and some jobs are preassigned to some machine. This problem arises in the daily assignment of workload to a set of flight dispatchers, and it is strongly characterized by the fact that the job lengths may assume one out of k different values, for small k. We prove the problem to be NP‐complete for k = 2 and propose an effective implicit enumeration algorithm which allows efficiently solution a set of real‐life instances. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 359–376, 2000     

Scheduling jobs with piecewise linear decreasing processing times

We study the problems of scheduling a set of nonpreemptive jobs on a single or multiple machines without idle times where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objectives are the minimization of makespan and minimization of total job completion time. The single machine problems are proved to be NP‐hard, and some properties of their optimal solutions are established. A pseudopolynomial time algorithm is constructed for makespan minimization. Several heuristics are derived for both total completion time and makespan minimization. Computational experiments are conducted to evaluate their efficiency. NP‐hardness proofs and polynomial time algorithms are presented for some special cases of the parallel machine problems. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 531–554, 2003     

A hybrid algorithm for the one machine sequencing problem to minimize total tardiness

In a recent paper, Hamilton Emmons has established theorems relating to the order in which pairs of jobs are to be processed in an optimal schedule to minimize the total tardiness of performing n jobs on one machine. Using these theorems, the algorithm of this paper determines the precedence relationships among pairs of jobs (whenever possible) and eliminates the first and the last few jobs in an optimal sequence. The remaining jobs are then ordered by incorporating the precedence relationships in a dynamic programming framework. Propositions are proved which considerably reduce the total computation involved in the dynamic programming phase. Computational results indicate that the solution time goes up less than linearly with the size (n) of the problem. The median solution time for solving 50 job problems was 0.36 second on UNIVAC 1108 computer.     

A network isolation algorithm

A set of edges D called an isolation set, is said to isolate a set of nodes R from an undirected network if every chain between the nodes in R contains at least one edge from the set D. Associated with each edge of the network is a positive cost. The isolation problem is concerned with finding an isolation set such that the sum of its edge costs is a minimum. This paper formulates the problem of determining the minimal cost isolation as a 0–1 integer linear programming problem. An algorithm is presented which applies a branch and bound enumerative scheme to a decomposed linear program whose dual subproblems are minimal cost network flow problems. Computational results are given. The problem is also formulated as a special quadratic assignment problem and an algorithm is presented that finds a local optimal solution. This local solution is used for an initial bound.     

Opportunistic retooling of a flexible machine subject to failure

A set of jobs can be processed without interruption by a flexible machine only if the set of tools required by all jobs can be loaded in the tool magazine. However, in practice the total number of tools required by a job set would exceed the tool magazine capacity. In such situations, the job set has to be carefully partitioned at the start of the production run such that each partition can be processed without interruption. During the production run, if there are unscheduled machine downtimes due to machine failure, this provides an additional opportunity to optimally retool the magazine for a smaller job set consisting of just the unprocessed jobs. In this paper, we study job sequencing rules that allow us to minimize the total expected cost of machine down time due to machine failures and magazine retooling, assuming a dynamic re‐sequencing of the unprocessed jobs after each machine failure. Using these rules, we develop a branch‐and‐bound heuristic that allows us to solve problems of reasonable size. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 79–97, 2001     

弹道导弹基本诸元的快速装订算法研究

应用牛顿迭代法实现了弹道导弹基本诸元的快速装订。推导了根据落点偏差求飞行程序角和发射方位角的牛顿迭代公式，设计了迭代算法，并给出了实际算例。考虑到迭代算法收敛速度与所给的迭代初值有一定的关系，提出了预先准备简易射表采用反插值算法为牛顿迭代法准备初值的方法，经计算表明可以大大减少迭代次数，从而实现标准弹道的快速设计。     

A stochastic optimization model for planning capacity expansion in a service industry under uncertain demand

A stochastic optimization model for capacity expansion for a service industry that incorporates uncertainty in future demand is developed. Based on a weighted set of possible demand scenarios, the model generates a recommended schedule of capacity expressions, and calculates the resulting sales under each scenario. The capacity schedule specifies the size, location, and timing of these expansions that will maximize the company's expected profit. The model includes a budget constraint on available resources. By using Lagrangian relaxation and exploiting the special nested knapsack structure in the sub-problems, an algorithm was developed for its solution. Based on the initial computational results, this algorithm appears to be more efficient than linear programming for this special problem. © 1994 John Wiley & Sons, Inc.     

An engagement model to optimize defense against a multiple attack assuming perfect kill assessment

We present an air-defense engagement model to counter an attack by multiple antiship missiles, assuming perfect kill assessment. In this model, the probability of shooting down all incoming missiles is maximized. A generating function is employed to produce an algorithm which is used to evaluate the outcomes. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 687–697, 1997