Scheduling to minimize the total compression and late costs

We consider a single-machine scheduling model in which the job processing times are controllable variables with linear costs. The objective is to minimize the sum of the cost incurred in compressing job processing times and the cost associated with the number of late jobs. The problem is shown to be NP-hard even when the due dates of all jobs are identical. We present a dynamic programming solution algorithm and a fully polynomial approximation scheme for the problem. Several efficient heuristics are proposed for solving the problem. Computational experiments demonstrate that the heuristics are capable of producing near-optimal solutions quickly. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 67–82, 1998     

Note: Optimal allocation of resources to nodes of series systems with respect to failure-rate ordering

Allocation of spare components in a system in order to optimize the lifetime of the system with respect to a suitable criterion is of considerable interest in reliability, engineering, industry, and defense. We consider the problem of allocation of K active spares to a series system of independent and identical components in order to optimize the failure-rate function of the system. © 1997 John Wiley & Sons, Inc.     

Computational study of the multiechelon production planning problem

In this article we try to identify appropriate solution procedures for different types of multiechelon production planning problems. We conduct an extensive computational study on uncapacitated multiechelon production planning problems with serial and assembly types of bill-of-material structures. Problems are formulated as both single-source fixed charge network problems and as multicommodity flow problems with fixed charges. Solution procedures considered are branch and cut, Lagrangean relaxation (for the network formulation), and branch and bound (for the multicommodity formulation). Three hundred problems with various problem structures are tested. Our conclusions suggest the best approach for each type of problem structure. © 1997 John Wiley & Sons, Inc.     

Analysis of aircraft sortie generation with the use of a fork-join queueing network model

This article presents an approximate analytical method for evaluating an aircraft sortie generation process. The process is modeled as a closed network of multiserver queues and fork-join nodes that allow concurrent service activities. The model uses a variation of mean value analysis (MVA) to capture the effect of mean service times, resource levels, and network topology on performance measures including resource utilizations and the overall sortie generation rate. The quality of the analytical approximation is demonstrated through comparison with simulation results. © 1997 John Wiley & Sons, Inc.

1 This article is a US Government work and, as such, is in the public domain in the United States of America.

Naval Research Logistics 44: 153–164, 1997     

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     

Cyclical schedules for the joint replenishment problem with dynamic demands

The Joint Replenishment Problem (JRP) involves production planning for a family of items. The items have a coordinated cost structure whereby a major setup cost is incurred whenever any item in the family is produced, and an item-specific minor setup cost is incurred whenever that item is produced. This paper investigates the performance of two types of cyclical production schedules for the JRP with dynamic demands over a finite planning horizon. The cyclical schedules considered are: (1) general cyclical schedules—schedules where the number of periods between successive production runs for any item is constant over the planning horizon—and (2) power-of-two schedules—a subset of cyclical schedules for which the number of periods between successive setups must be a power of 2. The paper evaluates the additional cost incurred by requiring schedules to be cyclical, and identifies problem characteristics that have a significant effect on this additional cost. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 577–589, 1997.     

System comparison procedures for automatic target recognition systems

Estimating the performance of an automatic target recognition (ATR) system in terms of its probability of successfully identifying a target involves extensive image collection and processing, which can be very time‐consuming and expensive. Therefore, we investigate the Wald sequential test for the difference in two proportions as a sample size‐reducing alternative to ranking and selection procedures and confidence intervals. An analysis of the test parameters leads to a practical methodology for implementing the Wald test for fairly comparing two systems, based on specific experimental goals. The test is also extended with the modified, sequentially rejective Bonferroni procedure for the multiple pairwise comparison of more than two systems. Two sampling schemes for different experimental goals are also discussed. The test methodology is applied to actual data to compare different configurations of a specific ATR system, with the results demonstrating that the modified Wald sequential procedure is a useful alternative to comparing proportions with confidence intervals, particularly when data are expensive. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 357–371, 1999     

A heuristic approach to bicriteria scheduling

We consider the problem of sequencing jobs on a single machine while minimizing a nondecreasing function of two criteria. We develop a heuristic procedure that quickly finds a good solution for bicriteria scheduling. The procedure is based on using several arcs in the criterion space that are representative of the possible locations of nondominated solutions. By sampling a small number of points on these arcs, a promising point is identified in the criterion space for each arc. An efficient sequence in the neighborhood of each of the promising points is found and the best of these efficient sequences is selected as the heuristic solution. We implement the procedure for two different bicriteria scheduling problems: (i) minimizing total flowtime and maximum tardiness and (ii) minimizing total flowtime and maximum earliness. The computational experience on a wide variety of problem instances show that the heuristic approach is very robust and yields good solutions. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 777–789, 1999     

The residual life of the renewal process: A simple algorithm

We develop a simple algorithm, which does not require convolutions, for computing the distribution of the residual life when the renewal process is discrete. We also analyze the algorithm for the particular case of lattice distributions, and we show how it can apply to an inventory problem. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 435–443, 1999     

System availability in a gamma alternating renewal process

We measure the effectiveness of a repairable system by the proportion of time the system is on, where on-time and off-times are assumed independent and both gamma-distributed. This measure is helpful for system planning and control in the short term, before the steady-state is reached, and its mean value is intermediary between instantaneous and steady-state availabilities. We also present other significant results concerning the Gamma Alternating Renewal Process. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 822–844, 1999