It is known that a threshold policy (or trunk reservation policy) is optimal for Erlang's loss system under certain assumptions. This paper examines the robustness of this policy under departures from the standard assumption of Poisson arrivals and shows that the optimal policy has a generalized trunk reservation form.

The relaxation time for an ergodic Markov process is a measure of the time until ergodicity is reached from its initial state. In this paper the relaxation time for an ergodic truncated birth-death process is studied. It is shown that the relaxation time for such a process on states {0,1, …, N} is the quasi-stationary exit time from the set {,2, …, N{0,1,…, N, N + 1} with two-sided absorption at states 0 and N + 1. The existence of such a dual process has been observed by Siegmund [15] for stochastically monotone Markov processes on the real line. Exit times for birth- death processes with two absorbing states are studied and an efficient algorithm for the numerical evaluation of mean exit times is presented. Simple analytical lower bounds for the relaxation times are obtained. These bounds are numerically accessible. Finally, the sensitivity of the relaxation time to variations in birth and death rates is studied.

Standard server assignment policies for multi-server queueing stations include the noncollaborative policy, where the servers work in parallel on different jobs; and the fully collaborative policy, where the servers work together on the same job. However, if each job can be decomposed into subtasks with no precedence relationships, then we consider a form of server coordination named task assignment where the servers work in parallel on different subtasks of the same job. We identify the task assignment policy that maximizes the long-run average throughput of a queueing station with finite internal buffers when blocked servers can be idled or reassigned to either replace or collaborate with other servers on unblocked subtasks. We then compare the server coordination policies and show that the task assignment is best when the servers are highly specialized; otherwise, the fully collaborative or noncollaborative policies are preferable depending on whether the synergy level among the servers is high or not. We also provide numerical results that quantify our previous comparison. Finally, we address buffer allocation in longer lines where there are precedence relationships between some of the tasks, and present numerical results that suggest our comparisons for one queueing station generalize to longer lines.

In this paper, we consider a two-stage call center staffing model. In the first stage, the interval staffing levels are set under arrival rate uncertainty. In the second stage, these initial staffing levels are corrected to the right value based on more precise arrival rate information. We show that this problem is of newsvendor type, where the costs are the initial staffing costs plus the second stage adaptation costs. We show that we should initially staff according to a quantile of the distributional forecast, rather than the mean. It is also shown that the errors in staffing are approximately linear in the forecasting errors. This leads to the conclusion that the weighted sum of errors should be the error measurement in call center forecasting, since minimizing, it minimizes the total staffing costs. In special cases where the costs are symmetric for over- and understaffing, this is equivalent to minimizing the weighted absolute percentage error.

We show how the importance sampling identity can often be used to efficiently bound tail probabilities, illustrating with the normal, Poisson, and gamma random variables.

The purpose of this paper is to establish some limit theorems of delayed averages for countable nonhomogeneous Markov chains. The definition of the generalized C-strong ergodicity and the generalized uniformly C-strong ergodicity for countable nonhomogeneous Markov chains is introduced first. Then a theorem about the generalized C-strong ergodicity and the generalized uniformly C-strong ergodicity for the nonhomogeneous Markov chains is established, and its applications to the information theory are given. Finally, the strong law of large numbers of delayed averages of bivariate functions for countable nonhomogeneous Markov chains is proved.

A simulation method is developed for computing average reward optimal policies, for a finite state and action Markovian decision process. It is shown that the method is consistent; i.e., it produces solutions arbitrarily close to the optimal. Various types of estimation errors and confidence bounds are examined. Finally, it is shown that the probability distribution of the number of simulation cycles required to compute an e-optimal policy satisfies a large deviations property.

Motivated by two measures of presortedness, number of runs and oscillation of a permutation, related to the sorting problem, we derive an error bound for normal approximation to the distribution of Here, αij's are given real numbers and π is a uniformly distributed random permutation of {l,…, n}. The derivation is based on Stein's method.

We present results on the finite-time behavior of the discrete-time, finite-space version of the simulated annealing algorithm. The asymptotic and finite-time behavior of the annealing algorithm under slow cooling will be shown to depend on the largest eigenvalue of a certain matrix. To illustrate the utility of our results, we study the slowly cooled annealing algorithm applied to the maximum matching problem and demonstrate a polynomial randomized approximation property of the algorithm.

It has long been observed that independent laboratories differ in reporting the results of repeated experiments. The problem is to detect those laboratories that might be considered aberrant. Previous analyses have been based on an analysis of variance framework or on subset selection for the detection of aberrant laboratories. The present procedure is also based on an ANOVA model but uses a Bayesian estimate of the number of aberrant laboratories. Subsequent to the determination of the aberrant laboratories, a linear model is used to separate sampling and laboratory effects.

In the fall of 1948 in my course on Least Squares in the Department of Mathematical Statistics at Columbia University (and in the spring in Correlation and Chi-Square), I was particularly impressed by one of the students— Gerald J. Lieberman. I was disappointed that this promising student left Columbia after one year, but it was not long until our paths met again. It is a pleasure to dedicate this paper to my colleague and close friend!

We give a computable bound on the rate of convergence of the occupation measure for the Gibbs sampler to the stationary distribution.

A number of data items (1,2,…,n) are to be maintained in a structure which consists of several linear lists. Successive requests to access items are independent random variables, and the probability that a particular request is for item i is pi. The cost of accessing the jth item from the front of a list is j. For a single list, the move-to-front rule (MF) has been extensively studied and has been shown to provide good performance. In some actual circumstances, MF is the only physically realizable or convenient policy. We extend the study of move-to-front by examining the case where items are kept in several lists. Following its access, an item must be replaced at the front of one of the lists. In certain cases, assuming the pi's are known, the policy which minimizes the average retrieval cost takes a particularly simple form: no item is ever moved from the list in which it is placed initially.

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 this paper, we develop a general approach to compute the probabilities of unresolved clones in random pooling designs. This unified and systematic approach gives better insight for handling the dependency issue among the columns and among the rows. Consequently, we identify some faster computation formulas for four random pooling designs proposed in the literature, and we derive some probability distribution functions of the number of unresolved clones that were not available before.

We propose two random network models for complex networks, which are treelike and always grow very fast. One is the uniform model and the other is the preferential attachment model, and both of them depends on a parameter 0<p<1. We first briefly discuss the network sizes, each of which can be corresponding to a supercritical branching process. And then we mainly study the degree distributions of both models. The asymptotic degree distribution of the first one with any parameter 0<p<1 is a geometric distribution with parameter 1/2, whereas that of the second one, which depends on p, can be uniquely determined by a functional equation of its probability generating function.

From health care to maintenance shops, many systems must contend with allocating resources to customers or jobs whose initial service requirements or costs change when they wait too long. We present a new queueing model for this scenario and use a Markov decision process formulation to analyze assignment policies that minimize holding costs. We show that the classic cμ rule is generally not optimal when service or cost requirements can change. Even for a two-class customer model where a class 1 task becomes a class 2 task upon waiting, we show that additional orderings of the service rates are needed to ensure the optimality of simple priority rules. We then show that seemingly-intuitive switching curve structures are also not optimal in general. We study these scenarios and provide conditions under which they do hold. Lastly, we show that results from the two-class model do not extend to when there are n≥3 customer classes. More broadly, we find that simple priority rules are not optimal. We provide sufficient conditions under which a simple priority rule holds. In short, allowing service and/or cost requirements to change fundamentally changes the structure of the optimal policy for resource allocation in queueing systems.

G-Network queueing network models, and in particular the random neural network (RNN), are useful tools for decision making in complex systems, due to their ability to learn from measurements in real time, and in turn provide real-time decisions regarding resource and task allocation. In particular, the RNN has led to the design of the cognitive packet network (CPN) decision tool for the routing of packets in the Internet, and for task allocation in the Cloud. Thus in this paper, we present recent research on how to dynamically create the means for quality of service (QoS) to end users of the Internet and in the Cloud. The approach is based on adapting the decisions so as to benefit users as the conditions in the Internet and in Cloud servers vary due to changing traffic and workload. We present an overview of the algorithms that were designed based on the RNN, and also detail the experimental results that were obtained in three areas: (i) traffic routing for real-time applications, which have strict QoS constraints; (ii) routing approaches, which operate at the overlay level without affecting the Internet infrastructure; and (iii) the routing of tasks across servers in the Cloud through the Internet.

We prove that the effective resistances of spherically symmetric random trees dominate in mean the effective resistances of random trees corresponding branching processes in varying environments and having the same growth law of spherically symmetric trees. We conjecture that the statement does not necessarily hold true in the case of stochastic domination and give an idea of constructing a counterexample.