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.

We explore visit-order policies in nonsymmetric polling systems with switch-in and switch-out times, where service is in batches of unlimited size. We concentrate on so-called “Hamiltonian tour” policies in which, in order to give a fair treatment to the various users, the server attends every nonempty queue exactly once during each round of visits (cycle). The server dynamically generates a new visit schedule at the start of each round, depending on the current state of the system (number of jobs in each queue) and on the various nonhomogeneous system parameters. We consider three service regimes, globally gated, (locally) gated, and exhaustive, and study three different performance measures: (1) minimizing the expected weighted sum of all sojourn times of jobs within a cycle; (2) minimizing the expected length of the next cycle, and (3) maximizing the expected weighted throughput in a cycle. For each combination of performance measure and service regime, we derive characteristics of the optimal Hamiltonian tour. Some of the resulting optimal policies are shown to be elegant index-type rules. Others are the solutions of deterministic NP-hard problems. Special cases are reduced to assignment problems with specific cost matrices. The index-type rules can further be used to construct fixed-order, cyclic-type polling tables in cases where dynamic control is not applicable.

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.

We consider the transformation T that takes a distribution F into the distribution of the length of the interval covering a fixed point in the stationary renewal process corresponding to F. This transformation has been referred to as size-biasing, length-biasing, the renewal length transformation, and the stationary lifetime operator. We review and develop properties of this transformation and apply it to diverse areas.

Motivated by large-scale service systems, we consider an infinite-server queue with batch arrivals, where the service times are dependent within each batch. We allow the arrival rate of batches to be time varying as well as constant. As regularity conditions, we require that the batch sizes be i.i.d. and independent of the arrival process of batches, and we require that the service times within different batches be independent. We exploit a recently established heavy-traffic limit for the number of busy servers to determine the performance impact of the dependence among the service times. The number of busy servers is approximately a Gaussian process. The dependence among the service times does not affect the mean number of busy servers, but it does affect the variance of the number of busy servers. Our approximations quantify the performance impact upon the variance. We conduct simulations to evaluate the heavy-traffic approximations for the stationary model and the model with a time-varying arrival rate. In the simulation experiments, we use the Marshall–Olkin multivariate exponential distribution to model dependent exponential service times within a batch. We also introduce a class of Marshall–Olkin multivariate hyperexponential distributions to model dependent hyper-exponential service times within a batch.

A two–time scale stochastic approximation algorithm is proposed for simulation-based parametric optimization of hidden Markov models, as an alternative to the traditional approaches to “infinitesimal perturbation analysis.” Its convergence is analyzed, and a queueing example is presented.

Observations may be taken from one of the two populations. A randomized selection rule is one that chooses the populations according to some determined odds. The odds for choosing a population the next time may be dependent on all the observations taken so far from both populations. In this paper, the odds are made for the randomized selection rule in such a way that the number of observations from the better population relative to the number of observations from the other population grows at prescribed rates, typically of exponential order or faster. The rules include randomized play-the-winner rules and randomized analogues of Robbins' rules. Some Monte Carlo investigations are conducted to study these randomized selection rules for moderate sample sizes.

Consider a system of queuing stations in tandem having both flexible servers (who are capable of working at multiple stations) and dedicated servers (who can only work at the station to which they are dedicated). We study the dynamic assignment of servers to stations in such systems with the goal of maximizing the long-run average throughput. We also investigate how the number of flexible servers influences the throughput and compare the improvement that is obtained by cross-training another server (i.e., increasing flexibility) with the improvement obtained by adding a resource (i.e., a new server or a buffer space). Finally, we show that having only one flexible server is sufficient for achieving near-optimal throughput in certain systems with moderate to large buffer sizes (the optimal throughput is attained by having all servers flexible). Our focus is on systems with generalist servers who are equally skilled at all tasks, but we also consider systems with arbitrary service rates.

Two queues forming two independent Poisson processes are served by one server with exponential service time. The server always works on the longer queue and, in case that they are of equal length, chooses either one with probability ½. Let πij be the probability that the two queue lengths equal i andj at equilibrium and π(z, w) = ∑πi j Ziwj. We determine π(z, w) and derive from this asymptotic formulas forπij as i, j → ∞. These asymptotic formulas are used to study the interdependence of the queue lengths. In particular, we obtain limit laws for the queue lengths conditioned on each other.

We consider a single server system accepting two types of retrial customers, which arrive according to two independent Poisson streams. The service station can handle at most one customer, and in case of blocking, type i customer, i=1, 2, is routed to a separate type i orbit queue of infinite capacity. Customers from the orbits try to access the server according to the constant retrial policy. We consider coupled orbit queues, and thus, when both orbit queues are non-empty, the orbit queue i tries to re-dispatch a blocked customer of type i to the main service station after an exponentially distributed time with rate μi. If an orbit queue empties, the other orbit queue changes its re-dispatch rate from μi to $\mu_{i}^{\ast}$. We consider both exponential and arbitrary distributed service requirements, and show that the probability generating function of the joint stationary orbit queue length distribution can be determined using the theory of Riemann (–Hilbert) boundary value problems. For exponential service requirements, we also investigate the exact tail asymptotic behavior of the stationary joint probability distribution of the two orbits with either an idle or a busy server by using the kernel method. Performance metrics are obtained, computational issues are discussed and a simple numerical example is presented.

