An experimental comparison of solution algorithms for the single-machine tardiness problem

A basic problem in scheduling involves the sequencing of a set of independent tasks at a single facility with the objective of minimizing mean tardiness. Although the problem is relatively simple, the determination of an optimal sequence remains a challenging combinatorial problem. A number of algorithms have been developed for finding solutions, and this paper reports a comparative evaluation of these procedures. Computer programs for five separate algorithms were written and all were run on a data base designed to highlight computational differences. Optimizing algorithms developed by Emmons and by Srinivasan appeared to be particularly efficient in the comparative study.     

Properties of an approximate hazard transform

The calculation of the exact reliability of complex systems is a difficult and tedious task. Consequently simple approximating techniques have great practical value. The hazard transform of a system is an invertible transformation of its reliability function which is convenient and useful in both applied and theoretical reliability work. A simple calculus for finding an approximate hazard transform for systems formed by series and parallel combinations of components is extended so that it can be used for any coherent system. The extended calculus is shown to lead to conservative approximations. A first order version of the extended calculus is also discussed. This method of approximation is even more simple to use, but is not always conservative. Examples of its application indicate that it is capable of giving quite accurate results.     

A computation procedure for the exact solution of location-allocation problems with rectangular distances

A method is presented to locate and allocate p new facilities in relation to n existing facilities. Each of the n existing facilities has a requirement flow which must be supplied by the new facilities. Rectangular distances are assumed to exist between all facilities. The algorithm proceeds in two stages. In the first stage a set of all possible optimal new facility locations is determined by a set reduction algorithm. The resultant problem is shown to be equivalent to finding the p-median of a weighted connected graph. In the second stage the optimal locations and allocations are obtained by using a technique for solving the p-median problem.     

On the treatment of force-level constraints in times-equential combat problems

The treatment of force-level constraints in time-sequential combat optimization problems is illustrated by further studying the fire-programming problem of Isbell and Marlow. By using the theory of state variable inequality constraints from modern optimal control theory, sharper results are obtained on necessary conditions of optimality for an optimal fire-distribution policy (in several cases justifying conjectures made in previous analysis). This leads to simplification of the determination of the domains of controllability for extremals leading to the various terminal states of combat. (Additionally, some new results for the determination of boundary conditions for the adjoint variables in optimal control problems with state variable inequality constraints have arisen from this work.) Some further extensions of previous analysis of the fire-programming problem are also given. These clarify some key points in the solution synthesis. Some important military principles for target selection and the valuation of combat resources are deduced from the solution. As a result of this work, more general time-sequential combat optimization problems can be handled, and a more systematic solution procedure is developed.     

An explicit general solution in linear fractional programming

A complete analysis and explicit solution is presented for the problem of linear fractional programming with interval programming constraints whose matrix is of full row rank. The analysis proceeds by simple transformation to canonical form, exploitation of the Farkas-Minkowki lemma and the duality relationships which emerge from the Charnes-Cooper linear programming equivalent for general linear fractional programming. The formulations as well as the proofs and the transformations provided by our general linear fractional programming theory are here employed to provide a substantial simplification for this class of cases. The augmentation developing the explicit solution is presented, for clarity, in an algorithmic format.     

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     

Reassessing Military Assistance to the Civil Powers: Are Traditional British Anti-Terrorist Responses Still Effective?

The provision of Military Assistance to the Civil Powers (MACP) encapsulates the traditional approach towards countering terrorism on the British mainland, which emphasises minimum force, proportionality, police primacy and the rule of law, with the military retained as a supporting instrument, being employed only as a measure of last resort. Recent terrorist incidents in major urban centres do, however, question the effectiveness of these established methods. This analysis initially codifies the conceptual issues that underscore the tensions between civil policing and military anti-terrorist approaches in the UK, and proceeds to evaluate and compare a number of operations that indicate the nature of the challenges facing the MACP apparatus. In particular, potential shortcomings in the MACP provisions are identified in the form of threat perception and deployment and enforcement gaps. The assessment finds that there are facets of MACP that are of enduring relevance in the current era, yet a continuing need persists to reconcile police and military imperatives toward serious civil disorder contingencies and conditions of emergency.     

The Hungarian method for the assignment problem

This paper has been presented with the Best Paper Award. It will appear in print in Volume 52, No. 1, February 2005.