Optimal sequential replenishment of ships during combat

A carrier battle group is operating in an area where it is subject to attack by enemy aircraft. It is anticipated that air raids will occur in large waves. The uncertain time between raids is available for the replenishment of supplies. We consider the problem of how best to schedule ammunition replenishment during this period. The theory of Gittins indices provides the technical background to the development of a range of models which yield a hierarchy of index-based heuristics for replenishment. One such heuristic is assessed computationally in a more realistic scenario than is explicitly allowed for by the models.     

Heterogeneous multitrunking queueing systems with thresholds

Queueing systems with multiple servers are commonly used to model telecommunications systems. But, in general, the service rate of each of the servers is not the same. This fact is indeed true in a communication network where one path (server) may be a terrestrial link and the other (server) a satellite link with its inherent propagation delay. In this article we consider a two-server system where arriving customers are first placed in the queue for the faster server until that queue size reaches a certain threshold, whereupon they are diverted to the slower server. Additional arriving customers are assigned to the slower server until the faster server's queue drops to another lower threshold, at which point arrivals are reassigned to the faster server. We develop an exact mathematical model of the steady-state behavior of each queueing system and a simple analytic approximation.     

An approach to modeling electric utility capacity expansion planning

This article describes an algorithm for solving the static electric utility capacity expansion problem. The advantages of this algorithm are twofold. First, it is simpler and yet more efficient than previous algorithms for the same problem. Second, by making simplifying but realistic assumptions on plant sizes it is possible to use this algorithm for the case where one does not allow fractional plant additions. While the model has n variables, it has a clear two-dimensional geometric representation for understanding its properties, developing an algorithm, and interpreting the optimal solution. This algorithm has been implemented in the Intermediate Future Forecasting (IFFS) capacity expansion model at the Department of Energy.     

A replacement model with overhauls and repairs

This article generalizes the classical periodical replacement model with minimal repair by considering the effect of the overhaul, which is assumed to be able to rejuvenate the system. The generalization is based on the notion of the virtual age of a system introduced by Kijima, Morimura, and Suzuki [“Periodical Replacement Problem without Assuming Minimal Repair,” European Journal of Operational Research, 37 , 194–203 (1988)]. © 1995 John Wiley & Sons, Inc.     

Makespan minimization for m parallel identical processors

We introduce an algorithm, called TMO (Two-Machine Optimal Scheduling) which minimizes the makespan for two identical processors. TMO employs lexicographic search in conjunction with the longest-processing time sequence to derive an optimal schedule. For the m identical parallel processors problem, we propose an improvement algorithm, which improves the seed solution obtained by any existing heuristic. The improvement algorithm, called Extended TMO, breaks the original m-machine problem into a set of two-machine problems and solves them repeatedly by the TMO. A simulation study is performed to evaluate the effectiveness of the proposed algorithms by comparing it against three existing heuristics: LPT (Graham, [11]), MULTIFIT (Coffman, Garey, and Johnson, [6]), and RMG (Lee and Massey, [17]). The simulation results show that: for the two processors case, the TMO performs significantly better than LPT, MULTIFIT, and RMG, and it generally takes considerably less CPU time than MULTIFIT and RMG. For the general parallel processors case, the Extended TMO algorithm is shown to be capable of greatly improving any seed solution. © 1995 John Wiley & Sons, Inc.     

Use of a classifier in a knowledge-based simulation optimization system

This article defines and develops a simulation optimization system based upon response surface classification and the integration of multiple search strategies. Response surfaces are classified according to characteristics that indicate which search technique will be most successful. Typical surface characteristics include statistical measures and topological features, while search techniques encompass response surface methodology, simulated annealing, random search, etc. The classify-then-search process flow and a knowledge-based architecture are developed and then demonstrated with a detailed computer example. The system is useful not only as an approach to optimizing simulations, but also as a means for integrating search techniques and thereby providing the user with the most promising path toward an optimal solution. © 1995 John Wiley & Sons, Inc.     

Note: A local-search heuristic for large set-covering problems

In this note we describe a local-search heuristic (LSH) for large non-unicost set-covering problems (SCPs). The new heuristic is based on the simulated annealing algorithm and uses an improvement routine designed to provide low-cost solutions within a reasonable amount of CPU time. The solution costs associated with the LSH compared very favorably to the best previously published solution costs for 20 large SCPs taken from the literature. In particular, the LSH yielded new benchmark solutions for 17 of the 20 test problems. We also report that, for SCPs where column cost is correlated with column coverage, the new heuristic provides solution costs competitive with previously published results for comparable problems. © 1995 John Wiley & Sons, Inc.     

Optimal force mix in heterogeneous combat

This article presents models for determining the optimum number of Red weapons required to win a heterogeneous combat in which m(m> 1) types of Red weapons face a single type of Blue weapon under a newly defined termination policy. Red aims at either minimizing the total cost or maximizing the aggregated remaining force strength. Kuhn-Tucker and simulated annealing techniques are used for obtaining the optimal solution. The methodology is illustrated by analysing heterogeneous combat to determine (i) the feasibility of introducing new types of weapons and (ii) the number of weapons required to win if a specific type of weapon, say infantry, dominates. © 1995 John Wiley & Sons, Inc.     

A simulated annealing approach to the cyclic staff-scheduling problem

This article presents the application of a simulated annealing heuristic to an NP-complete cyclic staff-scheduling problem. The new heuristic is compared to branch-and-bound integer programming algorithms, as well as construction and linear programming-based heuristics. It is designed for use in a continuously operating scheduling environment with the objective of minimizing the number of employees necessary to satisfy forecast demand. The results indicate that the simulated annealing-based method tends to dominate the branch-and-bound algorithms and the other heuristics in terms of solution quality. Moreover, the annealing algorithm exhibited rapid convergence to a low-cost solution. The simulated annealing heuristic is executed in a single program and does not require mathematical programming software. © 1993 John Wiley & Sons, Inc.     

Maintenance of a device with age-dependent exponential failures

We consider a device that deteriorates over time according to a Markov process so that the failure rate at each state is constant. The reliability of the device is characterized by a Markov renewal equation, and an IFRA (increasing failure rate on average) property of the lifetime is obtained. The optimal replacement and repair problems are analyzed under various cost structures. Furthermore, intuitive and counterintuitive characterizations of the optimal policies and results on some interesting special problems are presented. © 1992 John Wiley & Sons, Inc.