Let X1,X2,… be an ergodic Markov chain on the countable state space. We construct a strong stationary dual chain X* whose first hitting times give sharp bounds on the convergence to stationarity for X. Examples include birth and death chains, queueing models, and the excess life process of renewal theory. This paper gives the first extension of the stopping time arguments of Aldous and Diaconis [1,2] to infinite state spaces.

We consider a problem in which jobs continually arrive to a set of n processors that are arranged in an ordered list. When a job arrives the first processor in line attempts to process it; if it is unsuccessful then the next in line attempts it, and so on. Each time that processor j attempts to process a job it is, independently of all else, successful with (an unknown) probability pj. After a job has been completed or all n attempts have failed then, based on the result, we can reorder the processors before the next job arrives, with the objective being to minimize the average number of attempts per job. This paper compares the transposition rule and the move to the front rule.

In the classical TDMA, which has been the subject of extensive research in the past, a single slot is allocated to each and every user within every frame. In many situations this leads to an inefficient utilization of the channel calling for a nonhomogeneous allocation of slots. This paper focuses on a generalized TDMA scheme in which users are allocated more than a single slot per frame, not necessarily contiguous. We derive the delay distribution and buffer occupancy for such a scheme as well as the expected values of these quantities.

Consider a stochastic loss network, where calls or customer types arrive and have to find a path through the network to a given destination, and where our aim is to maximize the gain (suitably defined) from the network. In general there will be a number of paths available, and when a call arrives the two questions to answer are first, should the call be accepted, and secondly, if it is accepted which route should it take? The answer to the first question is in some sense harder than the second, and all dynamic routing or control policies have some explicit or implicit mechanism for rejecting calls and so answer the question in some way.

We present a decision procedure to determine the optimal maintenance intervals of a computer software throughout its operational phase. Our model accounts for the average cost per each maintenance activity and the damage cost per failure with the future cost discounted. Our decision policy is optimal in the sense that it minimizes the expected total cost. Our model assumes that the total number of errors in the software has a Poisson distribution with known mean λ and each error causes failures independently of other errors at a known constant failure rate. We study the structures of the optimal policy in terms of λ and present efficient numerical algorithms to compute the optimal maintenance time intervals, the optimal total number of maintenances, and the minimal total expected cost throughout the maintenance phase.

An important problem in reliability theory is to determine the reliability of a system from the reliability of its components. If E is a finite set of components, then certain subsets of E are prescribed to be the operating states of the system. A formation is any collection F of minimal operating states whose union is E. Reliability domination is defined as the total number of odd cardinality formations minus the total number of even cardinality formations. The purpose of this paper is to establish some new results concerning reliability domination. In the special case where the system can be identified with a graph or digraph, these new results lead to some new graph-theoretic properties and to simple proofs of certain known theorems. The pertinent graph-theoretic properties include spanning trees, acyclic orientations, Whitney's broken cycles, and Tutte's internal activity associated with the chromatic polynomial.

A second-order continuous-state-space model for two-dimensional queueing systems is developed in this article. A particular problem is treated but the results can apply to some other two-dimensional queueing problems directly. The generating function for the model is obtained by applying a Riemann boundary value problem and leads to a computationally feasible solution.