The <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/1+<Emphasis Type="Italic">G</Emphasis> queue revisited

We consider an M/G/1 queue with the following form of customer impatience: an arriving customer balks or reneges when its virtual waiting time, i.e., the amount of work seen upon arrival, is larger than a certain random patience time. We consider the number of customers in the system, the maximum workload during a busy period, and the length of a busy period. We also briefly treat the analogous model in which any customer enters the system and leaves at the end of his patience time or at the end of his virtual sojourn time, whichever occurs first.     

Sojourn Times in the <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">PH</Emphasis>/1 Processor Sharing Queue

We give in this paper an algorithm to compute the sojourn time distribution in the processor sharing, single server queue with Poisson arrivals and phase type distributed service times. In a first step, we establish the differential system governing the conditional sojourn times probability distributions in this queue, given the number of customers in the different phases of the PH distribution at the arrival instant of a customer. This differential system is then solved by using a uniformization procedure and an exponential of matrix. The proposed algorithm precisely consists of computing this exponential with a controlled accuracy. This algorithm is then used in practical cases to investigate the impact of the variability of service times on sojourn times and the validity of the so-called reduced service rate (RSR) approximation, when service times in the different phases are highly dissymmetrical. For two-stage PH distributions, we give conjectures on the limiting behavior in terms of an M/M/1 PS queue and provide numerical illustrative examples.This revised version was published online in June 2005 with corrected coverdate     

Lost customers in <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/1/1 loss system

In this paper, we consider lost customers in the M/M/1/1 Erlang loss system. Here we present an explicit form of the probability that the M/M/1/1 system does not lose any customer in the time interval [0, t) and an iterative procedure to determine the distribution of the total number of losses in [0, t). All these probabilities solve the same second-order differential equation which was used to evaluate the corresponding generating probability function. Finally, the connection between the Erlang’s loss rate and the evaluated probabilities is showed.     

Rate of convergence to stationarity of the system <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">N</Emphasis>/<Emphasis Type="Italic">N</Emphasis>+<Emphasis Type="Italic">R</Emphasis>

We consider the M/M/N/N+R service system, characterized by N servers, R waiting positions, Poisson arrivals and exponential service times. We discuss representations and bounds for the rate of convergence to stationarity of the number of customers in the system, and study its behaviour as a function of R, N and the arrival rate λ, allowing λ to be a function of N.     

<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.     

Further Results for the Queueing System <Emphasis Type="Italic">M</Emphasis><Superscript><Emphasis Type="Italic">x</Emphasis></Superscript>/<Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">c</Emphasis>

For the multi-channel bulk-arrival queue, M ^x /M/c, Abol'nikov and Kabak independently obtained steady state results. In this paper the results of these authors are extended, corrected and simplified. A number of measures of efficiency are calculated for three cases where the arrival group size has: (i) a constant value, (ii) a geometric distribution, or (iii) a positive Poisson distribution. The paper also shows how to calculate fractiles for both the queue length and the waiting time distribution. Examples of extensive numerical results for certain measures of efficiency are presented in tabular and chart form.     

The queue length in an <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/1 batch arrival retrial queue

An M/G/1 retrial queue with batch arrivals is studied. The queue length K _μ is decomposed into the sum of two independent random variables. One corresponds to the queue length K _∞ of a standard M/G/1 batch arrival queue, and another is compound-Poisson distributed. In the case of the distribution of the batch size being light-tailed, the tail asymptotics of K _μ are investigated through the relation between K _∞ and its service times.     

Scheduling policies in the <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/1 make-to-stock queue

In this paper, we analyse a production/inventory system modelled as an M/G/1 make-to-stock queue producing different products requiring different and general production times. We study different scheduling policies including the static first-come-first-served, preemptive and non-preemptive priority disciplines. For each static policy, we exploit the distributional Little's law to obtain the steady-state distribution of the number of customers in the system and then find the optimal inventory control policy and the cost. We additionally provide the conditions under which it is optimal to produce a product according to a make-to-order policy. We further extend the application area of a well-known dynamic scheduling heuristic, Myopic(T), for systems with non-exponential service times by permitting preemption. We compare the performance of the preemptive-Myopic(T) heuristic alongside that of the static preemptive-bμ rule against the optimal solution. The numerical study we have conducted demonstrates that the preemptive-Myopic(T) policy is superior between the two and yields costs very close to the optimal.     

