On bounds for bulk arrival queues

This paper gives a simple and effective approach pf deriving bounds for bulk arrival queues by making use of the bounds for single arrival queues. With this approach, upper bounds of mean actual/virtual waiting times and mean queue length at random epochs can be derived for the bulk arrival queues GI^X/G/1 and GI^X/G/c (lower bounds can be derived in a similar way). The merit of this approach is shown by comparing the bounds obtained with some existing results in the literature.     

A Polynomial Factorization Approach for the Discrete Time GIX/>G/1/K Queue

This paper proposes a polynomial factorization approach for queue length distribution of discrete time GI ^X /G/1 and GI _X /G/1/K queues. They are analyzed by using a two-component state model at the arrival and departure instants of customers. The equilibrium state-transition equations of state probabilities are solved by a polynomial factorization method. Finally, the queue length distributions are then obtained as linear combinations of geometric series, whose parameters are evaluated from roots of a characteristic polynomial.     

Analysis of the GI/Geo/1 queue with N-policy

We consider a discrete-time single server N  -policy GI/Geo/1$\mathit{GI}/\mathit{Geo}/1$ queueing system. The server stops servicing whenever the system becomes empty, and resumes its service as soon as the number of waiting customers in the queue reaches N. Using an embedded Markov chain and a trial solution approach, the stationary queue length distribution at arrival epochs is obtained. Furthermore, we obtain the stationary queue length distribution at arbitrary epochs by using the preceding result and a semi-Markov process. The sojourn time distribution is also presented.     

On the Stationary Distribution of the GI X /M Y /1 Queueing System

For the GI ^X /M/1 queue, it has been recently proved that there exist geometric distributions that are stochastic lower and upper bounds for the stationary distribution of the embedded Markov chain at arrival epochs. In this note we observe that this is also true for the GI ^X /M ^Y /1 queue. Moreover, we prove that the stationary distribution of its embedded Markov chain is asymptotically geometric. It is noteworthy that the asymptotic geometric parameter is the same as the geometric parameter of the upper bound. This fact justifies previous numerical findings about the quality of the bounds.     

Queue-length and waiting-time distributions of discrete-time GI X/Geom/ 1 queueing systems with early and late arrivals

In this paper, we give a unified approach to solving discrete-time GI ^X/Geom/ 1 queues with batch arrivals. The analysis has been carried out for early- and late-arrival systems using the supplementary variable technique. The distributions of numbers in systems at prearrival epochs have been expressed in terms of roots of associated characteristic equations. Furthermore, distributions at arbitrary as well as outside observer's observation epochs have been obtained using the relation derived in this paper. We also present delay analyses for both the systems. Numerical results are presented for various interarrival-time and batch-size distributions. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

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.     

A simple method for computing state probabilities of theM/G/1 andGI/M/1 finite waiting space queues

This paper presents a simple method for computing steady state probabilities at arbitrary and departure epochs of theM/G/1/K queue. The method is recursive and works efficiently for all service time distributions. The only input required for exact evaluation of state probabilities is the Laplace transform of the probability density function of service time. Results for theGI/M/1/K –1 queue have also been obtained from those ofM/G/1/K queue.     

Equivalences of Batch-Service Queues and Multi-Server Queues and Their Complete Simple Solutions in Terms of Roots

Abstract

In this article, we first present a unified discussion of several equivalence relationships among (as well as between) batch-service queues and multi-server queues, in terms of the stationary queue-length and waiting-time distributions. Then, we present a complete and simple solution for the queue-length and waiting-time distributions of the discrete-time multi-server deterministic-service Geo/D/b queue, in terms of roots of the so-called characteristic equation. This solution also represents the solutions for the other equivalent queues, as a result of the equivalence relationships. To aid in the applications of these results, sample numerical results are presented at the end.     

A unified algorithm for computing the stationary queue length distributions inM(k)/G/1/N and GI/M(k)/1/N queues

An iterative algorithm is developed for computing numerically the stationary queue length distributions in M/G/1/N queues with arbitrary state-dependent arrivals, or simply M(k)/G/1/N queues. The only input requirement is the Laplace-Stieltjes transform of the service time distribution.In addition, the algorithm can also be used to obtain the stationary queue length distributions in GI/M/1/N queues with state-dependent services, orGI/M(k)/1/N, after establishing a relationship between the stationary queue length distributions inGI/M(k)/1/N and M(k)/G/1/N+1 queues.Finally, we elaborate on some of the well studied special cases, such asM/G/1/N queues,M/G/1/N queues with distinct arrival rates (which includes the machine interference problems), andGI/M/C/N queues. The discussions lead to a simplified algorithm for each of the three cases.     

Approximations for the <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">N</Emphasis>+<Emphasis Type="Italic">GI</Emphasis> type call center

In this paper, we propose approximations to compute the steady-state performance measures of the M/GI/N+GI queue receiving Poisson arrivals with N identical servers, and general service and abandonment-time distributions. The approximations are based on scaling a single server M/GI/1+GI queue. For problems involving deterministic and exponential abandon times distributions, we suggest a practical way to compute the waiting time distributions and their moments using the Laplace transform of the workload density function. Our first contribution is numerically computing the workload density function in the M/GI/1+GI queue when the abandon times follow general distributions different from the deterministic and exponential distributions. Then we compute the waiting time distributions and their moments. Next, we scale-up the M/GI/1+GI queue giving rise to our approximations to capture the behavior of the multi-server system. We conduct extensive numerical experiments to test the speed and performance of the approximations, which prove the accuracy of their predictions.      

