A Tandem Queue with Server Slow-Down and Blocking

Abstract

We consider two variants of a two-station tandem network with blocking. In both variants the first server ceases to work when the queue length at the second station hits a ‘blocking threshold.’ In addition, in variant 2 the first server decreases its service rate when the second queue exceeds a ‘slow-down threshold, ’ which is smaller than the blocking level. In both variants the arrival process is Poisson and the service times at both stations are exponentially distributed. Note, however, that in case of slow-downs, server 1 works at a high rate, a slow rate, or not at all, depending on whether the second queue is below or above the slow-down threshold or at the blocking threshold, respectively. For variant 1, i.e., only blocking, we concentrate on the geometric decay rate of the number of jobs in the first buffer and prove that for increasing blocking thresholds the sequence of decay rates decreases monotonically and at least geometrically fast to max{ρ₁, ρ₂}, where ρ _i is the load at server i. The methods used in the proof also allow us to clarify the asymptotic queue length distribution at the second station. Then we generalize the analysis to variant 2, i.e., slow-down and blocking, and establish analogous results.     

Markov-modulated infinite-server queues driven by a common background process

This paper studies a system with multiple infinite-server queues that are modulated by a common background process. If this background process, being modeled as a finite-state continuous-time Markov chain, is in state j, then the arrival rate into the i-th queue is λ_{i, j}, whereas the service times of customers present in this queue are exponentially distributed with mean μ^{? 1}_{i, j}; at each of the individual queues all customers present are served in parallel (thus reflecting their infinite-server nature).

Three types of results are presented: in the first place (i) we derive differential equations for the probability-generating functions corresponding to the distributions of the transient and stationary numbers of customers (jointly in all queues), then (ii) we set up recursions for the (joint) moments, and finally (iii) we establish a central limit theorem in the asymptotic regime in which the arrival rates as well as the transition rates of the background process are simultaneously growing large.     

DECOMPOSITIONS OF THE QUEUE LENGTH DISTRIBUTIONS IN THE MAP/G/1 QUEUE UNDER MULTIPLE AND SINGLE VACATIONS WITH N-POLICY

In this paper, we establish an explicit form of matrix decompositions for the queue length distributions of the MAP/G/1 queues under multiple and single vacations with N-policy. We show that the vector generating function Y (z) of the queue length at an arbitrary time and X (z) at departures are decomposed into Y (z) = p _idle (z)ζ _Y (z) and X (z) = p _idle (z)ζ _X (z) where p _idle (z) is the vector generating function of the queue length at an arbitrary epoch at which the server is not in service, and ζ _Y (z) and ζ _X (z) are unidentified matrix generating functions.     

An RG-Factorization Approach for a BMAP/M/1 Generalized Processor-Sharing Queue

ABSTRACT

In this paper, we study a BMAP/M/1 generalized processor-sharing queue. We propose an RG-factorization approach, which can be applied to a wider class of Markovian block-structured processor-sharing queues. We obtain the expressions for both the distribution of the stationary queue length and the Laplace transform of the sojourn time distribution. From these two expressions, we develop an algorithm to compute the mean and variance of the sojourn time approximately.     

Commuting Matrices in the Queue Length and Sojourn Time Analysis of MAP/MAP/1 Queues

Queues with Markovian arrival and service processes, i.e., MAP/MAP/1 queues, have been useful in the analysis of computer and communication systems and different representations for their stationary sojourn time and queue length distribution have been derived. More specifically, the class of MAP/MAP/1 queues lies at the intersection of the class of QBD queues and the class of semi-Markovian queues. While QBD queues have a matrix exponential representation for their queue length and sojourn time distribution of order N and N², respectively, where N is the size of the background continuous time Markov chain, the reverse is true for a semi-Markovian queue. As the class of MAP/MAP/1 queues lies at the intersection, both the queue length and sojourn time distribution of a MAP/MAP/1 queue has an order N matrix exponential representation. The aim of this article is to understand why the order N² distributions of the sojourn time of a QBD queue and the queue length of a semi-Markovian queue can be reduced to an order N distribution in the specific case of a MAP/MAP/1 queue. We show that the key observation exists in establishing the commutativity of some fundamental matrices involved in the analysis of the MAP/MAP/1 queue.     

A new class of bivariate lifetime distributions

This paper introduces a new class of bivariate lifetime distributions. Let {X_i}_{i ? 1} and {Y_i}_{i ? 1} be two independent sequences of independent and identically distributed positive valued random variables. Define T₁ = min?(X₁, …, X_M) and T₂ = min?(Y₁, …, Y_N), where (M, N) has a discrete bivariate phase-type distribution, independent of {X_i}_{i ? 1} and {Y_i}_{i ? 1}. The joint survival function of (T₁, T₂) is studied.     

Equilibrium strategies in a constant retrial queue with setup time and the N-policy

Abstract

