In 1989, Boland, Proschan, and Tong [2] introduced the notion of criticality ranking among nodes and developed a procedure for obtaining an optimal assignment of components in coherent systems. In this article we obtain characterizations of the criticality ranking in terms of minimal cut (path) sets for coherent systems. Furthermore, utilizing the characterizations, it is shown that the criticality ranking defined by Boland et al. [2] is consistent with the cut-importance ranking introduced by Butler in 1979 [4]. A relationship between the criticality ranking and the well-known and widely used Birnbaum reliability importance measure is also derived.

Results and conditions that quantify the decrease in dependence with lag for stationary Markov chains are obtained. Notions of dependence that are used are the concordance or positive quadrant dependence ordering, measures of dependence based on ψ-divergences such as the relative entropy measure of dependence, and the Goodman-Kruskal measure of association. The general results are mainly for first-order Markov chains, but there are also some results for higher order Markov chains.

There is a growing interest in networks of queues with customers and signals. The signals in these models carry commands to the service nodes and trigger customers to move instantaneously within the network. In this note we consider networks of queues with signals and random triggering times; that is, when a signal arrives at a node, it takes a random amount of time to trigger a customer to move with distribution depending on the source of the signal. By appropriately choosing the triggering times, we can obtain network models such that a signal changes a customer's service time distribution – for example, the signal increases or decreases the service time of a customer. We show that the stationary distribution of this model has a product form solution.

We construct a version of the recently developed Poisson-Arrival-Location Model (PALM) to study communicating mobiles on a highway, giving the distribution of calls in progress and handoffs as a function of time and space. In a PALM arrivals generated by a nonhomogeneous Poisson process move independently through a general state space according to a location stochastic process. If, as an approximation, we ignore capacity constraints, then we can use this model to describe the performance of wireless communication systems. Our basic model here is for traffic on a one-way, single-lane, semi-infinite highway, with movement specified by a deterministic location function. For the highway PALM considered here, key quantities are the call density, the handoff rate, the call-origination-rate density and the call-termination-rate density, which themselves are simply related by two fundamental conservation equations. We show that the basic highway PALM can be applied, together with independent superposition, to treat more complicated models. Our analysis provides connections between teletraffic theory and highway traffic theory.

Consider a system consisting of a number of modules. The probability that a particular module is among the ones that have already failed by the time of system failure can be used as a measure of the importance of that module. In El-Neweihi and Sethuraman [6], this probability was called the role of a module in the failure of a system and its properties were developed. In this article we propose the number of failed modules from among a particular subgroup of modules as the basis for measuring the role of that subgroup of modules. We study some monotonicity properties of the distribution of that random variable, in some second order r-out-of-k systems. We illustrate the possible extensions of these results to multistate systems. Yet another measure of the role of a particular subgroup of modules can be based on the number of failed components from this subgroup by the time of system failure. We derive some monotonicity properties of the expected value of the number of such failed components.

Simulated annealing is a class of sequential search techniques for solving continuous global optimization problems. In this paper we attempt to help explain the success of simulated annealing for this class of problems by studying an idealized version of this algorithm, which we call adaptive search. The prototypical adaptive search algorithm generates a sequence of improving points drawn conditionally from samples from a corresponding sequence of probability distributions. Under the condition that the sequence of distributions stochastically dominate in objective function value the uniform distribution, we show that the expected number of improving points required to achieve the global optimum within a prespecified error grows at most linearly in the dimension of the problem for a large class of global optimization problems. Moreover, we derive a cooling schedule for simulated annealing, which follows in a natural way from the definition of the adaptive search algorithm.

In this paper we consider a fluid model of a single buffer in a random external environment modeled by an Ornstein-Uhlenbeck process. Such a model appears as the limiting case of the multiplexing model of Anick, Mitra, and Sondhi [2] in a heavy traffic environment. We use the change of measure technique to derive an exponential upper bound on the tail probabilities of the steady-state buffer content. We also establish an asymptotic upper and lower exponential bounds on the tail probabilities.

