Quasi-birth-and-death Markov processes with a tree structure and the MMAP[K]/PH[K]/N/LCFS non-preemptive queue

This paper studies a multi-server queueing system with multiple types of customers and last-come-first-served (LCFS) non-preemptive service discipline. First, a quasi-birth-and-death (QBD) Markov process with a tree structure is defined and some classical results of QBD Markov processes are generalized. Second, the MMAP[K]/PH[K]/N/LCFS non-preemptive queue is introduced. Using results of the QBD Markov process with a tree structure, explicit formulas are derived and an efficient algorithm is developed for computing the stationary distribution of queue strings. Numerical examples are presented to show the impact of the correlation and the pattern of the arrival process on the queueing process of each type of customer.     

Stationary Distributions of GI/M/c Queue with PH Type Vacations

We study a GI/M/c type queueing system with vacations in which all servers take vacations together when the system becomes empty. These servers keep taking synchronous vacations until they find waiting customers in the system at a vacation completion instant.The vacation time is a phase-type (PH) distributed random variable. Using embedded Markov chain modeling and the matrix geometric solution methods, we obtain explicit expressions for the stationary probability distributions of the queue length at arrivals and the waiting time. To compare the vacation model with the classical GI/M/c queue without vacations, we prove conditional stochastic decomposition properties for the queue length and the waiting time when all servers are busy. Our model is a generalization of several previous studies.     

Monotonicity properties in various retrial queues and their applications

We consider several multi-server retrial queueing models with exponential retrial times that arise in the literature of retrial queues. The effect of retrial rates on the behavior of the queue length process is investigated via sample path approach. We show that the number of customers in orbit and in the system as a whole are monotonically changed if the retrial rates in one system are bounded by the rates in second one. The monotonicity results are applied to show the convergence of generalized truncated systems that have been widely used for approximating the stationary queue length distribution in retrial queues. AMS subject classifications: Primary 60K25     

Factorization and Stochastic Decomposition Properties in Bulk Queues with Generalized Vacations

This paper considers a class of stationary batch-arrival, bulk-service queues with generalized vacations. The system consists of a single server and a waiting room of infinite capacity. Arrivals of customers follow a batch Markovian arrival process. The server is unavailable for occasional intervals of time called vacations, and when it is available, customers are served in groups of fixed size B. For this class of queues, we show that the vector probability generating function of the stationary queue length distribution is factored into two terms, one of which is the vector probability generating function of the conditional queue length distribution given that the server is on vacation. The special case of batch Poisson arrivals is carefully examined, and a new stochastic decomposition formula is derived for the stationary queue length distribution.AMS subject classification: 60K25, 90B22, 60K37     

M x /G/1 Queue with Multiple Vacations

Abstract

In this article, we study a queueing system M ^x /G/1 with multiple vacations. The probability generating function (P.G.F.) of stationary queue length and its expectation expression are deduced by using an embedded Markov chain of the queueing process. The P.G.F. of stationary system busy period and the probability of system in service state and vacation state also are obtained by the same method. At last we deduce the LST and mean of stationary waiting time in the service order FCFS and LCFS, respectively.     

Transient distributions of level dependent quasi-birth-death processes with linear transition rates

Many queueing systems such asM/M/s/K retrial queue with impatient customers, MAP/PH/1 retrial queue, retrial queue with two types of customers andMAP/M/∞ queue can be modeled by a level dependent quasi-birth-death (LDQBD) process with linear transition rates of the form λ_k = α+ βk at each levelk. The purpose of this paper is to propose an algorithm to find transient distributions for LDQBD processes with linear transition rates based on the adaptive uniformizaton technique introduced by van Moorsel and Sanders [11]. We apply the algorithm to some retrial queues and present numerical results.     

The M/G/1 Queue with Finite Workload Capacity

We consider the M/G/1 queueing system in which customers whose admission to the system would increase the workload beyond a prespecified finite capacity limit are not accepted. Various results on the distribution of the workload are derived; in particular, we give explicit formulas for its stationary distribution for M/M/1 and in the general case, under the preemptive LIFO discipline, for the joint stationary distribution of the number of customers in the system and their residual service times. Furthermore, the Laplace transform of the length of a busy period is determined. Finally, for M/D/1 the busy period distribution is derived in closed form.     

