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.      

An M/G/1 Retrial Queueing System with Two-Phase Service and Preemptive Resume

An M/G/1 retrial queueing system with additional phase of service and possible preemptive resume service discipline is considered. For an arbitrarily distributed retrial time distribution, the necessary and sufficient condition for the system stability is obtained, assuming that only the customer at the head of the orbit has priority access to the server. The steady-state distributions of the server state and the number of customers in the orbit are obtained along with other performance measures. The effects of various parameters on the system performance are analysed numerically. A general decomposition law for this retrial queueing system is established.     

非强占优先权下的M/M/1排队

分析带有两个优先权的非强占M/M/1系统的性能,用补充变量法构造向量马尔可夫过程对此排队系统的状态转移方程进行分析,得到两类顾客在非强占优先权的队长联合分布的母函数,进一步讨论,得出了服务台被两类顾客占有和闲置的概率以及两类信元各自的平均队长.     

有两个服务阶段、反馈、强占型的M/G/1重试排队

在假定重试区域中只有队首的顾客允许重试的条件下,重试时间是一般分布时,考虑具有两个服务阶段、反馈、强占型的M／G／1重试排队系统．得到了系统稳态的充要条件．求得稳态时系统队长和重试区域中队长分布及相关指标,并且得到了系统的随机分解性质．     

Relative priority policies for minimizing the cost of queueing systems with service discrimination

This paper considers several single-server two-class queueing systems with different cost functions. Customers in the two classes are discriminated by service rates and relative priorities. Most attention is focused on the ones with general quadratic bivariable and exponential cost functions that are usually applied in the relatively complicated systems. To the best of the authors’ knowledge, there is no literature analyzing these two kinds of cost functions on the subject of relative priority. We explicitly present the conditions under which relative priority outperforms absolute priority for reducing system cost and further provide the method to find the optimal DPS policy. Moreover, we also discuss variations where service rates of the two classes are decision variables under service equalization and service discrimination disciplines, respectively.     

M/G/1 retrial queueing systems with two types of calls and finite capacity

We consider anM/G/1 priority retrial queueing system with two types of calls which models a telephone switching system and a cellular mobile communication system. In the case that arriving calls are blocked due to the server being busy, type I calls are queued in a priority queue of finite capacityK whereas type II calls enter the retrial group in order to try service again after a random amount of time. In this paper we find the joint generating function of the numbers of calls in the priority queue and the retrial group in closed form. When ₁=0, it is shown that our results are consistent with the known results for a classical retrial queueing system.     

A queueing model for a nonreliable multiterminal system with polling scheduling

This paper deals with a nonhomogeneous finite-source queueing model to describe the performance of a multiterminal system subject to random breakdowns under the polling service discipline. The model studied here is a closed queueing network which has three service stations. a CPU (single server), terminals (infinite server), a repairman (single server), and a finite number of customers (jobs) that have distinct service rates at the service stations. The CPU's repair has preemptive priority over the terminal repairs, and failure of the CPU stops the service of the other stations, thus the nodes are not independent. It can be viewed as a continuation of papers by the authors (see references), which discussed a FIFO (first-in, first-out) and a PPS (priority processor sharing) serviced queueing model subject to random breakdowns. All random variables are assumed to be independent and exponentially distributed. The system behavior can be described by a Markov chain, but the number of states is very large. The purpose of this paper is to give a recursive computational approach to solve steady-state equations and to illustrate the problem in question using some numerical results. Supported by the Hungarian National Foundation for Scientific Research (grant Nos. OTKA T014974/95 and T016933/95) Proceedings of the Seminar on Stability Problems for Stochastic Models. Hajdúszoboszló, Hungary, 1997, Part, II.     

A simulation tool to evaluate the performance of finite-source queueing models

