Approximation of M/M/s/K retrial queue with nonpersistent customers

We consider the M/M/s/K retrial queues in which a customer who is blocked to enter the service facility may leave the system with a probability that depends on the number of attempts of the customer to enter the service facility. Approximation formulae for the distributions of the number of customers in service facility, waiting time in the system and the number of retrials made by a customer during its waiting time are derived. Approximation results are compared with the simulation.     

Using the M/G/1 queue under processor sharing for exact simulation of queues

In Sigman (J. Appl. Probab. 48A:209–216, 2011b), a first exact simulation algorithm was presented for the stationary distribution of customer delay for FIFO M/G/c queues in which ρ=λ/μ<1 (super stable case). The key idea involves dominated coupling from the past while using the M/G/1 queue under the processor sharing (PS) discipline as a sample-path upper bound, taking advantage of its time-reversibility properties so as to be able to simulate it backwards in time. Here, we expand upon this method and give several examples of other queueing models for which this method can be used to exactly simulate from their stationary distributions. Examples include sojourn times for single-server queues under various service disciplines, tandem queues, and multi-class networks with general routing.     

Steady state analysis of an M/G/1 queue with linear retrial policy and two phase service under Bernoulli vacation schedule

We consider a single server queueing system with two phases of heterogeneous service and Bernoulli vacation schedule which operate under the so called linear retrial policy. This model extends both the classical M/G/1 retrial queue with linear retrial policy as well as the M/G/1 queue with two phases of service and Bernoulli vacation model. We carry out an extensive analysis of the model.     

An M/G/1 queue with two phases of service subject to the server breakdown and delayed repair

This paper deals with the steady-state behaviour of an M/G/1 queue with an additional second phase of optional service subject to breakdowns occurring randomly at any instant while serving the customers and delayed repair. This model generalizes both the classical M/G/1 queue subject to random breakdown and delayed repair as well as M/G/1 queue with second optional service and server breakdowns. For this model, we first derive the joint distributions of state of the server and queue size, which is one of chief objectives of the paper. Secondly, we derive the probability generating function of the stationary queue size distribution at a departure epoch as a classical generalization of Pollaczek–Khinchin formula. Next, we derive Laplace Stieltjes transform of busy period distribution and waiting time distribution. Finally, we obtain some important performance measures and reliability indices of this model.     

Increasing convex ordering of queue length in bulk queues

This paper considers single-server bulk queues M^(X)/G^(Y)/1 and G^(X)/M^(Y)/1. In the former queue, service times and service capacity are dependent, while in the latter queue, inter-arriving times and arriving group size are dependent. We show that stronger dependence between those leads to shorter queue lengths in the increasing convex ordering sense.     

A duality relation for busy cycles inGI/G/1 queues

Using a generalization of the classical ballot theorem, Niu and Cooper [7] established a duality relation between the joint distribution of several variables associated with the busy cycle inM/G/1 (with a modified first service) and the corresponding joint distribution of several related variables in its dualGI/M/1. In this note, we generalize this duality relation toGI/G/1 queues with modified first services; this clarifies the original result, and shows that the generalized ballot theorem is superfluous for the duality relation.     

Queues with Workload-Dependent Arrival and Service Rates

We consider two types of queues with workload-dependent arrival rate and service speed. Our study is motivated by queueing scenarios where the arrival rate and/or speed of the server depends on the amount of work present, like production systems and the Internet. First, in the M/G/1 case, we compare the steady-state distribution of the workload (both at arbitrary epochs and at arrival instants) in two models, in which the ratio of arrival rate and service speed is equal. Applying level crossing arguments, we show that the steady-state distributions are proportional. Second, we consider a G/G/1-type queue with workload-dependent interarrival times and service speed. Using a stochastic mean-value approach, several well-known relations for the workload at various epochs in the ordinary G/G/1 queue are generalized.     

Heavy-traffic limits for many-server queues with service interruptions

We establish many-server heavy-traffic limits for G/M/n+M queueing models, allowing customer abandonment (the +M), subject to exogenous regenerative service interruptions. With unscaled service interruption times, we obtain a FWLLN for the queue-length process, where the limit is an ordinary differential equation in a two-state random environment. With asymptotically negligible service interruptions, we obtain a FCLT for the queue-length process, where the limit is characterized as the pathwise unique solution to a stochastic integral equation with jumps. When the arrivals are renewal and the interruption cycle time is exponential, the limit is a Markov process, being a jump-diffusion process in the QED regime and an O–U process driven by a Levy process in the ED regime (and for infinite-server queues). A stochastic-decomposition property of the steady-state distribution of the limit process in the ED regime (and for infinite-server queues) is obtained.     

Sojourn times in a processor sharing queue with multiple vacations

