Discrete-time queues with discretionary priorities

In this paper, we consider a discrete-time two-class discretionary priority queueing model with generally distributed service times and per slot i.i.d. structured inputs in which preemptions are allowed only when the elapsed service time of a lower-class customer being served does not exceed a certain threshold. As the preemption mode of the discretionary priority discipline, we consider the Preemptive Resume, Preemptive Repeat Different, and Preemptive Repeat Identical modes. We derive the Probability Generating Functions (PGFs) and first moments of queue lengths of each class in this model for all the three preemption modes in a unified manner. The obtained results include all the previous works on discrete-time priority queueing models with general service times and structured inputs as their special cases. A numerical example shows that, using the discretionary priority discipline, we can more subtly adjust the system performances than is possible using either the pure non-preemptive or the preemptive priority disciplines.     

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.     

输入率可变、反馈的、且有负顾客的优先排队模型

针对实际应用中存在输入率可变、因服务出差错而导致顾客需要重新排队接受服务以及不同的顾客类需要不同的服务质量等现状,建立了输入率可变、有反馈及负顾客的、服务时间服从一般分布优先排队模型.得出了"强占优先"与"非强占优先"两种服务规则下,系统中每一类顾客的队长、等待时间、逗留时间的平稳分布均存在,并求出了每一类顾客的队长、等待时间、逗留时间及他们的L-S变换,忙期等指标,最后还指出了模型在应用中的注意事项及要进一步解决的问题.     

Threshold-based interventions to optimize performance in preemptive priority queues

This paper studies a single-server priority queueing model in which preemptions are allowed during the early stages of service. Once enough service effort has been rendered, however, further preemptions are blocked. The threshold where the change occurs is either a proportion of the service requirement, or time-based. The Laplace–Stieltjes transform and mean of each class sojourn time are derived for a model which employs this hybrid preemption policy. Both preemptive resume and preemptive repeat service disciplines are considered. Numerical examples show that it is frequently the case that a good combination of preemptible and nonpreemptible service performs better than both the standard preemptive and nonpreemptive queues. In a number of these cases, the thresholds that optimize performance measures such as overall average sojourn time are determined. This revised version was published online in June 2006 with corrections to the Cover Date.     

An Exact Solution for the State Probabilities of the Multi-Class,Multi-Server Queue with Preemptive Priorities

We consider a multi-class, multi-server queueing system with preemptive priorities. We distinguish two groups of priority classes that consist of multiple customer types, each having their own arrival and service rate. We assume Poisson arrival processes and exponentially distributed service times. We derive an exact method to estimate the steady state probabilities. Because we need iterations to calculate the steady state probabilities, the only error arises from choosing a finite number of matrix iterations. Based on these probabilities, we can derive approximations for a wide range of relevant performance characteristics, such as the moments of the number of customers of a certain type in the system en the expected postponement time for each customer class. We illustrate our method with some numerical examples. Numerical results show that in most cases we need only a moderate number of matrix iterations (∼20) to obtain an error less than 1% when estimating key performance characteristics.This revised version was published online in June 2005 with corrected coverdate     

Waiting Time Distributions in the Preemptive Accumulating Priority Queue

We consider a queueing system in which a single server attends to N priority classes of customers. Upon arrival to the system, a customer begins to accumulate priority linearly at a rate which is distinct to the class to which it belongs. Customers with greater accumulated priority levels are given preferential treatment in the sense that at every service selection instant, the customer with the greatest accumulated priority level is selected next for servicing. Furthermore, the system is preemptive so that the servicing of a customer is interrupted for customers with greater accumulated priority levels. The main objective of the paper is to characterize the waiting time distributions of each class. Numerical examples are also provided which exemplify the true benefit of incorporating an accumulating prioritization structure, namely the ability to control waiting times.     

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.     

Mixing of non-preemptive and preemptive repeat priority disciplines

A single server dispenses service to m priority classes. The arrival process of the ith class, i = 1, 2,…,m, is homogeneous Poisson. Service times of each class are independent, identical, arbitrarily-distributed random variables with a finite second moment. The smaller the index of a class, the higher its priority degree. For i < j, class i has preemptive priority over j if and only if j ? i > d (where d is a predetermined non-negative integer), and non-preemptive priority otherwise. An interrupted service is resumed when the system contains no costomers with higher priority, preemptive and non-preemptive. Within each priority class the FIFO rule is obeyed.The preemptive regimes analyzed are repeat with and without resampling. For a k-customer, k = 1, 2,…,n, steady-state Laplace-Stieltjes transforms, and expectations of the waiting time and the time in the system are calculated.     

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.     

