Linear search with bounded resources

A point is placed at random on the real line according to some known distribution F, and a search is made for this point, beginning at some starting points s on the line, and moving along the line according to some function x(t). The objective of this article is to maximize the probability of finding the point while traveling at most d units. Characterizations of simple optimal searches are found for arbitrary distributions, for continuous distributions with continuous density everywhere (e.g., normal, Cauchy, triangular), and for continuous distributions with density which is continuous on its support (e.g., exponential, uniform). These optimal searches are also shown to be optimal for maximization of the expected number of points found if the points are placed on the line independently from a known distribution F.     

AN ALGORITHM FOR THE SEGREGATED STORAGE PROBLEM

The segregated storage problem involves the optimal distribution of products among compartments with the restriction that only one product may be stored in each compartment. The storage capacity of each compartment, the storage demand for each product, and the linear cost of storing one unit of a product in a given compartment are specified. The problem is reformulated as a large set-packing problem, and a column generation scheme is devised to solve the associated linear programming problem. In case of fractional solutions, a branch and bound procedure is utilized. Computational results are presented.     

The one-period,N-location distribution problem

This paper studies the one-period, general network distribution problem with linear costs. The approach is to decompose the problem into a transportation problem that represents a stocking decision, and into decoupled newsboy problems that represent the realization of demand with the usual associated holding and shortage costs. This approach leads to a characterization of optimal policies in terms of the dual of the transportation problem. This method is not directly suitable for the solution for large problems, but the exact solution for small problems can be obtained. For the numerical solutions of large problems, the problem has been formulated as a linear program with column generation. This latter approach is quite robust in the sense that it is easily extended to incorporate capacity constraints and the multiproduct case.     

Book reviews

Soviet Nuclear Strategy from Stalin to Gorbachev: a Revolution in Soviet Military and Political Thinking. By Honore M. Catudal. Mansell, London (1988), ISBN 0–7201–2000–4, £25.00

The Military: More Than Just a Job? Edited by Charles C. Moskos and Frank R. Wood. Pergamon‐Brassey's, London (1988), ISBN 0–08–034321‐X, £17.00 ($30.00)

Douglas Haig, 1861–1928. By Gerard J. de Groot. Unwin Hyman, London (1988), ISBN 004 4401922, £20.00

Defence Policy Making. A Comparative Analysis. Edited by G. M. Dillon. Leicester University Press, Leicester (1988), ISBN 0–715–1268–5, £10.95

The Future of U.K. Air Power. Edited by P. Sabin. Brassey's, London (1988), ISBN 0–08–035825‐X (hardcover), 0–08–036256–7 (flexicover), hardcover £18.95 ($34.00), flexicover £9.95 ($17.95)     

Interrelationships between performance measures for the machine-repairman problem

The machine-repairman problem with heterogeneous machines and multiple repairmen is considered. It is assumed that machine up times and repair times have general distributions, and a work-conserving service discipline is employed. Under these general assumptions, steady-state relationships between performance measures are examined for the individual machines. Also, various performance measures are defined for the aggregate system and interrelationships between these measures are established.     

Interactive multicriteria linear programming: An extension of the method of Zionts and Wallenius

This article presents an extension of the interactive multicriteria linear-programming method of Zionts and Wallenius [see Management Science, 29 (5) (1983)]. The decision maker's underlying utility function is assumed to be pseudoconcave, and his preference structure is assessed through pairwise comparison questions. In the method of Zionts and Wallenius, the decision maker's preference structure is represented as constraints on the weights on the objectives derived from his responses. This representation is only a linear approximation to the underlying nonlinear utility function. Accordingly, inconsistency among the constraints on the weights arises while solving the problem. Therefore, some of the constraints have to be dropped, resulting in a loss of information on the preference structure, and hence an increase in the total number of questions. In this article we develop a hybrid representation scheme to avoid this problem. The proposed scheme is implemented within the algorithmic framework of the method of Zionts and Wallenius, and its underlying theory is developed. Computational results show that the number of questions required by the Zionts and Wallenius method can be sinificantly reduced using the proposed scheme.     

Facility location on a grid with a diagonal line

This article extends the traditional median problem on a grid to include a diagonal line (e.g., a street). In contrast to the traditional median problem, this generalized problem is nonconvex and nonseparable, invalidating some of the properties on which well-known median-seeking algorithms are based. This work presents an algorithm for finding the median on this generalized grid and discusses the relationship between it and the traditional median.     

A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop

We present a shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop. The method decomposes the job shop into a number of single‐machine subproblems that are solved one after another. Each machine is scheduled according to the solution of its corresponding subproblem. The order in which the single machine subproblems are solved has a significant impact on the quality of the overall solution and on the time required to obtain this solution. We therefore test a number of different orders for solving the subproblems. Computational results on 66 instances with ten jobs and ten machines show that our heuristic yields solutions that are close to optimal, and it clearly outperforms a well‐known dispatching rule enhanced with backtracking mechanisms. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 1–17, 1999