Detailing Losses in the <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/1/1 Transient Loss System

This paper is aimed at investigating the transient losses in the M/M/1/1 Erlang loss system. We evaluate the explicit form of the probability distribution of the number of losses in the time interval [0, t) and provide two alternative representations: one based on the iterated derivatives of hyperbolic sinus and cosine and the other on the spherical modified Bessel function of the second kind. The mathematical structures of the transient loss rate and of the transient probability of losing all customers are described and several analytical properties are derived.     

The <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/1 retrial queue with retrials due to server failures

Sherman and Kharoufeh (Oper. Res. Lett. 34:697–705, [2006]) considered an M/M/1 type queueing system with unreliable server and retrials. In this model it is assumed that if the server fails during service of a customer, the customer leaves the server, joins a retrial group and in random intervals repeats attempts to get service. We suggest an alternative method for analysis of the Markov process, which describes the functioning of the system, and find the joint distribution of the server state, the number of customers in the queue and the number of customers in the retrial group in steady state.      

Packet loss characteristics for <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/1/<Emphasis Type="Italic">N</Emphasis> queueing systems

In this contribution we investigate higher-order loss characteristics for M/G/1/N queueing systems. We focus on the lengths of the loss and non-loss periods as well as on the number of arrivals during these periods. For the analysis, we extend the Markovian state of the queueing system with the time and number of admitted arrivals since the instant where the last loss occurred. By combining transform and matrix techniques, expressions for the various moments of these loss characteristics are found. The approach also yields expressions for the loss probability and the conditional loss probability. Some numerical examples then illustrate our results.     

The Recursive Solution for Geom/G/1（E,SV） queue with Feedback and Single Server Vacation

Using recursive method,this paper studies the queue size properties at any epoch n + in Geom/G/1(E,SV) queueing model with feedback under LASDA (late arrival system with delayed access) setup.Some new results about the recursive expressions of queue size distribution at different epoch (n+,n,n-) are obtained.Furthermore the important relations between stationary queue size distribution at different epochs are discovered.The results are different from the relations given in M/G/1 queueing system.The model discussed in this paper can be widely applied in many kinds of communications and computer network.     

Approximation in the <Emphasis Type="BoldItalic">M</Emphasis><Subscript>2</Subscript>/<Emphasis Type="BoldItalic">G</Emphasis><Subscript>2</Subscript>/1 Queue with Preemptive Priority

The main purpose of this paper is to use the strong stability method to approximate the characteristics of the M ₂/G ₂/1 queue with preemptive priority by those of the classical M/G/1 queue. The latter is simpler and more exploitable in practice. After perturbing the arrival intensity of the priority requests, we derive the stability conditions and next obtain the stability inequalities with an exact computation of constants. From those theoretical results, we elaborate an algorithm allowing us to verify the approximation conditions and to provide the made numerical error. In order to have an idea about the efficiency of this approach, we consider a concrete example whose results are compared with those obtained by simulation.     

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.      

Two new heuristics for the <Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/<Emphasis Type="Italic">n</Emphasis>/0 queueing loss system with examples based on the two-phase Coxian distribution

In this paper, we introduce a new heuristic approach for the numerical analysis of queueing systems. In particular, we study the general, multi-server queueing loss system, the GI/G/n/0 queue, with an emphasis on the calculation of steady-state loss probabilities. Two new heuristics are developed, called the GM Heuristic and the MG Heuristic, both of which make use of an exact analysis of the corresponding single-server GI/G/1/0 queue. The GM Heuristic also uses an exact analysis of the GI/M/n/0 queue, while the MG Heuristic uses an exact analysis of the M/G/n/0 queue. Experimental results are based on the use of two-phase Coxian distributions for both the inter-arrival time and the service time; these include an error analysis for each heuristic and the derivation of experimental probability bounds for the loss probability. For the class of problems studied, it is concluded that there are likely to be many situations where the accuracy of the GM Heuristic is adequate for practical purposes. Methods are also developed for combining the GM and MG Heuristics. In some cases, this leads to approximations that are significantly more accurate than those obtained by the individual heuristics.     