This note extends a recently proposed approximation for the loss probability to the batch-arrival Finite-buffer queues with complete rejection. Also, a condition is stated under which the approximation is exact.

For n-dimensional survival functions, we study some probabilistic aspects of the Schur-constant property. The latter is of interest in that it extends the “lack-of-memory” property in a Bayesian context. Some general facts are studied in detail, and related results about interdependence, aging, and extendibility are presented.

In this paper we analyze a queueing network consisting of parallel queues and arriving customers that have to be assigned to one of the queues. The assignment rule may not depend on the numbers of customers in the queues. Our goal is to find a policy that is optimal with respect to the long-run average cost. We will consider two cases: holding costs and waiting times. A recently developed algorithm for Markov decision chains with partial state information is applied. It turns out that the periodic policies found by this algorithm are close, if not equal, to the optimal ones.

Parallel processing systems with jobs structured as random graphs, where the nodes correspond to executable tasks and the directed edges to precedence constraints, are studied from a queueing theoretic point of view under general stationarity assumptions on the job flows. Jobs need to have their tasks processed non-preemptively by a set of uniform processors. Simple, natural greedy schemes of allocating processors to tasks are shown to asymptotically minimize the long-term average execution time per job. The stability condition for this queueing system is specified, and greedy allocation schemes are shown to stabilize the system under the maximum possible job arrival rate. Some recurrence properties of the system state are also established.

We describe a model for a random failure set in a fixed interval of the real line. (Failure sets are considered in input-domain-based theories of software reliability.) The model is based on an extended binary splitting process. Within the described model, we investigate the problem of how to select k test points such that the probability of finding at least one point of the failure set is maximized. It turns out that for values k > 2, the objective functions to be maximized are closely related to solutions of the Poisson-Euler-Darboux partial differential equation. Optimal test points are determined for arbitrary k in an asymptotic case where the failure set is, in a certain sense, “small” and “intricate,” which is the relevant case for practical applications.

This paper provides simple conditions for when the reliability of a system of independent components is better (worse) than the average reliability of the components. This result is useful in cases where little is known of the component reliabilities or the structure.

The paper considers representations of network reliability measures as the mean value of a random variable defined on the trajectories of a certain Markov process and investigates utility of such formulae for Monte Carlo (MC) estimating. Such an MC estimator is called (ε,δ)-polynomial if its relative error is less than ε with probability >1 – δ, for any sample size equal to or greater than a polynomial of ε-1, δ-1, and the size of the network. One of the main results: The suggested MC estimator for the disconnectedness probability of a multiterminal network is (ε,δ)-polynomial, under a certain natural condition on the edge failure probabilities. The method applies also to estimating the percolation critical point and certain equilibrium characteristics of renewal networks.

Motivated by stochastic allocation problems, we study sufficient conditions that imply a general class of stochastic arrangement inequalities. This class includes many known and useful arrangement inequalities in the literature. Some illustrative examples in reliability theory are also given.

To date, research in shock models has been primarily concerned with the classpreserving properties of certain shock and damage kernels. This article focuses on the order-preserving properties of those kernels. We show that they preserve stochastic ordering, hazard rate ordering, backward hazard rate ordering, and likelihood ratio ordering.

Frequency measurements by means of zero-crossing-counting device can be disturbed by noise in many different ways, such as fluctuating zero level or extra zero crossings. This paper presents a mathematical theory for analysis of the effect of noise on a zero-crossing counter. Comparisons are made with experiments made on the production of clicks in a zero-crossing-detecting FM receiver.

In this note using the notion of node criticality in Boland, Proschan, and Tong [2] and modular decompositions of coherent systems, we obtain algorithms and guidelines for allocating components in a k-out-of-R parallel modules system to maximize the system reliability. An illustrative example is given to compare a special case of our results with the previous result for series-parallel systems due to El-Neweihi, Proschan, and Sethuraman [5].

A multi-period model of interruptible electric power service that includes early notification may be described as a stochastic control problem: whom to notify when. When customer interruption losses are multiplicative or submodular, an optimal priority ordering exists, allowing for a simple notification policy.