Synchronous working vacation policy for finite-buffer multiserver queueing system

This paper presents modeling and analysis of unreliable Markovian multiserver finite-buffer queue with discouragement and synchronous working vacation policy. According to this policy, c servers keep serving the customers until the number of idle servers reaches the threshold level d; then d idle servers take vacation altogether. Out of these d vacationing servers, d_W servers may opt for working vacation i.e. they serve the secondary customers with different rates during the vacation period. On the other hand, the remaining d − d_W = d_V servers continue to be on vacation. During the vacation of d servers, the other e = c − d servers must be present in the system even if they are idle. On returning from vacation, if the queue size does not exceed e, then these d servers take another vacation together; otherwise start serving the customers. The servers may undergo breakdown simultaneously both in regular busy period and working vacation period due to the failure of a main control unit. This main unit is then repaired by the repairman in at most two phases. We obtain the stationary performance measures such as expected queue length, average balking and reneging rate, throughput, etc. The steady state and transient behaviours of the arriving customers and the servers are examined by using matrix analytical method and numerical approach based on Runge-Kutta method of fourth order, respectively. The sensitivity analysis is facilitated for the transient model to demonstrate the validity of the analytical results and to examine the effect of different parameters on various performance indices.     

Vacation policies for machine repair problem with two type spares

This paper studies the machine repair problem consisting of M operating machines with two types of spare machines (S = S₁ + S₂), and R servers (repairmen) who leave for a vacation of random length when there are no failed machines queuing up for repair in the repair facility. At the end of the vacation the servers return and operate two vacation policies. First, the servers take vacations repeatedly until they find the repair facility has at least one waiting failed machine in the queue. Second, the servers do not take a vacation again and remain idle until the first arriving failed machine arrives, which starts a busy period in the repair facility. For both policies, the servers have two service rates for repair-slow and fast. The matrix geometric theory is used to find the steady-state probabilities of the number of failed machines in the system as well as the performance measures. Some special cases are given. A direct search algorithm is used to simultaneously determine the optimal values of the number of two types of spares and the number of servers while maintaining a minimum specified level of system availability.     

Analysis of Queueing Systems with Synchronous Single Vacation for Some Servers

We study a multi-server M/M/c type queue with a single vacation policy for some idle servers. In this queueing system, if at a service completion instant, any d (d c) servers become idle, these d servers will take one and only one vacation together. During the vacation of d servers, the other c–d servers do not take vacation even if they are idle. Using a quasi-birth-and-death process and the matrix analytic method, we obtain the stationary distribution of the system. Conditional stochastic decomposition properties have been established for the waiting time and the queue length given that all servers are busy.     

Transient behavior ofM/M ij/1 queues

We obtain the time dependent probabilities for the joint distribution of the number of arrivals and departures in [0,t] for theM/M ^ij/1 queue. This queue has the exponential service with parametersμ _ij, depending on the types of the successive customers attended. We provide an intuitive interpretation of the solution and also present some numerical results, including time dependent event probabilities and queue length.     

Queues where customers of one queue act as servers of the other queue

We consider a system comprised of two connected M/M/?/? type queues, where customers of one queue act as servers for the other queue. One queue, Q ₁, operates as a limited-buffer M/M/1/N?1 system. The other queue, Q ₂, has an unlimited-buffer and receives service from the customers of Q ₁. Such analytic models may represent applications like SETI@home, where idle computers of users are used to process data collected by space radio telescopes. Let L ₁ denote the number of customers in Q ₁. Then, two models are studied, distinguished by their service discipline in Q ₂: In Model 1, Q ₂ operates as an unlimited-buffer, single-server M/M/1/∞ queue with Poisson arrival rate λ ₂ and dynamically changing service rate μ ₂ L ₁. In Model 2, Q ₂ operates as a multi-server M/M/L ₁/∞ queue with varying number of servers, L ₁, each serving at a Poisson rate of μ ₂. We analyze both models and derive the Probability Generating Functions of the system’s steady-state probabilities. We then calculate the mean total number of customers present in each queue. Extreme cases are indicated.     