We consider binary coherent systems with independent binary components having equal failure probability q. The system DOWN probability is expressed via its signature's combinatorial analogue, the so-called D-spectrum. Using the definition of the Birnbaum importance measure (BIM), we introduce for each component a new combinatorial parameter, so-called BIM-spectrum, and develop a simple formula expressing component BIM via the component BIM-spectrum. Further extension of this approach allows obtaining a combinatorial representation for the joint reliability importance (JRI) of two components. To estimate component BIMs and JRIs, there is no need to know the analytic formula for system reliability. We demonstrate how our method works using the Monte Carlo approach. We present several examples of estimating component importance measures in a network when the DOWN state is defined as the loss of terminal connectivity.

The Coxian-2 distribution is a very useful distribution for queuing and reliability analysis. It is important to know when a general probability distribution can be approximated by a Coxian-2 distribution by fitting the first three moments. For a positive random variable with a squared coefficient of variation larger than 1, a lower bound on its third moment is known for which a three-moment fit exists. To complete the figure, in this note lower and upper bounds on the third moment are derived when the squared coefficient of variation is between 0.5 and 1. Also, we characterize the C2-distributions that correspond to these bounds.

We study the Birnbaum importance of the consecutive-k-out-of-n line and clear up confusion in some claimed but unproved results. We introduce some new techniques which not only prove these claimed results but also generalize them much further. Finally, we extend our results to the 2-out-of-m-out-of-n line.

We consider systems based on sequential order statistics (SOS) with underlying distributions possessing proportional hazard rates (PHRs). In that case, the lifetime distribution of the system can be expressed as a distorted distribution. Motivated by the distribution structure in the case of pairwise different model parameters, a particular class of distorted distributions, the generalized PHR model, is introduced and characterizations of stochastic comparisons for several stochastic orders are obtained. Moreover, results on the asymptotic behavior of some aging characteristics, for example, the hazard rate and the mean residual life function, of general distorted distributions as well as related bounds are given. The results are supplemented with limiting properties of the systems in the case of possibly equal model parameters. Some examples are presented in order to illustrate the application of the findings to systems based on SOS and also to systems with independent heterogeneous components.

In general, finite mixtures of distributions with increasing failure rates are not increasing. However, conditions have been given by Lynch [8] so that a mixture of distributions with increasing failure rates has increasing failure rate. We establish similar results for other standard classes and also give examples which show that although the assumptions are stringent, continuous mixtures of standard families of lifetime distributions do have increasing failure rates. We also show that the result of Lynch follows from Savits [12] and the techniques of the last-cited paper can be applied to other classes as well.

Consider an M/G/1 type queueing system with two service modes: regular speed and high speed. The service rule is characterized by two switch-over levels nR and nH, where nR and nH are given integers with 0 ≤ nH < nR. The server switches from regular speed mode to high speed mode when the number of customers present at a service completion epoch is equal to or larger than nR and switches from high speed mode to regular speed mode when the number of customers present decreases to nH. A key feature of the model is that the server takes a vacation for setup operations before a new service mode is available. This paper derives for the general model an expression for the generating function of the equilibrium queue-length distribution in terms of the switch-over levels. Two unknown parameters appear in the generating functions. Using a recursive method, we solve these unknown parameters and obtain a computationally tractable algorithm for the steady-state probabilities.

Simulation-based policy iteration (SBPI) is a modification of the policy iteration algorithm for computing optimal policies for Markov decision processes. At each iteration, rather than solving the average evaluation equations, SBPI employs simulation to estimate a solution to these equations. For recurrent average-reward Markov decision processes with finite state and action spaces, we provide easily verifiable conditions that ensure that simulation-based policy iteration almost-surely eventually never leaves the set of optimal decision rules. We analyze three simulation estimators for solutions to the average evaluation equations. Using our general results, we derive simple conditions on the simulation run lengths that guarantee the almost-sure convergence of the algorithm.

In the present article, we develop some efficient bounds for the distribution function of a two-dimensional scan statistic defined on a (double) sequence of independent and identically distributed (i.i.d.) binary trials. The methodology employed here takes advantage of the connection between the scan statistic problem and an equivalent reliability structure and exploits appropriate techniques of reliability theory to establish tractable bounds for the distribution of the statistic of interest. An asymptotic result is established and a numerical study is carried out to investigate the efficiency of the suggested bounds.

Stochastic automata networks (SANs) have recently received much attention in the literature as a means to analyze complex Markov chains in an efficient way. The main advantage of SANs over most other paradigms is that they allow a very compact description of the generator matrix by means of much smaller matrices for single automata. This representation can be exploited in different iterative techniques to compute the stationary solution. However, the set of applicable solution methods for SANs is restricted, because a solution method has to respect the specific representation of the generator matrix to exploit the compact representation. In particular, aggregation/disaggregation (a/d) methods cannot be applied in their usual realization for SANs without losing the possibility to exploit the compact representation of the generator matrix.

In this paper, a new a/d algorithm for SANs is introduced. The algorithm differs significantly from standard a/d methods because the parts to be aggregated are defined in a completely different way, exploiting the structure of the generator matrix of a SAN. Aggregation is performed with respect to single automata or sets of automata, which are the basic parts generating a SAN. It is shown that the new algorithm is efficient even if the automata are not loosely coupled.

The length biased distribution occurs naturally for some sampling plans in reliability, biometry, and survival analysis. In this note, inequalities for length biased distributions are proved for monotone hazard functions and mean residual life functions. The problem of sampling and selection of experiments from the length biased distribution as opposed to the original distribution is addressed. Certain modified cross-entropy measures are also investigated.