Calculation of output characteristics of a priority queue through a busy period analysis

In this paper, we analyze some output characteristics of a discrete-time two-class priority queue by means of probability generating functions. Therefore, we construct a Markov chain which – after analysis – provides a.o. the probability generating functions of the lengths of the busy periods of both classes. It is furthermore shown how performance measures, related to the output process, are calculated from these functions. The queueing model is kept fairly simple to explain the method of analysis of the busy periods and the output characteristics of priority queues as clearly as possible.     

Analysis of flexible manufacturing systems with priority scheduling: PMVA

A new methodology for performance analysis of flexible manufacturing systems (FMSs) with priority scheduling is presented. The analytic model developed extends the mean value analysis of closed networks of queues with multiple product types, various non-preemptive priority service disciplines, and with parallel machine stations. Performance measures derived include the expected throughput per product and per station, utilization of machines and transporters, queuing times and queue length measures for various configurations. Extensive numerical calculations have shown that the algorithm used for solving the problem converges rapidly and retains numerical stability for large models. The paper also illustrates the application of the model to a system with a mixture of FCFS and HOL disciplines which gives insights into various priority assignment policies in FMSs. Special attention was given to the problem of scheduling the robot carriers (transporters).     

带有转换时间和阀值的非抢占优先权排队模型

在[3]中,我们研究了在抢占规则下带有转换时间和阈值的两类顾客优先权排队系统,本文就非抢占情形对这样的系统作进一步的研究,同样求出两类顾客队长的稳态联合概率母函数。籍助这些母函数可求出诸如平均队长这样一些重要的系统性能指标。     

Analysis of a discrete-time preemptive resume priority buffer

In this paper, we analyze a discrete-time preemptive resume priority queue. We consider two classes of customers which have to be served, where customers of one class have preemptive resume priority over customers of the other. Both classes contain customers with generally distributed service times. We show that the use of probability generating functions is beneficial for analyzing the system contents and customer delays of both classes. It is shown (theoretically as well as by some practical procedures) how moments and approximate tail probabilities of system contents and customer delays are calculated. The influence of the priority scheduling discipline and the service time distributions on the performance measures is shown by some numerical examples.     

带有阈值转换和启动时间的优先权排队

在诸如ＩＳＤＮ的通信网络中,多种信息共用一条线路,为了满足不同类型信息的服务质量要求,带有阈值转换的优先权排队系统应是一种合适的模型。本文研究单服务员、两类顾客的带有阈值转换和启动时间的优先权排队系统,首先,分别就抢占和非抢占情形讨论了具有泊松到达、服务时间和启动时间均有指数贩系统,然后就非抢占情况进上步考虑了服务时间和启动时间有一般分布的系统,求出了系统中两类顾客队长的稳态联合概率母函数,藉助这     

The discrete-time preemptive repeat identical priority queue

Priority queueing systems come natural when customers with diversified delay requirements have to wait to get service. The customers that cannot tolerate but small delays get service priority over customers which are less delay-sensitive. In this contribution, we analyze a discrete-time two-class preemptive repeat identical priority queue with infinite buffer space and generally distributed service times. Newly arriving high-priority customers interrupt the on-going service of a low-priority customer. After all high-priority customers have left the system, the interrupted service of the low-priority customer has to be repeated completely. By means of a probability generating functions approach, we analyze the system content and the delay of both types of customers. Performance measures (such as means and variances) are calculated and the impact of the priority scheduling is discussed by means of some numerical examples.     

A preemptive repeat priority queue with resampling: Performance analysis

In this paper, we analyze a discrete-time preemptive repeat priority queue with resampling. High-priority packets have preemptive repeat priority, and interrupted low-priority packets are subjected to independent retransmission attempts. Both classes contain packets with generally distributed transmission times. We show that the use of generating functions is beneficial for analyzing the system contents and packet delay of both classes. The influence of the priority scheduling on the performance measures is illustrated by some numerical examples. This work has been supported by the Interuniversity Attraction Poles Programme–Belgian Science Policy.     

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.     

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.     

