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.     

Expulsion and scheduling control for multiclass queues with heterogeneous servers

We consider an M/M/2 system with nonidentical servers and multiple classes of customers. Each customer class has its own reward rate and holding cost. We may assign priorities so that high priority customers may preempt lower priority customers on the servers. We give two models for which the optimal admission and scheduling policy for maximizing expected discounted profit is determined by a threshold structure on the number of customers of each type in the system. Surprisingly, the optimal thresholds do not depend on the specific numerical values of the reward rates and holding costs, making them relatively easy to determine in practice. Our results also hold when there is a finite buffer and when customers have independent random deadlines for service completion.     

Transient analysis of queues with heterogeneous arrivals

In this paper we consider a discrete time queueing model where the time axis is divided into time slots of unit length. The model satisfies the following assumptions: (i) an event is either an arrival of typei of batch sizeb _i, i=1,...,r with probability _i or is a depature of a single customer with probability or zero depending on whether the queue is busy or empty; (ii) no more than one event can occur in a slot, therefore the probability that neither an arrival nor a departure occurs in a slot is 1––_{i i} or 1–_{i i} according as the queue is busy or empty; (iii) events in different slots are independent. Using a lattice path representation in higher dimensional space we will derive the time dependent joint distribution of the number of arrivals of various types and the number of completed services. The distribution for the corresponding continuous time model is found by using weak convergence.     

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.     

Nonstationary queues with Interrrupted Poisson arrivals and unreliable/repairable servers