Graded central polynomials for the algebra <Emphasis Type="Italic">M</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>(<Emphasis Type="Italic">K</Emphasis>)

Let M _n (K) be the algebra of all n × n matrices over an infinite field K. This algebra has a natural ℤ _n -grading and a natural ℤ-grading. Finite bases for its ℤ _n -graded identities and for its ℤ-graded identities are known. In this paper we describe finite generating sets for the ℤ _n -graded and for the ℤ-graded central polynomials for M _n (K) Partially supported by CNPq 620025/2006-9     

The <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/∞ queue in a random environment

We consider the M/M/∞ queueing system with arrival and service rate depending on the state of an auxiliary semi-Markov process (which can be viewed as an external environment) and find the mean number of customers in the system in steady state. In a particular case when the external environment can be only in two states we find the distribution of the number of customers in the system.      

<Emphasis Type="Italic">M</Emphasis>-slenderness

Analogues of Nunke’s theorem are proved which characterize variants of slenderness. For a bounded monotone subgroup M of ? ^ω , a torsion-free reduced abelian group G is M-slender if, and only if, there is no monomorphism from M into G. It is consistent relative to ordinary set theory (ZFC) that if M ≠ ? ^ω is an unbounded monotone subgroup of ? ^ω , then a torsion-free reduced abelian group G is M-slender if, and only if, there is no monomorphism from M into G.     

An <Emphasis Type="Italic">M</Emphasis><Superscript>[<Emphasis Type="Italic">X</Emphasis>]</Superscript>/<Emphasis Type="Italic">G</Emphasis>/1 retrial queue with server breakdowns and constant rate of repeated attempts

We consider an M ^[X]/G/1 retrial queue subject to breakdowns where the retrial time is exponential and independent of the number of customers applying for service. If a coming batch of customers finds the server idle, one of the arriving customers begins his service immediately and the rest joins a retrial group (called orbit) to repeat his request later; otherwise, if the server is busy or down, all customers of the coming batch enter the orbit. It is assumed that the server has a constant failure rate and arbitrary repair time distribution. We study the ergodicity of the embedded Markov chain, its stationary distribution and the joint distribution of the server state and the orbit size in steady-state. The orbit and system size distributions are obtained as well as some performance measures of the system. The stochastic decomposition property and the asymptotic behavior under high rate of retrials are discussed. We also analyse some reliability problems, the k-busy period and the ordinary busy period of our retrial queue. Besides, we give a recursive scheme to compute the distribution of the number of served customers during the k-busy period and the ordinary busy period. The effects of several parameters on the system are analysed numerically. I. Atencia’s and Moreno’s research is supported by the MEC through the project MTM2005-01248.     

On sojourn times in <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">GI</Emphasis> systems under state-dependent processor sharing

We consider a system with Poisson arrivals and i.i.d. service times. The requests are served according to the state-dependent processor-sharing discipline, where each request receives a service capacity which depends on the actual number of requests in the system. The linear systems of PDEs describing the residual and attained sojourn times coincide for this system, which provides time reversibility including sojourn times for this system, and their minimal non-negative solution gives the LST of the sojourn time V(τ) of a request with required service time τ. For the case that the service time distribution is exponential in a neighborhood of zero, we derive a linear system of ODEs, whose minimal non-negative solution gives the LST of V(τ), and which yields linear systems of ODEs for the moments of V(τ) in the considered neighborhood of zero. Numerical results are presented for the variance of V(τ). In the case of an M/GI/2-PS system, the LST of V(τ) is given in terms of the solution of a convolution equation in the considered neighborhood of zero. For service times bounded from below, surprisingly simple expressions for the LST and variance of V(τ) in this neighborhood of zero are derived, which yield in particular the LST and variance of V(τ) in M/D/2-PS.