Average-case analysis of the bin-packing problem with general cost structures

We consider a version of the famous bin-packing problem where the cost of a bin is a concave function of the number of items in the bin. We analyze the problem from an average-case point of view and develop techniques to determine the asymptotic optimal solution value for a variety of functions. We also describe heuristic techniques that are asymptotically optimal. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 673–686, 1997     

Compromise allocation in multivariate stratified sampling: An integer solution

The problem of determining the sample sizes in various strata when several characteristics are under study is formulated as a nonlinear multistage decision problem. Dynamic programming is used to obtain an integer solution to the problem. © 1997 John Wiley & Sons, Inc.     

A generalized Johnson's rule for stochastic assembly systems

Johnson's rule gives the optimal order to schedule a set of jobs through a two-machine flow shop with deterministic processing times. We extend Johnson's rule to fork-join systems with random processing times. Most of the system may be an arbitrary network. We give conditions under which Johnson's rule is optimal in the stochastic sense, in the increasing convex sense, and in expected value. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 211–220, 1997     

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.     

Attrition modeling in the presence of decoys: An operations-other-than-war motivation

Under various operational conditions, in particular in operations other than war (OOTW) or peacekeeping, an intervening force, here Blue, must occasionally engage in attrition warfare with an opposing force, here Red, that is intermingled with noncombatants. Desirably, Red armed actives are targeted, and not the unarmed noncombatants. This article describes some simple Lanchesterian attrition models that reflect a certain capacity of Blue to discriminate noncombatants from armed and active Red opponents. An explicit extension of the Lanchester square law results: Blue's abstinence concerning the indiscriminate shooting of civilians mixed with Red's is essentially reflected in a lower Blue rate of fire and less advantageous exchange rate. The model applies to other situations involving decoys, and reflects the value of a discrimination capability. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44 : 507–514, 1997     

Robustness of the normal approximation of lead-time demand in a distribution setting

Previous studies criticize the general use of the normal approximation of lead-time demand on the grounds that it can lead to serious errors in safety stock. We reexamine this issue for the distribution of fast-moving finished goods. We first determine the optimal reorder points and quantities by using the classical normal-approximation method and a theoretically correct procedure. We then evaluate the misspecification error of the normal approximation solution with respect to safety stock, logistics-system costs, total costs (logistics costs, including acquisition costs), and fill rates. The results provide evidence that the normal approximation is robust with respect to both cost and service for seven major industry groups. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 165–186, 1997     

A dynamic model for component testing

We consider the component testing problem of a system where the main feature is that the component failure rates are not constant parameters, but they change in a dynamic fashion with respect to time. More precisely, each component has a piecewise-constant failure-rate function such that the lifetime distribution is exponential with a constant rate over local intervals of time within the overall mission time. There are several such intervals, and the rates change dynamically from one interval to another. We note that these lifetime distributions can also be used in a more general setting to approximate arbitrary lifetime distributions. The optimal component testing problem is formulated as a semi-infinite linear program. We present an algorithmic procedure to compute optimal test times based on the column-generation technique and illustrate it with a numerical example. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 187–197, 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     

Markov decision processes with restricted observations: Finite horizon case

In this article we consider a Markov decision process subject to the constraints that result from some observability restrictions. We assume that the state of the Markov process under consideration is unobservable. The states are grouped so that the group that a state belongs to is observable. So, we want to find an optimal decision rule depending on the observable groups instead of the states. This means that the same decision applies to all the states in the same group. We prove that a deterministic optimal policy exists for the finite horizon. An algorithm is developed to compute policies minimizing the total expected discounted cost over a finite horizon. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44 : 439–456, 1997     

Polynomial algorithms for center location on spheres

When locating facilities over the earth or in space, a planar location model is no longer valid and we must use a spherical surface. In this article, we consider the one-and two-center problems on a sphere that contains n demand points. The problem is to locate facilities to minimize the maximum distance from any demand point to the closest facility. We present an O(n) algorithm for the one-center problem when a hemisphere contains all demand points and also give an O(n) algorithm for determining whether or not the hemisphere property holds. We present an O(n³ log n) algorithm for the two-center problem for arbitrarily located demand points. Finally, we show that for general p, the p center on a sphere problem is NP-hard. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 341–352, 1997     

Acceptance sampling,imperfect production,and the optimality of zero defects

Acceptance sampling is often used to monitor the quality of raw materials and components when product testing is destructive, time-consuming, or expensive. In this paper we consider the effect of a buyer-imposed acceptance sampling policy on the optimal batch size and optimal quality level delivered by an expected cost minimizing supplier. We define quality as the supplier's process capability, i.e., the probability that a unit conforms to all product specifications, and we assume that unit cost is an increasing function of the quality level. We also assume that the supplier faces a known and constant “pass-through” cost, i.e., a fixed cost per defective unit passed on to the buyer. We show that the acceptance sampling plan has a significant impact on the supplier's optimal quality level, and we derive the conditions under which zero defects (100% conformance) is the policy that minimizes the supplier's expected annual cost. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 515–530, 1997     

Algorithms for computing waiting time distributions under different queue disciplines for the D-BMAP/PH/1