A queueing model having a nonstationary Interrupted Poisson arrival process (IPP(t)),s time-dependent exponential unreliable/repairable servers and finite capacityc is introduced, and an approximation method for analysis of it is developed and tested. Approximations are developed for the time-dependent queue length moments and the system viewpoint waiting time distributions and moments. The approximation involves state-space partitioning and numerically integrating partial-moment differential equations (PMDEs). Surrogate distribution approximations (SDA's) are used to close the system of PMDEs. The approximations allow for analysis using only (s + 1)(s + 6) differential equations for the queue length moments rather than the 2(c + 1)(s +1) equations required by the classic method of numerically integrating the full set of Kolmogorov-forward equations. Effectively hours of cpu time are reduced to minutes for even modest capacity systems. Approximations for waiting time distributions and moments are developed.This research was partially funded by National Science Foundation grant ECS-8404409.     

Numerical analysis of multi-server queues with deterministic service and special phase-type arrivals

In this paper we study multi-server queues with deterministic service times and a phase-type arrival process. In particular, we consider for the interarrival time hyperexponential distributions and mixtures of Erlang distributions with the same scale parameter. We give an algorithm to compute the steady state probabilities of the number of customers in the system and derive explicit expressions for various operating characteristics.Special attention is paid to the numerical evaluation of the required transition probabilities and the implementation of the iterative solution method for the steady state probabilities.

---

Zusammenfassung In dieser Arbeit werden Bedienungssysteme mit mehreren parallelen Schaltern studiert, wobei ein Ankunftsstrom vom Phasentyp und deterministische Bedienungszeiten angenommen werden. Speziell werden hyperexponentialverteilte Zwischenankunftszeiten betrachtet oder solche, die nach einer Mischung von Erlangverteilungen mit dem selben Skalenparameter verteilt sind. Es werden ein Algorithmus zur Berechnung der stationären Wahrscheinlichkeiten für die Anzahl der Kunden im System angegeben sowie explizite Ausdrücke für diverse Charakteristiken hergeleitet.Besonderes Gewicht liegt auf der numerischen Berechnung der benötigten Übergangswahrscheinlichkeiten und der Implementierung der iterativen Methode zur Berechnung der stationären Wahrscheinlichkeiten.

     

Time-dependent analysis of a queue with batch arrivals andn levels of nonpreemptive priority

A queueing system with batch arrivals andn classes of customers with nonpreemptive priorities between them is considered. Each batch arrives according to the Poisson distribution and contains customers of all classes while the service times follow arbitrary distributions with different probability density functions for each class. For such a model the system states probabilities both in the transient and in the steady state are analysed and also expressions for the Laplace transforms of the busy period densities for each class and for the general busy period are obtained.     

Waiting time analysis of the multiple priority dual queue with a preemptive priority service discipline

The dual queue consists of two queues, called the primary queue and the secondary queue. There is a single server in the primary queue but the secondary queue has no service facility and only serves as a holding queue for the overloaded primary queue. The dual queue has the additional feature of a priority scheme to help reduce congestion. Two classes of customers, class 1 and 2, arrive to the dual queue as two independent Poisson processes and the single server in the primary queue dispenses an exponentially distributed service time at the rate which is dependent on the customer’s class. The service discipline is preemptive priority with priority given to class 1 over class 2 customers. In this paper, we use matrix-analytic method to construct the infinitesimal generator of the system and also to provide a detailed analysis of the expected waiting time of each class of customers in both queues.     

Decomposition of an M/D/r·k queue with FIFO into k Ek/D/r queues with FIFO

It is observed that the queuing system M/D/r·k with FIFO has the same waiting time distribution as the queuing system E_k/D/r with FIFO. Using this simple equivalence we can apply numerical methods and tables for M/Dn to solve E_k/D/r.     

Fluctuation analysis in queues with several operational modes and priority customers

We analyze a complex queueing system with a single server operating in three different modes and dependent on circumstances, servicing two different queues simultaneously. There are different switching policies that specify when the server takes one or two queues. Main techniques are based on fluctuation analysis. One of the objectives is to model processes that occur in software, computer, and electrical engineering, and to argue that methods of fluctuation theory produce closed form functionals.     

Analysis of nonpreemptive priority queues with multiple servers and two priority classes

In this paper, we model a priority multiserver queueing system with two priority classes. A high priority customer has nonpreemptive priority over low priority customers. The approaches for solving the problem are the state-reduction based variant of Kao, the modified boundary algorithm of Latouche, the logarithmic reduction algorithm of Latouche and Ramaswami, and the power-series method of Blanc. The objectives of this paper are to present a power-series implementation for the priority queue and to evaluate the relative efficiencies of alternative procedures to compute various performance characteristics. In the paper, we find that at times the logarithmic reduction algorithm may not perform as well as expected and the power-series approach can occasionally pose numerical difficulties.     

Analysis of finite-buffer multi-server queues with group arrivals: GIX/M/c/N

In this paper, we analyse a multi-server queue with bulk arrivals and finite-buffer space. The interarrival and service times are arbitrarily and exponentially distributed, respectively. The model is discussed with partial and total batch rejections and the distributions of the numbers of customers in the system at prearrival and arbitrary epochs are obtained. In addition, blocking probabilities and waiting time analyses of the first, an arbitrary and the last customer of a batch are discussed. Finally, some numerical results are presented. This revised version was published online in June 2006 with corrections to the Cover Date.     

Delay analysis of discrete-time priority queue with structured inputs

This paper investigates a discrete-time priority queue with multi-class customers. Applying a delay-cycle analysis, we explicitly derive the probability generating function of the waiting time for an individual class in a geometric batch input queue under preemptive-resume and head-of-the-line priority rules. The conservation law and waiting time characterization for a general class of discrete-time queues are also presented. The results in this paper cover several previous results as special cases.     

Busy-period and blocking behavior of finite queues with state-dependent Markov renewal arrivals

The busy-period length distributions and blocking probabilities are considered for finiteG/G/1/K queues with state-dependent Markov renewal arrivals. The Laplace-Stieltjes transforms of the distributions and blocking probabilities are given for the non-preemptive and last-come-first-served preemptive resume (or repeat) service disciplines. For Erlangian (or deterministic) service times in particular, it is proved that the busy-period length (the number of blocked customers) for the non-preemptive discipline is smaller (larger) than for the preemptive resume discipline.     

Waiting time and queue length analysis of Markov-modulated fluid priority queues

Queueing Systems - This paper considers a multi-type fluid queue with priority service. The input fluid rates are modulated by a Markov chain, which is common for all fluid types. The service rate...     

Product form in networks of queues with batch arrivals and batch services

A product form equilibrium distribution is derived for a class of queueing networks in either discrete or continuous time, in which multiple customers arrive simultaneously and batches of customers complete service simultaneously.     

A tandem of discrete-time queues with arrivals and departures at each stage

A discrete-time system of a tandem of queues with exogenous arrivals and departures at each stage is considered. A customer leaving queuek–1 departs the system with probability 1– ^[k] and continues to queuek with probability ^[k] . Exogenous arrivals to each stage are i.i.d. at each time slot. An approximate analysis of the occupancy and busy-period distributions of each stage based on a General Busy-period with batches and Memoryless (geometric) Idle period renewal Process (GBMIP) provides improved performance over two-state Markov approximations and gives exact results when there are no interstage departures.This research was supported in part by NSF grant NCR-8708282.     

Delay analysis of two batch-service queueing models with batch arrivals: Geo X /Geo c /1

In this paper, we compute the probability generating functions (PGF’s) of the customer delay for two batch-service queueing models with batch arrivals. In the first model, the available server starts a new service whenever the system is not empty (without waiting to fill the capacity), while the server waits until he can serve at full capacity in the second model. Moments can then be obtained from these PGF’s, through which we study and compare both systems. We pay special attention to the influence of the distribution of the arrival batch sizes. The main observation is that the difference between the two policies depends highly on this distribution. Another conclusion is that the results are considerably different as compared to Bernoulli (single) arrivals, which are frequently considered in the literature. This demonstrates the necessity of modeling the arrivals as batches.