Random evolutions in discrete and continuous time

This paper points out a connection between random evolutions and products of random matrices. This connection is useful in predicting the long-run growth rate of a single-type, continuously changing population in randomly varying environments using only observations at discrete points in time. A scalar Markov random evolution is specified by the n×n irreducible intensity matrix or infinitesimal generator Q = (q_ij) of a time-homogeneous Markov chain and by n finite real growth rates (scalars) s_i. The scalar Markov random evolution is the quantity M^C(t) = exp(Σⁿ_j=1s_jg^C_j (t)), where g^C_j(t) is the occupancy times in state j up to time t. The scalar Markov product of random matrices induced by this scalar Markov random evolution is the quantity M^D(t) = exp(Σⁿ_j=1s_jg^D_j (t)), where g^D_j(t) is the occupancy time in state j up to and including t of the discrete-time Markov chain with stochastic one-step transition matrix P = e^Q. We show that lim_t→∞(1/t)E(logM^D(t))=lim_t→∞(1/t)E(logM^C(t)) but that in general lim_t→∞(1/t)logE(M^C(t)) ≠ lim_t→∞(1/t)logE(M^D(t)). Thus the mean Malthusian parameter of population biologists is invariant with respect to the choice of continuous or discrete time, but the rate of growth of average population size is not. By contrast with a single-type population, in multitype populations whose growth is governed by non-commuting operators, the mean Malthusian parameter may be destined for a less prominent role as a measure of long-run growth.     

<Emphasis Type="Italic">M</Emphasis><Superscript><Emphasis Type="Italic">X</Emphasis></Superscript>/<Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">c</Emphasis> Queue with catastrophes and state-dependent control at idle time

We consider an M ^X /M/c queue with catastrophes and state-dependent control at idle time. Properties of the queues which terminate when the servers become idle are first studied. Recurrence, equilibrium distribution, and equilibrium queue-size structure are studied for the case of resurrection and no catastrophes. All of these properties and the first effective catastrophe occurrence time are then investigated for the case of resurrection and catastrophes. In particular, we obtain the Laplace transform of the transition probability for the absorbing M ^X /M/c queue.     

On the Erlang Loss Model with Time Dependent Input

We consider the M(t)/M(t)/m/m queue, where the arrival rate λ(t) and service rate μ(t) are arbitrary (smooth) functions of time. Letting p_n(t) be the probability that n servers are occupied at time t (0≤ n≤ m, t > 0), we study this distribution asymptotically, for m→∞ with a comparably large arrival rate λ(t) = O(m) (with μ(t) = O(1)). We use singular perturbation techniques to solve the forward equation for p_n(t) asymptotically. Particular attention is paid to computing the mean number of occupied servers and the blocking probability p_m(t). The analysis involves several different space-time ranges, as well as different initial conditions (we assume that at t = 0 exactly n₀ servers are occupied, 0≤ n₀≤ m). Numerical studies back up the asymptotic analysis. AMS subject classification: 60K25,34E10 Supported in part by NSF grants DMS-99-71656 and DMS-02-02815     

A two threshold vacation policy in multiserver queueing systems

We consider a queueing system with c servers and a threshold type vacation policy. In this system, when a certain number d < c of servers become idle at a service completion instant, these d servers will take a synchronous vacation of random length together. After each vacation, the number of customers in the system is checked. If that number is N or more, these d servers will resume serving the queue; otherwise, they will take another vacation together. Using the matrix analytical method, we obtain the stationary distribution of queue length and prove the conditional stochastic decomposition properties. Through numerical examples, we discuss the performance evaluation and optimization issues in such a vacation system with this (d, N) threshold policy.     

Analyzing Ek|Er|c queues

