The constrained shortest path problem

The shortest path problem between two specified nodes in a general network possesses the unimodularity property and, therefore, can be solved by efficient labelling algorithms. However, the introduction of an additional linear constraint would, in general, destroy this property and the existing algorithms are not applicable in this case. This paper presents a parametric approach for solving this problem. The algorithm presented would require, on the average, a number of iterations which is polynomially bounded. The similarity of this approach to that of the generalized Lagrange multiplier technique is demonstrated and a numerical example is presented.     

Optimal replacement under additive damage in randomly varying environments

A system is subject to a sequence of randomly occurring shocks. Each shock causes a random amount of damage which accumulates additively. Any of the shocks might cause the system to fail. The shock process is in some sense related to an environmental process in order to describe randomly varying external factors of an economical and/or technical nature as well as internal factors of a statistical nature. A discrete time formulation of the problem is given. Sufficient conditions are found for optimality of a generalized control-limit rule with respect to the total cost criterion: Whenever the accumulated damage s is not less than a specified critical number t(i), depending on the environmental state i, replace the system by a new one; otherwise do not replace it. Moreover, bounds are given for these critical numbers.     

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.     

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.     

Gittins-index heuristics for research planning

The classical work of Gittins, which resulted in the celebrated index result, had applications to research planning as an important part of its motivation. However, research planning problems often have features that are not accommodated within Gittins's original framework. These include precedence constraints on the task set, influence between tasks, stopping or investment options and routes to success in which some tasks do not feature. We consider three classes of Markovian decision models for research planning, each of which has all of these features. Gittins-index heuristics are proposed and are assessed both analytically and computationally. They perform impressively. © 1995 John Wiley & Sons, Inc.     

Optimal timing schedules in earliness-tardiness single machine sequencing

The article deals with a single machine earliness-tardiness scheduling model where idle times are permitted in job processing. Based on a cluster concept we develop properties of the model that lead to a very fast algorithm to find an optimal timing schedule for a given sequence of jobs. The performance of this algorithm is tested on 480 randomly generated problems involving 100, 200, 400 and 500 jobs. It takes less than two seconds to solve a 500 job problem on a PC. © 1995 John Wiley & Sons, Inc.     

Log‐concave and concave distributions in reliability

Nonparametric classes of life distributions are usually based on the pattern of aging in some sense. The common parametric families of life distributions also feature monotone aging. In this paper we consider the class of log‐concave distributions and the subclass of concave distributions. The work is motivated by the fact that most of the common parametric models of life distributions (including Weibull, Gamma, log‐normal, Pareto, and Gompertz distributions) are log‐concave, while the remaining life of maintained and old units tend to have a concave distribution. The classes of concave and log‐concave distributions do not feature monotone aging. Nevertheless, these two classes are shown to have several interesting and useful properties. We examine the closure of these classes under a number of reliability operations, and provide sharp reliability bounds for nonmaintained and maintained units having life distribution belonging to these classes. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 419–433, 1999