A class of Bayes-optimal two-stage screens

Items are characterized by a set of attributes (T) and a collection of covariates (X) associated with those attributes. We wish to screen for acceptable items (T ∈ C_T), but T is expensive to measure. We envisage a two-stage screen in which observation of X_ is used as a filter at the first stage to sentence most items. The second stage involves the observation of T for those items for which the first stage is indecisive. We adopt a Bayes decision-theoretic approach to the development of optimal two-stage screens within a general framework for costs and stochastic structure. We also consider the important question of how much screens need to be modified in the light of resource limitations that bound the proportion of items that can be passed to the second stage. © 1996 John Wiley & Sons, Inc.     

Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems

Until recently, fast algorithms for the maximum flow problem have typically proceeded by constructing layered networks and establishing blocking flows in these networks. However, in recent years, new distance-directed algorithms have been suggested that do not construct layered networks but instead maintain a distance label with each node. The distance label of a node is a lower bound on the length of the shortest augmenting path from the node to the sink. In this article we develop two distance-directed augmenting path algorithms for the maximum flow problem. Both the algorithms run in O(n²m) time on networks with n nodes and m arcs. We also point out the relationship between the distance labels and layered networks. Using a scaling technique, we improve the complexity of our distance-directed algorithms to O(nm log U), where U denotes the largest arc capacity. We also consider applications of these algorithms to unit capacity maximum flow problems and a class of parametric maximum flow problems.     

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.     

A periodic maintenance model with used equipment and random minimal repair

The maintenance strategy considered in this article is in the class of block replacement policies. The working unit is replaced by new ones at instants T,2T,3T,… independently of the age and state of the unit. If a failure occurs between these instants, the random repair cost is evaluated. If it is smaller than a predetermined control limit then a minimal repair is carried out. Otherwise the unit is replaced by a used unit. The performance of this maintenance strategy is evaluated in terms of average total cost per time unit over an infinite time span. The mathematical model is defined and several analytical results are obtained. A computer program has been written, which solves the mathematical problem, and some examples are given for the cases where the underlying life distribution is gamma, Weibull or truncated normal.     

The discrete evasion game with three-move lag

The discrete evasion game with three-move lag, formulated over 30 years ago, was one of the earliest games with time-lag complications. This game remains unsolved even though it is well known that the game has a value. In this article we obtain an upper bound for the value by constructing a strategy which consists of 400 conditional probabilities for the minimizing player. This is believed to be the best upper bound known.     

Asymptotic normality of the estimated optimal order quantity for one-period inventories with supply uncertainty

A one-period inventory situation where the supply is an NBUE random variable with mean proportional to the quantity ordered has been considered. The optimal exponential order quantity, which maximizes the minimum profit obtainable in the NBUE class of supply distributions, is a function of the demand distribution function. Here we show that an estimator of the maximin order quantity, which is already known to converge almost surely to its true value, converges also in distribution to an appropriate normal law with increasing sample size.     

Optimal layered search

This article investigates the problem of planning an optimal layered search for a stationary target. A search is layered if it assigns each point in the search space an integer number of glimpses or looks. General necessary and sufficient conditions and an existence theorem are obtained. The special case in which the initial target distribution is bivariate normal is considered in detail.     

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.