Performance analysis of a discrete-time Geo/G/1 queue with randomized vacations and at most J vacations

This paper presents the analysis of a discrete-time Geo/G/1$\mathit{Geo}/G/1$ queue with randomized vacations. Using the probability decomposition theory and renewal process, two variants on this model, namely the late arrival system with delayed access (LAS-DA) and early arrival system (EAS), have been examined. For both the cases, recursive solution for queue length distributions at arbitrary, just before a potential arrival, pre-arrival, immediately after potential departure, and outside observer’s observation epochs are obtained. Further, various performance measures such as potential blocking probability, turned-on period, turned-off period, vacation period, expected length of the turned-on circle period, average queue length and sojourn time, etc. have been presented. It is hoped that the results obtained in this paper may provide useful information to designers of telecommunication systems, practitioners, and others.     

Dynamic server assignment in a two-queue model

We consider a polling model of two M/G/1 queues, served by a single server. The service policy for this polling model is of threshold type. Service at queue 1 is exhaustive. Service at queue 2 is exhaustive unless the size of queue 1 reaches some level T during a service at queue 2; in the latter case the server switches to queue 1 at the end of that service. Both zero- and nonzero switchover times are considered. We derive exact expressions for the joint queue length distribution at customer departure epochs, and for the steady-state queue-length and sojourn time distributions. In addition, we supply a simple and very accurate approximation for the mean queue lengths, which is suitable for optimization purposes.     

Discrete-Time Geo X /G/1 Queue with Preemptive Repeat Different Priority

This paper considers a discrete-time Geo ^X /G/1 queue accepting two classes of messages with preemptive repeat different priority. Service times of messages of each priority class are i.i.d. according to a general discrete distribution function that may differ between two classes. The completion time and the stability condition for our system are investigated. By using the supplementary variable method and the generating function technique, we derive the joint system contents distributions at various observation instants and also compute the probability distribution for the unfinished work.     

Exact Convergence Rate for the Distributions of GI/M/c/K Queue as K Tends to Infinity

We obtain the exact convergence rate of the stationary distribution ^(K) of the embedded Markov chain in GI/M/c/K queue to the stationary distribution of the embedded Markov chain in GI/M/c queue as K. Similar result for the time-stationary distributions of queue size is also included. These generalize Choi and Kim's results of the case c=1 by nontrivial ways. Our results also strengthen the Simonot's results [5].     

Performance Analysis of a Finite-Buffer Bulk-Arrival and Bulk-Service Queue with Variable Server Capacity

Abstract

In this paper, we consider a finite-buffer bulk-arrival and bulk-service queue with variable server capacity: M ^X /G ^Y /1/K + B. The main purpose of this paper is to discuss the analytic and computational aspects of this system. We first derive steady-state departure-epoch probabilities based on the embedded Markov chain method. Next, we demonstrate two numerically stable relationships for the steady-state probabilities of the queue lengths at three different epochs: departure, random, and arrival. Finally, based on these relationships, we present various useful performance measures of interest such as moments of the number of customers in the queue at three different epochs, the loss probability, and the probability that server is busy. Numerical results are presented for a deterministic service-time distribution – a case that has gained importance in recent years.     

Optimal (r,N)‐policy for discrete‐time Geo ∕ G ∕ 1 queue with different input rate and setup time

This paper presents a queue‐length analysis of Geo ∕ G ∕ 1 queue with ( r , N )‐policy and different input rate. Using a different method, the recursive expressions of queue‐length distribution at different epochs are obtained. Furthermore, some performance measures are also investigated. Finally, the Tabu search algorithm is used to search the joint optimum value of ( r , N ), which minimizes the state‐dependent operating cost. Copyright © 2014 John Wiley & Sons, Ltd.     

Discrete-time queue with unreliable server and multiple adaptive delayed vacations

In this paper we consider a discrete-time Geo^X/G/1 queue with unreliable server and multiple adaptive delayed vacations policy in which the vacation time, service time, repair time and the delayed time all follow arbitrary discrete distribution. By using a concise decomposition method, the transient and steady-state distributions of the queue length are studied, and the stochastic decomposition property of steady-state queue length has been proved. Several common vacation policies are special cases of the vacation policy presented in this study. The relationship between the generating functions of steady-state queue length at departure epoch and arbitrary epoch is obtained. Finally, we give some numerical examples to illustrate the effect of the parameters on several performance characteristics.     

Diffusion Approximations for Queues with Markovian Bases

Consider a base family of state-dependent queues whose queue-length process can be formulated by a continuous-time Markov process. In this paper, we develop a piecewise-constant diffusion model for an enlarged family of queues, each of whose members has arrival and service distributions generalized from those of the associated queue in the base. The enlarged family covers many standard queueing systems with finite waiting spaces, finite sources and so on. We provide a unifying explicit expression for the steady-state distribution, which is consistent with the exact result when the arrival and service distributions are those of the base. The model is an extension as well as a refinement of the M/M/s-consistent diffusion model for the GI/G/s queue developed by Kimura [13] where the base was a birth-and-death process. As a typical base, we still focus on birth-and-death processes, but we also consider a class of continuous-time Markov processes with lower-triangular infinitesimal generators.     

Heavy Traffic Analysis of Two Coupled Processors

We consider two parallel queues. When both are non-empty, they behave as two independent M/M/1 queues. If one queue is empty the server in the other works at a different rate. We consider the heavy traffic limit, where the system is close to instability. We derive and analyze the heavy traffic diffusion approximation for this model. In particular, we obtain simple integral representations for the joint steady state density of the (scaled) queue lengths. Asymptotic and numerical properties of the solution are studied.