This paper deals with a software tool to evaluate the main characteristics of a nonhomogeneous finite-source queueing model to describe the performance of a multi-terminal system subject to random breakdowns under FIFO, priority processor sharing, and polling service disciplines. The model studied here is actually a closed queueing network network with three nonindependent service stations (CPU, terminals, and repairman), and a finite number of customers (jobs), which have different service rates at the service stations. The aim of this paper is to introduce the FQM (finite-source queueing model) program package, which was developed at the Institute of Mathematics and Informatics of Lajos Kossuth University in Debrecen, Hungary, and to investigate the performance of the above-mentioned finite-source queueing models. At the end we give a sample result to illustrate the problem in question. Supported by the Hungarian National Foundation for Scientific Research (grant Nos. OTKA T014974/95 and T016933/95). Proceedings of the Seminar on Stability Problems for Stochastic Models, Vologda, Russia, 1998, Part I.     

A discrete-time Geo/G/1 retrial queue with preferred and impatient customers

This paper is concerned with a discrete-time Geo/G/1 retrial queue with preferred, impatient customers and general retrial times. We analyze the Markov chain underlying the considered queueing system and derive its ergodicity condition. The system state distribution as well as the orbit size and the system size distributions are obtained in terms of their generating functions. These generating functions yield exact expressions for different performance measures. Besides, the stochastic decomposition property and the corresponding continuous-time queueing system are investigated. Finally, some numerical examples are provided to illustrate the effect of priority and impatience on several performance characteristics of the system.     

Proof of Monotone Loss Rate of Fluid Priority-Queue with Finite Buffer

This paper studies a fluid queueing system that has a single server, a single finite buffer, and which applies a strict priority discipline to multiple arriving streams of different classes. The arriving streams are modeled by statistically independent, identically distributed random processes. A proof is presented for the highly intuitive result that, in such a queueing system, a higher priority class stream has a lower average fluid loss rate than a lower priority class stream. The proof exploits the fact that for a work-conserving queue, the fluid loss rate for a given class is invariant of what queueing discipline is applied to all arriving fluid of this particular class. AMS subject classification: 60K25, 68M20     

Stability and busy periods in a multiclass queue with state-dependent arrival rates

We introduce a multiclass single-server queueing system in which the arrival rates depend on the current job in service. The system is characterized by a matrix of arrival rates in lieu of a vector of arrival rates. Our proposed model departs from existing state-dependent queueing models in which the parameters depend primarily on the number of jobs in the system rather than on the job in service. We formulate the queueing model and its corresponding fluid model and proceed to obtain necessary and sufficient conditions for stability via fluid models. Utilizing the natural connection with the multitype Galton–Watson processes, the Laplace–Stieltjes transform of busy periods in the system is given. We conclude with tail asymptotics for the busy period for heavy-tailed service time distributions for the regularly varying case.     

Exact tail asymptotics in a priority queue—characterizations of the non-preemptive model

This is a companion paper to Li and Zhao (Queueing Syst. 63:355–381, 2009) recently published in Queueing Systems, in which the classical preemptive priority queueing system was considered. In the current paper we consider the classical non-preemptive priority queueing system with two classes of independent Poisson customers and a single exponential server serving the two classes of customers at possibly different rates. A complete characterization of the regions of system parameters for exact tail asymptotics is obtained through an analysis of generating functions. This is done for the joint stationary distribution of the queue length of the two classes of customers, for the two marginal distributions and also for the distribution of the total number of customers in the system, respectively. This complete characterization is supplemental to the existing literature, which would be useful to researchers.     

Workload in queues having priorities assigned according to service time

System designers often implement priority queueing disciplines in order to improve overall system performance; however, improvement is often gained at the expense of lower priority cystomers. Shortest Processing Time is an example of a priority discipline wherein lower priority customers may suffer very long waiting times when compared to their waiting times under a democratic service discipline. In what follows, we shall investigate a queueing system where customers are divided into a finitie number of priority classes according to their service times.We develop the multivariate generating function characterizing the joint workload among the priority classes. First moments obtained from the generating function yield traffic intensities for each priority class. Second moments address expected workloads, in particular, we obtain simple Pollaczek-Khinchine type formulae for the classes. Higher moments address variance and covariance among the workloads of the priority classes.This work was supported in part by National Science Foundation Grant DDM-8913658.     

