We consider a network of N identical /M/l or /M/∞ queues. There are two types of arriving customers, those that have no routing choice, and those that first pick r queues at random, and are then routed to the least busy of those queues. We derive the limiting distribution of queue lengths as N→∞, and investigate how this distribution varies with r. We show that even a small amount of routing choice can lead to substantial gains in performance through resource pooling. We corroborate these conclusions by carrying out some simulations of a related model, from which the previous model can be derived by an exchangeable queue simplification. We also observe that the exchangeable queue simplification results in a performance gain for some parameters, in contrast to earlier work.

We establish functional large deviation principles (FLDPs) for waiting and departure processes in single-server queues with unlimited waiting space and the first-in first-out service discipline. We apply the extended contraction principle to show that these processes obey FLDPs in the function space D with one of the nonuniform Skorohod topologies whenever the arrival and service processes obey FLDPs and the rate function is finite for appropriate discontinuous functions. We apply our previous FLDPs for inverse processes to obtain an FLDP for the waiting times in a queue with a superposition arrival process. We obtain FLDPs for queues within acyclic networks by showing that FLDPs are inherited by processes arising from the network operations of departure, superposition, and random splitting. For this purpose, we also obtain FLDPs for split point processes. For the special cases of deterministic arrival processes and deterministic service processes, we obtain convenient explicit expressions for the rate function of the departure process, but not more generally. In general, the rate function for the departure process evidently must be calculated numerically. We also obtain an FLDP for the departure process of completed work, which has important application to the concept of effective bandwidths for admission control and capacity planning in packet communication networks.

A machining process produces a batch of n units every time period. At the end of the period, the units are inspected (provided inspection is cost free). Based on the inspection and the quality data as well as the system history, a decision is made as to whether the process is in control. If not, the process is “revised,” in terms of machine recalibration, maintenance, or repair. In the presence of inspection cost, there is also the need to decide whether to inspect the produced batch. We formulate the problem as Markov decision programs, considering both discounted and average costs. We prove the optimality of certain threshold policies, and characterize the monotone behavior of the optimal thresholds.

We consider a monotone multistate system with conditionally independent components given the component reliabilities, and random component reliabilities. Upper and lower bounds are derived for the moments of the random reliability function, extending results for binary systems. The second moment is given special attention, as this quantity is used to calculate the standard deviation of the system reliability estimate. The motivation for the paper is to establish a basis for uncertainty analysis and Bayesian estimation in connection with multistate systems.

This paper presents an exact derivation of the statistical distribution of the signal to interference-plus-noise ratio (SINR) for optimum linear combining in wireless systems with multiple cochannel interferes, Rayleigh fading, and additive white Gaussian noise. The distribution of the SINR is shown to be remarkably simple and leads to bounds on the bit error rate and outage probabilities which are tighter, simpler, and more robust than any previous results. The simplicity of the SINR distribution permits extremely fast computation of outage probabilities for any number of interference channels and diversity levels. Hence for wireless systems it enables performance studies to be performed over a much wider range of conditions, such as shadow fading, specific channel allocation methods, etc. Previously such studies were extremely limited due to the intensive computational requirements of simulating these systems.

Let S0,…,Sn be a symmetric random walk that starts at the origin (S0 = 0) and takes steps uniformly distributed on [— 1,+1]. We study the large-n behavior of the expected maximum excursion and prove the estimate

,

where c = 0.297952.... This estimate applies to the problem of packing n rectangles into a unit-width strip; in particular, it makes much more precise the known upper bound on the expected minimum height, O(n½), when the rectangle sides are 2n independent uniform random draws from [0,1].

In this paper, we study the asymptotic equipartition property (AEP) for a nonhomogeneous Markov information source. We first give a limit theorem for the averages of the functions of two variables of this information source by using the convergence theorem for the martingale difference sequence. As corollaries, we get several limit theorems and a limit theorem of the relative entropy density, which hold for any nonhomogeneous Markov information source. Then, we get a class of strong laws of large numbers for nonhomogeneous Markov information sources. Finally, we prove the AEP for a class of nonhomogeneous Markov information sources.

We model the virtual contention queue in an ATM nonblocking packet switch with capacity c and input queues by a Geox1, Geox2/D/c Head-of-Line priority queueing system with Random Order Selection within each class and find the joint queue length distribution and the waiting time distribution for each class.

In this short note, we give a counterexample to a conjecture of Koole (1995, Stochastic scheduling and dynamic programming) concerning the equivalence of two orderings arising in the context of a customer assignment model with asymmetric service times.

Given a Markov chain on a countable state space, we present a Lyapunov (sufficient) condition for existence of an invariant probability with a geometric tail.

A two timescale stochastic approximation scheme which uses coupled iterations is used for simulation-based parametric optimization as an alternative to traditional “infinitesimal perturbation analysis” schemes. It avoids the aggregation of data present in many other schemes. Its convergence is analyzed, and a queueing example is presented.

We study an optimal stopping problem for a nonhomogeneous Markov process, with a reward function that is lower semicontinuous everywhere and smooth in certain regions. We prove that the payoff (value function) is lower semicontinuous as well and solves a so-called generalized Stefan problem in each of these regions. We provide some results for the geometry of the “stopping observations” set. Our results generalize those in Bassan, Brezzi, and Scarsini (1996). The problem we consider stems from an economic model in which several self-interested agents desire information, whereas a social planner, although benevolent toward the agents, might decide to withhold information in order to induce diversification in their behavior.

A statistic for testing the null hypothesis that F is the exponential distribution against the alternative of harmonic new better than used in expectation (HNBUE) is proposed. The asymptotic distribution theory for this statistic is derived under the null hypothesis and asymptotic relative efficiency (ARE) with respect to other competing tests for HNBUE is evaluated. This test is applied to the leukemia data described in Bryson and Siddiqui (1969).