We study an M/G/1 processor sharing queue with multiple vacations. The server only takes a vacation when the system has become empty. If he finds the system still empty upon return, he takes another vacation, and so on. Successive vacations are identically distributed, with a general distribution. When the service requirements are exponentially distributed we determine the sojourn time distribution of an arbitrary customer. We also show how the same approach can be used to determine the sojourn time distribution in an M/M/1-PS queue of a polling model, under the following constraints: the service discipline at that queue is exhaustive service, the service discipline at each of the other queues satisfies a so-called branching property, and the arrival processes at the various queues are independent Poisson processes. For a general service requirement distribution we investigate both the vacation queue and the polling model, restricting ourselves to the mean sojourn time.     

M/M/c Retrial Queue with Multiclass of Customers

We consider the M/M/c retrial queues with multiclass of customers. We show that the stationary joint distribution for the number of customers in service facility and orbit converges to those of the ordinary M/M/c with discriminatory random order service (DROS) policy as retrial rate tends to infinity. Approximation formulae for the distributions of the number of customers in service facility, the mean number of customers in orbit and the sojourn time distribution of a customer are presented. The approximations are compared with exact and simulation results.     

Approximation of M/M/c retrial queue with PH-retrial times

We consider the M/M/c retrial queues with PH-retrial times. Approximation formulae for the distribution of the number of customers in service facility and the mean number of customers in orbit are presented. Some numerical results are presented.     

The Maximum Queue Length for Heavy-Tailed Service Times in the M/G/1 FB Queue

This paper treats the maximum queue length M, in terms of the number of customers present, in a busy cycle in the M/G/1 queue. The distribution of M depends both on the service time distribution and on the service discipline. Assume that the service times have a logconvex density and the discipline is Foreground Background (FB). The FB service discipline gives service to the customer(s) that have received the least amount of service so far. It is shown that under these assumptions the tail of M is bounded by an exponential tail. This bound is used to calculate the time to overflow of a buffer, both in stable and unstable queues.     

The interior of the Šilov boundary of M(G) is trivial

Let G be a non-discrete locally compact abelian group, and let M(G) be the convolution algebra of regular bounded Borel measures on G. Let Γ denote the dual group of G. Then the interior of the ?ilov boundary of M(G) is exactly Γ. The proof uses generalized Riesz products for the compact metrizable case and standard liftings from that case.     

On the fluid limit of the M/G/∞ queue

The paper deals with the fluid limits of some generalized M/G/∞ queues under heavy-traffic scaling. The target application is the modeling of Internet traffic at the flow level. Our paper first gives a simplified approach in the case of Poisson arrivals. Expressing the state process as a functional of some Poisson point process, an elementary proof for limit theorems based on martingales techniques and weak convergence results is given. The paper illustrates in the special Poisson arrivals case the classical heavy-traffic limit theorems for the G/G/∞ queue developed earlier by Borovkov and by Iglehart, and later by Krichagina and Puhalskii. In addition, asymptotics for the covariance of the limit Gaussian processes are obtained for some classes of service time distributions, which are useful to derive in practice the key parameters of these distributions.     

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.     

Diagonalizing matrices over C(X)

A complete characterization of those compact Hausdorff spaces is given such that for every n, each normal element in the algebra C(X)?M_n of continuous functions from X to $\text{M}$_n can be continuously diagonalized. The conditions are that X be a sub-Stonean space with dim X ? 2 and carries no nontrivial G-bundles over any closed subset, for G a symmetric group or the circle group. In particular, diagonalization is assured on every totally disconnected sub-Stonean space, but also on connected spaces of the form β(Y)/Y, where Y is a simply-connected (noncompact) graph.     

Comparison conjectures about the M/G/s queue

We conjecture that the equilibrium waiting-time distribution in an M/G/s queue increases stochastically when the service-time distribution becomes more variable. We discuss evidence in support of this conjecture and others based partly on light-traffic and heavy-traffic limits. We also establish an insensitivity property for the case of many servers in light traffic.     

On the complete monotonicity of the waiting time density in some GI/G/k systems

In this note the complete monotonicity of the waiting time density in GI/G/k queues is proved under the assumption that the service time density is completely monotone. This is an extension of Keilson's [3] result for M/G/1 queues. We also provide another proof of the result that complete monotonicity is preserved by geometric compounding.     

A MAP/G/1 Queue with Negative Customers

In this paper, we consider a MAP/G/1 queue with MAP arrivals of negative customers, where there are two types of service times and two classes of removal rules: the RCA and RCH, as introduced in section 2. We provide an approach for analyzing the system. This approach is based on the classical supplementary variable method, combined with the matrix-analytic method and the censoring technique. By using this approach, we are able to relate the boundary conditions of the system of differential equations to a Markov chain of GI/G/1 type or a Markov renewal process of GI/G/1 type. This leads to a solution of the boundary equations, which is crucial for solving the system of differential equations. We also provide expressions for the distributions of stationary queue length and virtual sojourn time, and the Laplace transform of the busy period. Moreover, we provide an analysis for the asymptotics of the stationary queue length of the MAP/G/1 queues with and without negative customers.