Sequence of operations analysis for dynamic data structures

This paper introduces a rather general technique for computing the average-case performance of dynamic data structures, subjected to arbitrary sequences of insert, delete, and search operations. The method allows us effectively to evaluate the integrated cost of various interesting data structure implementations, for stacks, dictionaries, symbol tables, priority queues, and linear lists; it can thus be used as a basis for measuring the efficiency of each proposed implementation. For each data type, a specific continued fraction and a family of orthogonal polynomials are associated with sequences of operations: Tchebycheff for stacks, Laguerre for dictionaries, Charlier for symbol tables, Hermite for priority queues, and Meixner for linear lists. Our main result is an explicit expression, for each of the above data types, of the generating function for integrated costs, as a linear integral transform of the generating functions for individual operation costs. We use the result to compute explicitly integrated costs of various implementations of dictionaries and priority queues.     

On two-queue Markovian polling systems with exhaustive service

We consider a class of two-queue polling systems with exhaustive service, where the order in which the server visits the queues is governed by a discrete-time Markov chain. For this model, we derive an expression for the probability generating function of the joint queue length distribution at polling epochs. Based on these results, we obtain explicit expressions for the Laplace–Stieltjes transforms of the waiting-time distributions and the probability generating function of the joint queue length distribution at an arbitrary point in time. We also study the heavy-traffic behaviour of properly scaled versions of these distributions, which results in compact and closed-form expressions for the distribution functions themselves. The heavy-traffic behaviour turns out to be similar to that of cyclic polling models, provides insights into the main effects of the model parameters when the system is heavily loaded, and can be used to derive closed-form approximations for the waiting-time distribution or the queue length distribution.     

Analysis of multiclass Markovian polling systems with feedback and composite scheduling algorithms

We consider multiclass Markovian polling systems with feedback and analyze their average performance measures. Scheduling in polling systems has many applications in computer and communication systems. We utilize the framework that has been effectively used to analyze various composite scheduling algorithms in many types of multiclass queues systematically in conjunction with the functional computation method (Hirayama in Naval Research Logistics 50:719?C741, 2003; Journal of the Operations Research Society of Japan 48:226?C255, 2005; Advances in queueing theory and network applications, pp. 119?C146, Springer, New?York, 2009a; Journal of Industrial and Management Optimization 6:541?C568, 2010). We define the conditional expected values of the performance measures such as the sojourn times as functions of the system state and find their expressions by solving some equations. Then from these expressions, we derive the average numbers of customers and the average sojourn times for all service stages of customers circulating the system. We consider their application to a packet scheduling problem where multiple categories of packets share a resource.     

A semidefinite optimization approach to the steady-state analysis of queueing systems

Obtaining (tail) probabilities from a transform function is an important topic in queueing theory. To obtain these probabilities in discrete-time queueing systems, we have to invert probability generating functions, since most important distributions in discrete-time queueing systems can be determined in the form of probability generating functions. In this paper, we calculate the tail probabilities of two particular random variables in discrete-time priority queueing systems, by means of the dominant singularity approximation. We show that obtaining these tail probabilities can be a complex task, and that the obtained tail probabilities are not necessarily exponential (as in most ‘traditional’ queueing systems). Further, we show the impact and significance of the various system parameters on the type of tail behavior. Finally, we compare our approximation results with simulations.     

Prediction in Markovian bulk arrival queues

This paper deals with the statistical analysis of bulk arrival queues from a Bayesian point of view. The focus is on prediction of the usual measures of performance of the system in equilibrium. Posterior predictive distribution of the number of customers in the system is obtained through its probability generating function. Posterior distribution of the waiting time, in the queue and in the system, of the first customer of an arriving group is expressed in terms of their Laplace and Laplace–Stieltjes transform. Discussion of numerical inversion of these transforms is addressed.     

Performance analysis of a GI-Geo-1 buffer with a preemptive resume priority scheduling discipline