MAP/(PH/PH)/c Queue with Self-Generation of Priorities and Non-Preemptive Service

Abstract

Customers arriving according to a Markovian arrival process are served at a c server facility. Waiting customers generate into priority while waiting in the system (self-generation of priorities), at a constant rate γ; such a customer is immediately taken for service, if at least one of the servers is free. Else it waits at a waiting space of capacity c exclusively for priority generated customers, provided there is vacancy. A customer in service is not preempted to accommodate a priority generated customer. The service times of ordinary and priority generated customers follow distinct PH-distributions. It is proved that the system is always stable. We provide a numerical procedure to compute the optimal number of servers to be employed to minimize the loss to the system. Several performance measures are evaluated.     

Insensitivity of multiclass systems with general dynamic preemptive resume queueing disciplines

We are concerned with the insensitivity of the stationary distributions of the system states inM/G/s/m queues with multiclass customers and with LIFO preemptive resume service disciplines. We introduce general entrance and exit rules into and from waiting positions, respectively, for the behaviour of waiting customers whose service is interrupted. These rules may, roughly speaking, depend on the number of customers in the system. It is shown that the stationary distribution of the system state is insensitive not only with respect to the service time distributions but also with respect to the general entrance and exit rules. As well as the insensitivity of the service scheme, our results are obtained for a special form of state and customer type dependent arrival and service rates. Some further results are concluded related to insensitivity like the formula for the conditional mean sojourn time and the property of transformation of a Poisson input into a Poisson output by the systems.     

On priority queues with impatient customers

In this paper, we study three different problems where one class of customers is given priority over the other class. In the first problem, a single server receives two classes of customers with general service time requirements and follows a preemptive-resume policy between them. Both classes are impatient and abandon the system if their wait time is longer than their exponentially distributed patience limits. In the second model, the low-priority class is assumed to be patient and the single server chooses the next customer to serve according to a non-preemptive priority policy in favor of the impatient customers. The third problem involves a multi-server system that can be used to analyze a call center offering a call-back option to its impatient customers. Here, customers requesting to be called back are considered to be the low-priority class. We obtain the steady-state performance measures of each class in the first two problems and those of the high-priority class in the third problem by exploiting the level crossing method. We furthermore adapt an algorithm from the literature to obtain the factorial moments of the low-priority queue length of the multi-server system exactly.      

A Regularly Preemptive Model and its Approximations

A regularly preemptive model D,MAP/D ₁,D ₂/1 is studied. Priority customers have constant inter-arrival times and constant service times. On the other hand, ordinary customers' arrivals follow a Markovian Arrival Process (MAP) with constant service times. Although this model can be formulated by using the piecewise Markov process, there remain some difficult problems on numerical calculations. In order to solve these problems, a novel approximation model MAP/MR/1 with Markov renewal services is proposed. These two queueing processes become different due to the existence of idle periods. Thus, a MAP/MR/1 queue with a general boundary condition is introduced. It is a model with the exceptional first service in each busy period. In particular, two special models are studied: one is a warm-up queue and the other is a cool-down queue. It can be proved that the waiting time of ordinary customers for the regular preemption model is stochastically smaller than the waiting time of the former model. On the other hand, it is stochastically larger than the waiting time of the latter model.     

A decomposition theorem and related results for the discriminatory processor sharing queue

In this paper, we study a discriminatory processor sharing queue with Poisson arrivals,K classes and general service times. For this queue, we prove a decomposition theorem for the conditional sojourn time of a tagged customer given the service times and class affiliations of the customers present in the system when the tagged customer arrives. We show that this conditional sojourn time can be decomposed inton+1 components if there aren customers present when the tagged customer arrives. Further, we show that thesen+1 components can be obtained as a solution of a system of non-linear integral equations. These results generalize known results about theM/G/1 egalitarian processor sharing queue.     

A Discrete-Time Single-Server Queueing System Under Multiple Vacations and Setup-Closedown Times