In this paper we study a system consisting of c parallel identical servers and a common queue. The service times are Erlang-r distributed and the interarrival times are Erlang-k distributed. The service discipline is first-come first-served. The waiting process may be characterized by (n₋₁, n₀, n₁,…, n_c) where n₋₁ represents the number of remaining arrival stages, n₀ the number of waiting jobs and n_i, i = 1,…, c, the number of remaining service stages for server i. Bertsimas has proved that the equilibrium probability for saturated states (i.e. states with all servers busy) can be written as a linear combination of geometric terms with n₀ as exponent. In the present paper it is shown that the coefficients also have a geometric form with respect to n₋₁, n₁, …, n_c. It is also shown how the factors may be found efficiently. The present paper uses a direct approach for solving the equilibrium equations rather than a generating function approach as Bertsimas does. The direct approach is based on separation of variables and has been inspired by previous work of two of the authors on the shortest queue problem in particular and the two-dimensional random walk more generally. The characterization of the equilibrium probabilities leads to exact expressions for performance measures such as the moments of the queue length and the waiting time, which are useful for numerical computations. Numerical results are presented.     

Asymptotic formula for the convolution of a generalized divisor function

An asymptotic formula is obtained for the sum of terms σ _it (n)σ_-it (N - n) (t is real) over 0 < n < N with a remainder estimated by O _ε((1+|t|)^1+ε N ^3/4+ε) for any ε > 0. As a consequence, Porter’s result on a power scale for the average number of steps in the Euclidean algorithm is improved.     

Maximum Likelihood Estimates and Confidence Intervals of an M/M/R Queue with Heterogeneous Servers

This paper studies maximum likelihood estimates as well as confidence intervals of an M/M/R queue with heterogeneous servers under steady-state conditions. We derive the maximum likelihood estimates of the mean arrival rate and the three unequal mean service rates for an M/M/3 queue with heterogeneous servers, and then extend the results to an M/M/R queue with heterogeneous servers. We also develop the confidence interval formula for the parameter ρ, the probability of empty system P ₀, and the expected number of customers in the system E[N], of an M/M/R queue with heterogeneous servers     

Asymptotic estimates for the principal eigenvalue of the laplacian in a geodesic ball

LetM be a compact Riemannian manifold and letB _ε be a geodesic ball of radiusε with center0 ∈ M. We investigate the asymptotic behavior ofλ _ε , the principal eigenvalue of the Laplace-Beltrami operator on \(M/\bar B_\varepsilon\) with homogeneous Dirichlet boundary conditions. We prove thatλ _ε ~Cφ _n (ε) wheren = dimM, φ ₂ (ε)=(logε ^?1)^?1 andφ _n (ε) = (n-2)ε ^n-2 (n>2). In the case whereM is a model the constantC is explicitly evaluated.     

Some results for the queues Mx/M/c and GIx/ G/c

We develop for the queue M^x/M/c an upper bound for the mean queue length and lower bounds for the delay probabilities (that of an arrival group and that of an arbitrary customer in the arrival group). An approximate formula is also developed for the general bulk-arrival queue GI^x/G/c. Preliminary numerical studies have indicated excellent performance of the results.     

An abstract approach to Loewner chains

We present a new geometric construction of Loewner chains in one and several complex variables which holds on complete hyperbolic complex manifolds and prove that there is essentially a one-to-one correspondence between evolution families of order d and Loewner chains of the same order. As a consequence, we obtain a univalent solution (f _t : M → N) of any Loewner-Kufarev PDE. The problem of finding solutions given by univalent mappings (f _t : M → ? ⁿ ) is reduced to investigating whether the complex manifold ∪ _t≥0 f _t (M) is biholomorphic to a domain in ? ⁿ . We apply such results to the study of univalent mappings f: B ⁿ → ? ⁿ .     

Sharp and simple bounds for the Erlang delay and loss formulae