In this paper, we analyze a discrete-time GI-Geo-1 preemptive resume priority queue. We consider two classes of packets which have to be served, where one class has preemptive resume priority over the other. We show that the use of generating functions is beneficial for analyzing the system contents and packet delay of both classes. Moments and (approximate) tail probabilities of system contents and packet delay are calculated. The influence of the priority scheduling is shown by some numerical examples.     

Smoothed perturbation analysis algorithms for estimating the derivatives of occupancy-related functions in serial queueing networks

We present unbiased Smoothed Perturbation Analysis (SPA) estimators for the derivatives of occupancy-related performance functions in serial networks ofG/G/1 queues with respect to parameters of the distributions of service times at the queues. The sample functions for these performance measures are piecewise constant, and established Infinitesimal Perturbation Analysis (IPA) methods typically fail to provide unbiased estimators in this case. The performance measures considered in this paper are: the average network occupancy as seen by an arrival, the average occupancy of a specific queue as seen by an arrival to it, the probability that a customer is blocked at a specific queue, and the probability that a customer leaves a queue idle. The SPA estimators derived are quite simple and flexible, and they lend themselves to straightforward analysis. Unlike most of the established SPA algorithms, ours are not based on the comparison of hazard rates, and the proofs of their unbiasedness do not require the boundedness of such hazard rates.Supported in part by the National Science Foundation under Grant ECS-8801912, by the Office of Naval Research under Contract N00014-87-K-0304, and by NASA under Contract NAG 2-595.     

Analyzing priority queues with 3 classes using tree-like processes

In this paper we demonstrate how tree-like processes can be used to analyze a general class of priority queues with three service classes, creating a new methodology to study priority queues. The key result is that the operation of a 3-class priority queue can be mimicked by means of an alternate system that is composed of a single stack and queue. The evolution of this alternate system is reduced to a tree-like Markov process, the solution of which is realized through matrix analytic methods. The main performance measures, i.e., the queue length distributions and loss rates, are obtained from the steady state of the tree-like process through a censoring argument. The strength of our approach is demonstrated via a series of numerical examples. AMS Subject Classifications Primary—60K25; Secondary—60M20, 90B22     

Inference and prediction in bulk arrival queues and queues with service in stages

This paper deals with the statistical analysis from a Bayesian point of view, of bulk arrival queues where the batch size is considered as a fixed constant. The focus is on prediction of the usual measures of performance of the system in the steady state. The probability generating function of the posterior predictive distribution of the number of customers in the system and the Laplace transform of the posterior predictive distribution of the waiting time in the system are obtained. Numerical inversion of these transforms is considered. Inference and prediction of its equivalent single queue with service in stages is also discussed. © 1998 John Wiley & Sons, Ltd.     

Busy periods of discrete-time queues using the Lagrange implicit function theorem

In this paper, we study the busy-period distribution for discrete-time queues assuming a Bernoulli arrival process, with arbitrary service-time and batch-arrival distributions. We derive explicit analytic formulas for these distributions using the Lagrange Implicit Function Theorem applied to probability generating functions. The convenient coefficient operator notation used in these formulas leads to a computationally efficient method for obtaining the distributions in their entirety from these analytic formulas.     

Numerical analysis for bulk-arrival queueing systems: Root-finding and steady-state probabilities inGI r /M/1 queues

Queueing theorists have presented, as solutions to many queueing models, probability generating functions in which state probabilities are expressed as functions of the roots of characteristic equations, evaluation of the roots in particular cases being left to the reader. Many users have complained that such solutions are inadequate. Some queueing theorists, in particular Neuts [6], rather than use Rouché's theorem to count roots and an equation-solver to find them, have developed new algorithms to solve queueing problems numerically, without explicit calculation of roots. Powell [7] has shown that in many bulk service queues arising in transportation models, characteristic equations can be solved and state probabilities can be found without serious difficulty, even when the number of roots to be found is large. We have slightly modified Powell's method, and have extended his work to cover a number of bulk-service queues discussed by Chaudhry et al. [1] and a number of bulk-arrival queues discussed in the present paper.