Abstract

This article concerns a Geo/G/1/∞ queueing system under multiple vacations and setup-closedown times. Specifically, the operation of the system is as follows. After each departure leaving an empty system, the server is deactivated during a closedown time. At the end of each closedown time, if at least a customer is present in the system, the server begins the service of the customers (is reactivated) without setup; however, if the system is completely empty, the server takes a vacation. At the end of each vacation, if there is at least a customer in the system, the server requires a startup time (is reactivated) before beginning the service of the customers; nevertheless, if there are not customers waiting in the system, the server takes another vacation. By applying the supplementary variable technique, the joint generating function of the server state and the system length together with the main performance measures are derived. We also study the length of the different busy periods of the server. The stationary distributions of the time spent waiting in the queue and in the system under the FCFS discipline are analysed too. Finally, a cost model with some numerical results is presented.     

Optimal priority queues: The simple discretionary priority rule

Summary The simple discretionary priority rule defines a point of discretion for every customer class up to which preemption by newly arriving customers of higher classes is possible. The paper derives the transient state results for the case with arbitrary numbers of customer classes and general service time distributions. The optimal point of discretion is determined for cost functions linear in the expected number of customers of each class present in the system.

---

Zusammenfassung Die einfache diskretionäre Prioritätsregel legt für jede Kundenklasse einen Punkt der Diskretion fest, bis zu welchem Verdrängung durch neuankommende Kunden höherer Klassen möglich ist. Ergebnisse für das zeitabhängige Verhalten von Prozessen mit beliebiger Anzahl von Kundenklassen und allgemeinverteilten Bedienzeiten werden abgeleitet. Der optimale Punkt der Diskretion wird bestimmt für eine Kostenfunktion linear im Erwartungswert der Anzahl der im System anwesenden Kunden einer jeden Klasse.

     

A mixed priority retrial queue with negative arrivals,unreliable server and multiple vacations

A retrial queue accepting two types of positive customers and negative arrivals, mixed priorities, unreliable server and multiple vacations is considered. In case of blocking the first type customers can be queued whereas the second type customers leave the system and try their luck again after a random time period. When a first type customer arrives during the service of a second type customer, he either pushes the customer in service in orbit (preemptive) or he joins the queue waiting to be served (non-preemptive). Moreover negative arrivals eliminate the customer in service and cause server’s abnormal breakdown, while in addition normal breakdowns may also occur. In both cases the server is sent immediately for repair. When, upon a service or repair completion, the server finds no first type customers waiting in queue remains idle and activates a timer. If timer expires before an arrival of a positive customer the server departs for multiple vacations. For such a system the stability conditions and the system state probabilities are investigated both in a transient and in a steady state. A stochastic decomposition result is also presented. Interesting applications are also discussed. Numerical results are finally obtained and used to investigate system performance.     

The MAP/(PH/PH)/1 queue with self-generation of priorities and non-preemptive service

Customers arriving according to a Markovian arrival process are served at a single server facility. Waiting customers generate priority at a constant rate γ$\gamma$; such a customer waits in a waiting space of capacity 1 if this waiting space is not already occupied by a priority generated customer; else it leaves the system. A customer in service will be completely served before the priority generated customer is taken for service (non-preemptive service discipline). Only one priority generated customer can wait at a time and a customer generating into priority at that time will have to leave the system in search of emergency service elsewhere. The service times of ordinary and priority generated customers follow PH-distributions. The matrix analytic method is used to compute the steady state distribution. Performance measures such as the probability of n consecutive services of priority generated customers, the probability of the same for ordinary customers, and the mean waiting time of a tagged customer are found by approximating them by their corresponding values in a truncated system. All these results are supported numerically.     

Strong approximations for priority queues; head-of-the-line-first discipline

In this paper, we obtain strong approximation theorems for a single server queue withr priority classes of customers and a head-of-the-line-first discipline. By using priority queues of preemptive-resume discipline as modified systems, we prove strong approximation theorems for the number of customers of each priority in the system at timet, the number of customers of each priority that have departed in the interval [0,t], the work load in service time of each priority class facing the server at timet, and the accumulated time in [0,t] during which there are neither customers of a given priority class nor customers of priority higher than that in the system.Research supported by the National Natural Science Foundation of China.