This paper is concerned with how coupling can be used to enhance the efficiency of a certain class of terminating simulations, in Markov process settings in which the stationary distribution is known. We are able to theoretically establish that our coupling-based estimator is often more efficient than the naive estimator. In addition, we discuss extensions of our methodology to Markov process settings in which conventional coupling fails and show (for Doeblin chains) that knowledge of the stationary distribution is sometimes unnecessary.

The total hazard Monte Carlo estimator has been successfully applied to estimate the unreliability of multicomponent systems. Nevertheless, there are some cases where it is less efficient than the crude estimator. We propose in this paper a simple modification that improves the performance of the total hazard estimator.

A variety of methods for reducing the variance on Monte Carlo estimators of the expected waiting time Wn of the nth customer in a GI/G/1 queue are studied. The ideas involve Spitzer's identity, importance sampling, and sums with stratified or controlled randomized length.

Consider a renewal process [N(t), t>0]. For fixed t > 0 and each n ≥ 1, let yn,1, …, Yn,n be independent exponentials each having mean t/n, independent of the renewal process. Ross [2] developed a recursion for the sequence of approximations mn = EN(Yn,1 + … + Yn,n) that converges to m(t)if the renewal function m(·) = EN(·) is continuous at t > 0. In this note, we derive an upper bound on the rate of convergence of this sequence under mild conditions on m near t. Tightness of this bound is discussed in terms of regularity conditions on m.

We present necessary and suffi2ient Foster-type conditions for a countable state Markov chain to have an invariant probability with at least a geometric tail. These conditions are obtained by using a generalized Farkas Theorem in Linear Algebra. The purpose of this note is also to pose an interesting and important research problem that is still largely open.

We discuss socially optimal and equilibrium retrial rates in a single-server queueing model. We extend known results, compare the two rates, and suggest ways to impose tolls on retrials (or rebates for waiting) in order to equate the equilibrium rate with the socially optimal one.

We study the problem of scheduling multiclass parallel server queues where the cost for each job is a general class-dependent function of the job's completion time and a second random variable. We characterize the structure of the optimal policy under fairly general conditions on the random variables.

Fixed point approximations for blocking probabilities arising from a link independence assumption and a light retrial rate limit are derived for circuitswitched network models that incorporate caller retrials. This approximation is a generalization of the well-known reduced load approximation for loss networks, which retains much of the versatility of this approximation.

We consider an M/G/1 queue with the special feature of additional negative customers, who arrive according to a Poisson process. Negative customers require no service, but at their arrival a stochastic amount of work is instantaneously removed from the system. We show that the workload distribution in this M/G/1 queue with negative customers equals the waiting time distribution in a GI/G/1 queue with ordinary customers only; the effect of the negative customers is incorporated in the new arrival process.

In this paper, we study the problem of dynamic allocation of a single server to parallel queues with finite-capacity buffers. The arrival processes are mutually independent, equal rate Poisson processes, and the service times are independent and identically distributed random variables with an arbitrary distribution. We are interested in characterizing the allocation policy that stochastically minimizes the number of customers lost due to buffer overflows. Using a coupling argument, we establish the optimality of the Fewest-Empty-Spaces policy, which allocates the server to the queue with the fewest empty buffer spaces, within the class of nonpreemptive and nonidling policies. The result extends to the class of preemptive policies, if the service times are exponentially distributed. We also briefly discuss the allocation problem under more general statistical assumptions on the arrival processes.

This paper shows that the equilibrium distribution of a queueing network with batch routing continues to be of product form if a batch that cannot enter its destination — for example, as a consequence of capacity constraints — immediately triggers a new transition that takes up the whole batch.

For a class of performability models with component-interdependent repairs and breakdowns, monotonicity is shown over time for expected availability measures. This result is of interest to justify steady-state bounds.