We prove some simple and sharp lower and upper bounds for the Erlang delay and loss formulae and for the number of servers that invert the Erlang delay and loss formulae. We also suggest simple and sharp approximations for the number of servers that invert the Erlang delay and loss formulae. We illustrate the importance of these bounds by using them to establish convexity proofs. We show that the probability that the M/M/s queue is empty is a decreasing and convex function of the traffic intensity. We also give a very short proof to show that the Erlang delay formula is convex in the traffic intensity when the number of servers is held constant. The complete proof of this classical result has never been published. We also give a very short proof to show that the Erlang delay formula is a convex function of the (positive integer) number of servers. One of our results is then used to get a sharp bound to the Flow Assignment Problem.     

The evolution of the min-min random graph process

We study the following min-min random graph process G=(G₀,G₁,…): the initial state G₀ is an empty graph on n vertices (n even). Further, G_M+1 is obtained from G_M by choosing a pair {v,w} of distinct vertices of minimum degree uniformly at random among all such pairs in G_M and adding the edge {v,w}. The process may produce multiple edges. We show that G_M is asymptotically almost surely disconnected if M≤n, and that for M=(1+t)n, constant, the probability that G_M is connected increases from 0 to 1. Furthermore, we investigate the number X of vertices outside the giant component of G_M for M=(1+t)n. For constant we derive the precise limiting distribution of X. In addition, for n⁻¹ln⁴n≤t=o(1) we show that tX converges to a gamma distribution.     

Two-Phase Stefan Problem as the Limit Case of Two-Phase Stefan Problem with Kinetic Condition

Both one-dimensional two-phase Stefan problem with the thermodynamic equilibrium condition u(R(t),t)=0 and with the kinetic rule u_ε(R_ε(t),t)=εR_ε′(t) at the moving boundary are considered. We prove, when ε approaches zero, R_ε(t) converges to R(t) in C^1+δ/2[0,T] for any finite T>0, 0<δ<1.     

Tandem Queues with Impatient Customers for Blood Screening Procedures

We study a blood testing procedure for detecting viruses like HIV, HBV and HCV. In this procedure, blood samples go through two screening steps. The first test is ELISA (antibody Enzyme Linked Immuno-Sorbent Assay). The portions of blood which are found not contaminated in this first phase are tested in groups through PCR (Polymerase Chain Reaction). The ELISA test is less sensitive than the PCR test and the PCR tests are considerably more expensive. We model the two test phases of blood samples as services in two queues in series; service in the second queue is in batches, as PCR tests are done in groups. The fact that blood can only be used for transfusions until a certain expiration date leads, in the tandem queue, to the feature of customer impatience. Since the first queue basically is an infinite server queue, we mainly focus on the second queue, which in its most general form is an S-server M/G ^[k,?K]/S?+?G queue, with batches of sizes which are bounded by k and K. Our objective is to maximize the expected profit of the system, which is composed of the amount earned for items which pass the test (and before their patience runs out), minus costs. This is done by an appropriate choice of the decision variables, namely, the batch sizes and the number of servers at the second service station. As will be seen, even the simplest version of the batch queue, the M/M ^[k,?K]/1?+?M queue, already gives rise to serious analytical complications for any batch size larger than 1. These complications are discussed in detail, and handled for K?=?2. In view of the fact that we aim to solve realistic optimization problems for blood screening procedures, these analytical complications force us to take recourse to either a numerical approach or approximations. We present a numerical solution for the queue length distribution in the M/M ^[k,?K]/S?+?M queue and then formulate and solve several optimization problems. The power-series algorithm, which is a numerical-analytic method, is also discussed.     

Approximation by light maps and parametric Lelek maps

The class of metrizable spaces M with the following approximation property is introduced and investigated: M∈AP(n,0) if for every ε>0 and a map g:In→M there exists a 0-dimensional map g^′:In→M which is ε-homotopic to g. It is shown that this class has very nice properties. For example, if Mi∈AP(ni,0), i=1,2, then M₁×M₂∈AP(n₁+n₂,0). Moreover, M∈AP(n,0) if and only if each point of M has a local base of neighborhoods U with U∈AP(n,0). Using the properties of AP(n,0)-spaces, we generalize some results of Levin and Kato-Matsuhashi concerning the existence of residual sets of n-dimensional Lelek maps.