In this article, customers’ strategic behavior and social optimation in a constant retrial queue with setup time and the N-policy are investigated. Customers who find the server isn’t idle either leave forever or enter an orbit. After a service, the server will seek a customer from the orbit at a constant rate. The server is closed whenever the system becomes empty, and is activated when the number of waitlisted customers reaches a threshold. We obtain the equilibrium arrival rates in different states. There exist both Follow-the-Crowd (FTC) and Avoid-the-Crowd (ATC) behaviors. Through the Particle Swarm Optimization (PSO) algorithm, we numerically obtain the optimal solution of the social welfare maximization problem. Finally, numerical examples are presented to illustrate the sensitivity of system performance measures.     

Optimum invariant tests for random manova models

Consider the canonical-form MANOVA setup with X: n × p = (+ E, X_i n_i × p, i = 1, 2, 3, M_i: n_i × p, i = 1, 2, n₁ + n₂ + n₃) p, where E is a normally distributed error matrix with mean zero and dispersion I_n (> 0 (positive definite). Assume (in contrast with the usual case) that M₁i is normal with mean zero and dispersion I_n1) and M₂2 is either fixed or random normal with mean zero and different dispersion matrix I_n2 (being unknown. It is also assumed that M₁ E, and M₂ (if random) are all independent. For testing H₀) = 0 versus H₁: (> 0, it is shown that when either n₂ = 0 or M₂ is fixed if n₂ > 0, the trace test of Pillai (1955) is uniformly most powerful invariant (UMPI) if min(n₁, p)= 1 and locally best invariant (LBI) if min(n₁ p) > 1 underthe action of the full linear group Gl (p). When p > 1, the LBI test is also derived under a somewhat smaller group G_T(p) of p × p lower triangular matrices with positive diagonal elements. However, such results do not hold if n₂ > 0 and M₂ is random. The null, nonnull, and optimality robustness of Pillai's trace test under Gl(p) for suitable deviations from normality is pointed out.     

Bayesian analysis of Er/M/1 and Er/M/c queues

Bayesian inference and prediction tasks for Er/M/1 and Er/M/c queues are undertaken. Equilibrium probabilities of the queue size and waiting time distributions are estimated using conditional Monte-Carlo simulation methods. We illustrate that some standard queueing measures do not exist when independent priors are used for the arrival and service rates of a G/M/1 queue.     

A Two‐Queue Polling Model with Regularly Varying Service and/or Switchover Times

Abstract

We consider the cyclic polling system with two queues. One queue is severed according to the exhaustive discipline, and the other queue is served according to the 1‐limited discipline. At least one of the service and/or switchover times has a regularly varying tail. We obtain the tail behavior of the waiting time distributions. When one of the service and/or switchover times has an infinite second moment, we derive the heavy‐traffic behavior of the waiting time distribution at the 1‐limited queue.     

Sojourn time in an M/M/1 processor sharing queue with permanent customers

We explicitly compute the sojourn time distribution of an arbitrary customer in an M/M/1 processor sharing (PS) queue with permanent customers. We notably exhibit the orthogonal structure associated with this queuing system and we show how sieved Pollaczek polynomials and their associated orthogonality measure can be used to obtain an explicit representation for the complementary cumulative distribution function of the sojourn time of a customer. This explicit formula subsequently allows us to compute the two first moments of this random variable and to study the asymptotic behavior of its distribution. The most salient result is that the decay rate depends on the load of the system and the number K of permanent customers. When the load is above a certain threshold depending on K, the decay rate is identical to that of a regular M/M/1 PS queue.     

Stationary distributions for a class of Markov-modulated tandem fluid queues

ABSTRACT

We consider a model consisting of two fluid queues driven by the same background continuous-time Markov chain, such that the rates of change of the fluid in the second queue depend on whether the first queue is empty or not: when the first queue is nonempty, the content of the second queue increases, and when the first queue is empty, the content of the second queue decreases.

We analyze the stationary distribution of this tandem model using operator-analytic methods. The various densities (or Laplace–Stieltjes transforms thereof) and probability masses involved in this stationary distribution are expressed in terms of the stationary distribution of some embedded process. To find the latter from the (known) transition kernel, we propose a numerical procedure based on discretization and truncation. For some examples we show the method works well, although its performance is clearly affected by the quality of these approximations, both in terms of accuracy and run time.     

Analysis of a batch arrival queue with vacation policy and exceptional service

ABSTRACT

We consider the distributions of operating characteristics of an M^[x]/G/1 queue under vacation policies, where the first customer of each busy period receives an exceptional service. When all the customers are served in the system exhaustively, the server deactivates and operates one of two vacation policies: (1) multiple vacation policy and (2) single vacation policy. We develop the performance measures for both systems. Finally, some numerical illustrations are also given. These two vacation models have potential applications in day-to-day life, such as post offices, banks, hospitals, etc.     

AN INFINITE-PHASE QUASI-BIRTH-AND-DEATH MODEL FOR THE NON-PREEMPTIVE PRIORITY M/PH/1 QUEUE

This paper considers a single server queue that handles arrivals from N classes of customers on a non-preemptive priority basis. Each of the N classes of customers features arrivals from a Poisson process at rate λ _i and class-dependent phase type service. To analyze the queue length and waiting time processes of this queue, we derive a matrix geometric solution for the stationary distribution of the underlying Markov chain. A defining characteristic of the paper is the fact that the number of distinct states represented within the sub-level is countably infinite, rather than finite as is usually assumed. Among the results we obtain in the two-priority case are tractable algorithms for the computation of both the joint distribution for the number of customers present and the marginal distribution of low-priority customers, and an explicit solution for the marginal distribution of the number of high-priority customers. This explicit solution can be expressed completely in terms of the arrival rates and parameters of the two service time distributions. These results are followed by algorithms for the stationary waiting time distributions for high- and low-priority customers. We then address the case of an arbitrary number of priority classes, which we solve by relating it to an equivalent three-priority queue. Numerical examples are also presented.     

Asymptotic Throughput in Discrete‐Time Cyclic Networks with Queue‐Length‐Dependent Service Rates

Abstract

For a discrete‐time closed cyclic network of single server queues whose service rates are non‐decreasing in the queue length, we compute the queue‐length distribution at each node in terms of throughputs of related networks. For the asymptotic analysis, we consider sequences of networks where the number of nodes grows to infinity, service rates are taken only from a fixed finite set of non‐decreasing sequences, the ratio of customers to nodes has a limit, and the proportion of nodes for each possible service‐rate sequence has a limit. Under these assumptions, the asymptotic throughput exists and is calculated explicitly. Furthermore, the asymptotic queue‐length distribution at any node can be obtained in terms of the asymptotic throughput. The asymptotic throughput, regarded as a function of the limiting customer‐to‐node ratio, is strictly increasing for ratios up to a threshold value (possibly infinite) and is constant thereafter. For ratios less than the threshold, the asymptotic queue‐length distribution at each node has finite moments of all orders. However, at or above the threshold, bottlenecks (nodes with asymptotically‐infinite mean queue length) do occur, and we completely characterize such nodes.     

Estimation of the Scale Parameter of the Selected Gamma Population Under the Entropy Loss Function

Let X ₁, X ₂,…, X _k be k (≥2) independent random variables from gamma populations Π₁, Π₂,…, Π _k with common known shape parameter α and unknown scale parameter θ _i , i = 1,2,…,k, respectively. Let X _(i) denotes the ith order statistics of X ₁,X ₂,…,X _k . Suppose the population corresponding to largest X _(k) (or the smallest X ₍₁₎) observation is selected. We consider the problem of estimating the scale parameter θ _M (or θ _J ) of the selected population under the entropy loss function. For k ≥ 2, we obtain the Unique Minimum Risk Unbiased (UMRU) estimator of θ _M (and θ _J ). For k = 2, we derive the class of all linear admissible estimators of the form cX ₍₂₎ (and cX ₍₁₎) and show that the UMRU estimator of θ _M is inadmissible. The results are extended to some subclass of exponential family.     

Performance measures of M/G/1 retrial queues with recurrent customers,breakdowns, and general delays

In this paper, an M/G/1 retrial system with two classes of customers: transit and recurrent customers is studied. After service completion, recurrent customers always return to the orbit and transit customers leave the system forever. The server is subject to breakdowns and delayed repairs. The customer whose service is interrupted stays in the service, waiting for delay and repair of the server. After repair this customer completes his service. The study of the system concerns the joint generating function of the server state and the queue length in steady state. Some performance measures of the system are then derived and some numerical results are presented to illustrate the effect of the system parameters on the developed performance measures.     

GEOMETRIC DECAY OF THE STEADY-STATE PROBABILITIES IN A QUASI-BIRTH-AND-DEATH PROCESS WITH A COUNTABLE NUMBER OF PHASES

A sufficient condition is proved for geometric decay of the steady-state probabilities in a quasi-birth-and-death process having a countable number of phases in each level. If there is a positive number η and positive vectors x = (x _i) and y = (y _j ) satisfying some equations and inequalities, the steady-state probability π _mi decays geometrically with rate η in the sense π _mi ～ cη ^m x _i as m → ∞. As an example, the result is applied to a two-queue system with shorter queue discipline.     

Using a Truncated C p Statistic for Variable Selection in Multiple Linear Regression

In multiple linear regression analysis each lower-dimensional subspace L of a known linear subspace M of ? ⁿ corresponds to a non empty subset of the columns of the regressor matrix. For a fixed subspace L, the C _p statistic is an unbiased estimator of the mean square error if the projection of the response vector onto L is used to estimate the expected response. In this article, we consider two truncated versions of the C _p statistic that can also be used to estimate this mean square error. The C _p statistic and its truncated versions are compared in two example data sets, illustrating that use of the truncated versions may result in models different from those selected by standard C _p .