A queueing system characterized by the discrete batch Markovian arrival process (D-BMAP) and a probability of phase type distribution for the service time is one that arises frequently in the area of telecommunications. Under this arrival process and service time distribution we derive the waiting time distribution for three queue disciplines: first in first out (FIFO), last in first out (LIFO), and service in random order (SIRO). We also outline efficient algorithmic procedures for computing the waiting time distributions under each discipline. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 559–576, 1997     

Towards finding global representations of the efficient set in multiple objective mathematical programming

We propose and justify the proposition that finding truly global representations of the efficient sets of multiple objective mathematical programs is a worthy goal. We summarize the essential elements of a general global shooting procedure that seeks such representations. This procedure illustrates the potential benefits to be gained from procedures for globally representing efficient sets in multiple objective mathematical programming. © 1997 John Wiley & Sons, Inc.     

Optimal nonmyopic gambling strategy for the generalized Kelly criterion

We consider the optimal wagers to be made by a gambler who starts with a given initial wealth. The gambler faces a sequence of two-outcome games, i.e., “win” vs. “lose,” and wishes to maximize the expected value of his terminal utility. It has been shown by Kelly, Bellman, and others that if the terminal utility is of the form log x, where x is the terminal wealth, then the optimal policy is myopic, i.e., the optimal wager is always to bet a constant fraction of the wealth provided that the probability of winning exceeds the probability of losing. In this paper we provide a critique of the simple logarithmic assumption for the utility of terminal wealth and solve the problem with a more general utility function. We show that in the general case, the optimal policy is not myopic, and we provide analytic expressions for optimal wager decisions in terms of the problem parameters. We also provide conditions under which the optimal policy reduces to the simple myopic case. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 639–654, 1997     

Routing in packet-switched communication networks with different criticality classes of communicating node pairs

This paper addresses the routing problem with reliability requirements in packet-switched communication networks. In this problem, two classes of communicating node pairs are considered: less critical and highly critical node pairs. We develop a model which identifies a primary route for each less critical node pair and both a primary and a secondary (back up) route for each highly critical node pair. The objective is to minimize the average delay encountered by messages. A solution procedure based on a relaxation of the problem is presented. Computational results over a wide range of problem structures show that the procedure is very effective. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44 : 485–505, 1997     

A dynamic-programming approach to continuous-review obsolescent inventory problems

Inventory models of modern production and service operations should take into consideration possible exogenous failures or the abrupt decline of demand resulting from obsolescence. This article analyzes continuous-review versions of the classical obsolescence problem in inventory theory. We assume a deterministic demand model and general continuous random times to obsolescence (“failure”). Using continuous dynamic programming, we investigate structural properties of the problem and propose explicit and workable solution techniques. These techniques apply to two fairly wide (and sometimes overlapping) classes of failure distributions: those which are increasing in failure rate and those which have finite support. Consequently, several specific failure processes in continuous time are given exact solutions. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 757–774, 1997     

The military recruiting productivity slowdown: The roles of resources,opportunity cost and the tastes of youth*

After a decade of successful recruiting, the US military began experiencing recruiting difficulties in the 1990s. Cyclical factors as well as trend factors may have played a role. This paper uses monthly data by state over the period 1989-1997 to estimate models of enlistment and evaluate the various explanations for the recruiting slowdown. Estimates of the impact of economic variables - relative military pay and unemployment - and recruiting resource variables - recruiters and advertising - are similar to those in previous studies. Two trend factors, rising college attendance and declining adult veteran population (influencers), are found to be important factors explaining the decline in enlistment.     

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.     

A Markovian model for process setup and improvement

We examine the setup and improvement policies for a production process with multiple performance states. Assume that the production process deteriorates randomly over time, following a Markovian process with known transition probabilities. In order to reduce the production cost incurred because of process deterioration, the process is inspected at the end of each period. Then one of three actions may be taken: do nothing, perform routine process setup, or perform routine setup and process improvement. The routine setup operation returns the process to its best performance state, whereas the process improvement action may reduce future production and setup costs and improve the process-state transition probabilities. A discounted Markovian model is formulated to find the strategy that minimizes the total cost of operating the production process. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 383–400, 1997     

Multiple-facility loading under capacity-based economies of scope

Multiple-facility loading (MFL) involves the allocation of products among a set of finite-capacity facilities. Applications of MFL arise naturally in a variety of production scheduling environments. MFL models typically assume that capacity is consumed as a linear function of products assigned to a facility. Product similarities and differences, however, result in capacity-based economies or diseconomies of scope, and thus the effective capacity of the facility is often a (nonlinear) function of the set of tasks assigned to the facility. This article addresses the multiple-facility loading problem under capacity-based economies (and diseconomies) of scope (MFLS). We formulate MFLS as a nonlinear 0–1 mixed-integer programming problem, and we discuss some useful properties. MFLS generalizes many well-known combinatorial optimization problems, such as the capacitated facility location problem and the generalized assignment problem. We also define a tabu-search heuristic and a branch-and-bound algorithm for MFLS. The tabu-search heuristic alternates between two search phases, a regional search and a diversification search, and offers a novel approach to solution diversification. We also report computational experience with the procedures. In addition to demonstrating MFLS problem tractability, the computational results indicate that the heuristic is an effective tool for obtaining high-quality solutions to MFLS. © 1997 John Wiley & Sons, Inc. Naval Research Logistics 44: 229–256, 1997