Exact tail asymptotics in a priority queue—characterizations of the preemptive model

In this paper, we consider the classical preemptive priority queueing system with two classes of independent Poisson customers and a single exponential server serving the two classes of customers at possibly different rates. For this system, we carry out a detailed analysis on exact tail asymptotics for the joint stationary distribution of the queue length of the two classes of customers, for the two marginal distributions and for the distribution of the total number of customers in the system, respectively. A complete characterization of the regions of system parameters for exact tail asymptotics is obtained through analysis of generating functions. This characterization has never before been completed. It is interesting to note that the exact tail asymptotics along the high-priority queue direction is of a new form that does not fall within the three types of exact tail asymptotics characterized by various methods for this type of two-dimensional system reported in the literature. We expect that the method employed in this paper can also be applied to the exact tail asymptotic analysis for the non-preemptive priority queueing model, among other possibilities.     

Delay analysis of a discrete-time multiclass slot-bound priority system

This paper introduces a new priority mechanism in discrete-time queueing systems that compromises between first-come-first-served (FCFS) and head-of-line priority. In this scheduling discipline—which we dubbed slot-bound priority—customers of different priority classes entering the system during the same time-slot are served in order of their respective priority class. Customers entering during different slots are served on a FCFS basis. In this paper we study the delay in an N-class discrete-time queueing system under slot-bound priority. General independent arrivals and class-specific general service time distributions are assumed. Expressions for the probability generating function of the delay of a random type-j customer are derived, from which the respective moments are easily obtained. The tail behaviour of these distributions is analyzed as well, and some numerical examples show the effect slot-bound priority can have on the performance measures.     

Queueing Systems with a Removable Service Station

A single-server queueing system with constant Poisson input is considered and the partial elimination of the station's idle fraction is envisaged by intermittent close-down and set-up. The rule pertaining to the dismantling and re-establishing of the service station—the management doctrine—is based on the instantaneous size of the queue, but these processes are assumed to consume time. Operating characteristics of such systems—in particular, average queue length and queueing time—are evaluated. A cost structure is superimposed on the system and optimization procedures are outlined. The close relationship with (a) priority queueing and (b) storage models is pointed out.     

A Simple proof for the stability of global FIFO queueing networks

We study the stability of multiclass queueing networks under the global FIFO （first in first out） service discipline, which was established by Bramson in 2001. For these networks, the service priority of a customer is determined by his entrance time. Using fluid models, we describe the entrance time of the most senior customer in the networks at time t, which is the key to simplify the proof for the stability of the global FIFO queueing networks.     

Maximum Entropy Condition in Queueing Theory

The main results in queueing theory are obtained when the queueing system is in a steady-state condition and if the requirements of a birth-and-death stochastic process are satisfied. The aim of this paper is to obtain a probabilistic model when the queueing system is in a maximum entropy condition. For applying the entropic approach, the only information required is represented by mean values (mean arrival rates, mean service rates, the mean number of customers in the system). For some one-server queueing systems, when the expected number of customers is given, the maximum entropy condition gives the same probability distribution of the possible states of the system as the birth-and-death process applied to an M/M/1 system in a steady-state condition. For other queueing systems, as M/G/1 for instance, the entropic approach gives a simple probability distribution of possible states, while no close expression for such a probability distribution is known in the general framework of a birth-and-death process.     

Mean sojourn times for phase-type discriminatory processor sharing systems

In a discriminatory processor sharing (DPS) queueing model, each job (or customer) belongs to one out of finitely many classes. The arrival processes are Poisson. Classes differ with respect to arrival rates and service time distributions. Moreover, classes have different priority levels. All jobs present are served simultaneously but the fraction of the server’s capacity allocated to each one of them is proportional to their class priority parameter (while the total capacity is of course fixed).