Optimal control of an M/M/2 queueing system with finite capacity operating under the triadic (0,Q,N,M) policy

operating under the triadic (0,Q, N,M) policy, where L is the maximum number of customers in the system. The number of working servers can be adjusted one at a time at arrival epochs or at service completion epochs depending on the number of customers in the system. Analytic closed-form solutions of the controllable M/M/2 queueing system with finite capacity operating under the triadic (0,Q, N,M) policy are derived. This is a generalization of the ordinary M/M/2 and the controllable M/M/1 queueing systems in the literature. The total expected cost function per unit time is developed to obtain the optimal operating (0,Q, N,M) policy at minimum cost.     

A finite capacity multi-queueing system with priorities and with repeated server vacations

In this paper, we study an M/G/1 multi-queueing system consisting ofM finite capacity queues, at which customers arrive according to independent Poisson processes. The customers require service times according to a queue-dependent general distribution. Each queue has a different priority. The queues are attended by a single server according to their priority and are served in a non-preemptive way. If there are no customers present, the server takes repeated vacations. The length of each vacation is a random variable with a general distribution function. We derive steady state formulas for the queue length distribution and the Laplace transform of the queueing time distribution for each queue.     

On the Transient Behavior of the M/M/1 and M/M/1/M Queues

This paper gives a transient analysis of the classic M/M/1 and M/M/1/K queues. Our results are asymptotic as time and queue length become simultaneously large for the infinite capacity queue, and as the system’s storage capacity K becomes large for the finite capacity queue. We give asymptotic expansions for p_n(t), which is the probability that the system contains n customers at time t. We treat several cases of initial conditions and different traffic intensities. The results are based on (i) asymptotic expansion of an exact integral representation for p_n(t) and (ii) applying the ray method to a scaled form of the forward Kolmogorov equation which describes the time evolution of p_n(t).     

Bottleneck analysis in multiclass closed queueing networks and its application

Asymptotic behavior of queues is studied for large closed multi-class queueing networks consisting of one infinite server station with K classes and M processor sharing (PS) stations. A simple numerical procedure is derived that allows us to identify all bottleneck PS stations. The bottleneck station is defined asymptotically as the station where the number of customers grows proportionally to the total number of customers in the network, as the latter increases simultaneously with service rates at PS stations. For the case when K=M=2, the set of network parameters is identified that corresponds to each of the three possible types of behavior in heavy traffic: both PS stations are bottlenecks, only one PS station is a bottleneck, and a group of two PS stations is a bottleneck while neither PS station forms a bottleneck by itself. In the last case both PS stations are equally loaded by each customer class and their individual queue lengths, normalized by the large parameter, converge to uniformly distributed random variables. These results are directly generalized for arbitrary K=M. Generalizations for K≠M are also indicated. The case of two bottlenecks is illustrated by its application to the problem of dimensioning bandwidth for different data sources in packet-switched communication networks. An engineering rule is provided for determining the link rates such that a service objective on a per-class throughput is satisfied. This revised version was published online in June 2006 with corrections to the Cover Date.     

Performance analysis approximation in a queueing system of type M/G/1

In this work, we apply the strong stability method to obtain an estimate for the proximity of the performance measures in the M/G/1 queueing system to the same performance measures in the M/M/1 system under the assumption that the distributions of the service time are close and the arrival flows coincide. In addition to the proof of the stability fact for the perturbed M/M/1 queueing system, we obtain the inequalities of the stability. These results give with precision the error, on the queue size stationary distribution, due to the approximation. For this, we elaborate from the obtained theoretical results, the STR-STAB algorithm which we execute for a determined queueing system: M/Coxian − 2/1. The accuracy of the approach is evaluated by comparison with simulation results.     

An MX/G/1 queueing system with a setup period and a vacation period

This paper deals with an M^X/G/1 queueing system with a vacation period which comprises an idle period and a random setup period. The server is turned off each time when the system becomes empty. At this point of time the idle period starts. As soon as a customer or a batch of customers arrive, the setup of the service facility begins which is needed before starting each busy period. In this paper we study the steady state behaviour of the queue size distributions at stationary (random) point of time and at departure point of time. One of our findings is that the departure point queue size distribution is the convolution of the distributions of three independent random variables. Also, we drive analytically explicit expressions for the system state probabilities and some performance measures of this queueing system. Finally, we derive the probability generating function of the additional queue size distribution due to the vacation period as the limiting behaviour of the M^X/M/1 type queueing system. This revised version was published online in June 2006 with corrections to the Cover Date.     

Bayesian prediction inM/M/1 queues

Simple queues with Poisson input and exponential service times are considered to illustrate how well-suited Bayesian methods are used to handle the common inferential aims that appear when dealing with queue problems. The emphasis will mainly be placed on prediction; in particular, we study the predictive distribution of usual measures of effectiveness in anM/M/1 queue system, such as the number of customers in the queue and in the system, the waiting time in the queue and in the system, the length of an idle period and the length of a busy period.     

A queue with a pair of instantaneous independent bernoulli feedback processes

In this paper we are concerned with several random processes that occur in M/G₂/l queue with instantaneous feedback in which the feedback decision process is a pair of independent Bernoulli processes. The stationary distribution of the output process has been obtained. Results for particular queues with feedback and without feedback are obtained. Some operating characteristics are derived for this queue. Some interesting results are obtained for departure processes. Optimum service rate is obtained. Numerical examples are provided to test the feasibility of the queueing model     

On the stationary distribution of queue lengths in a multi-class priority queueing system with customer transfers

This paper deals with a multi-class priority queueing system with customer transfers that occur only from lower priority queues to higher priority queues. Conditions for the queueing system to be stable/unstable are obtained. An auxiliary queueing system is introduced, for which an explicit product-form solution is found for the stationary distribution of queue lengths. Sample path relationships between the queue lengths in the original queueing system and the auxiliary queueing system are obtained, which lead to bounds on the stationary distribution of the queue lengths in the original queueing system. Using matrix-analytic methods, it is shown that the tail asymptotics of the stationary distribution is exact geometric, if the queue with the highest priority is overloaded.      

The Periodic BMAP/PH/c Queue

In queueing theory, most models are based on time-homogeneous arrival processes and service time distributions. However, in communication networks arrival rates and/or the service capacity usually vary periodically in time. In order to reflect this property accurately, one needs to examine periodic rather than homogeneous queues. In the present paper, the periodic BMAP/PH/c queue is analyzed. This queue has a periodic BMAP arrival process, which is defined in this paper, and phase-type service time distributions. As a Markovian queue, it can be analysed like an (inhomogeneous) Markov jump process. The transient distribution is derived by solving the Kolmogorov forward equations. Furthermore, a stability condition in terms of arrival and service rates is proven and for the case of stability, the asymptotic distribution is given explicitly. This turns out to be a periodic family of probability distributions. It is sketched how to analyze the periodic BMAP/M _t /c queue with periodically varying service rates by the same method.     

GI\M\n系統中大量服务的排队过程

<正> §1.引言 我們知道,描述一个排队过程,需要三个因素:輸入过程,排队紀律,及服务机构.所謂GI|M|n,就是指这样的一个排队过程,它的 i)輸入过程,各顾客到来的时間区間的长度t相互独立、相同分布.其分布記     

The Discrete-Time GI/Geo/1 Queue with Multiple Vacations

We study a discrete-time GI/Geo/1 queue with server vacations. In this queueing system, the server takes vacations when the system does not have any waiting customers at a service completion instant or a vacation completion instant. This type of discrete-time queueing model has potential applications in computer or telecommunication network systems. Using matrix-geometric method, we obtain the explicit expressions for the stationary distributions of queue length and waiting time and demonstrate the conditional stochastic decomposition property of the queue length and waiting time in this system.     

Limit non-stationary behavior of large closed queueing networks with bottlenecks

In this paper martingales methods are applied for analyzing limit non-stationary behavior of the queue length processes in closed Jackson queueing networks with a single class consisting of a large number of customers, a single infinite server queue, and a fixed number of single server queues with large state independent service rates. It is assumed that one of the single server nodes forms a bottleneck. For the non-bottleneck nodes we show that the queue length distribution at timet converges in generalized sense to the stationary distribution of the M/M/1 queue whose parameters explicitly depend ont. For the bottleneck node a diffusion approximation with reflection is proved in the moderate usage regime while fluid and Gaussian diffusion approximations are established for the heavy usage regime.