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.     

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.     

Analysis of preemptive loss priority queues with preemption distance

In a queueing system with preemptive loss priority discipline, customers disappear from the system immediately when their service is preempted by the arrival of another customer with higher priority. Such a system can model a case in which old requests of low priority are not worthy of deferred service. This paper is concerned with preemptive loss priority queues in which customers of each priority class arrive in a Poisson process and have general service time distribution. The strict preemption in the existing model is extended by allowing the preemption distance parameterd such that arriving customers of only class 1 throughp — d can preempt the service of a customer of classp. We obtain closed-form expressions for the mean waiting time, sojourn time, and queue size from their distributions for each class, together with numerical examples. We also consider similar systems with server vacations.     

An M/G/1 retrial G-queue with preemptive resume priority and collisions subject to the server breakdowns and delayed repairs

We consider an M/G/1 retrial G-queue with preemptive resume priority and collisions under linear retrial policy subject to the server breakdowns and delayed repairs. A breakdown at the busy server is represented by the arrival of a negative customer which causes the customer being in service to be lost. The stability condition of the system is derived. Using generating function technique, the steady-state distributions of the server state and the number of customers in the orbit are obtained along with some interesting and important performance measures. The stochastic decomposition property is investigated. Further, some special cases of interest are discussed. Finally, numerical illustrations are provided.     

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.     

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

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

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.     

Optimal server scheduling in nonpreemptive finite-population queueing systems

We consider a finite-population queueing system with heterogeneous classes of customers and a single server. For the case of nonpreemptive service, we fully characterize the structure of the server's optimal service policy that minimizes the total average customer waiting costs. We show that the optimal service policy may never serve some classes of customers. For those classes that are served, we show that the optimal service policy is a simple static priority policy. We also derive sufficient conditions that determine the optimal priority sequence.     

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.     

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.     

Invariance of stationary probabilities of states for network of multiserver queues

A queueing network consisting of multiserver nodes with different sources of customers is considered. We investigate stationary probability distributions of network states. Their invariance with respect to the functional form of distributions of input and service processes is established under fixed expectations of these distributions and service discipline when any entering customer has a preemptive resume discipline.     

The $$MMAP\left[ K \right]/PH\left[ K \right]/1$$ queues with a last-come-first-served preemptive service discipline

This paper studies two queueing systems with a Markov arrival process with marked arrivals and PH-distribution service times for each type of customer. Customers (regardless of their types) are served on a last-come-first-served preemptive resume and repeat basis, respectively. The focus is on the stationary distribution of queue strings in the system and busy periods. Efficient algorithms are developed for computing the stationary distribution of queue strings, the mean numbers of customers served in a busy period, and the mean length of a busy period. Comparison is conducted numerically between performance measures of queueing systems with preemptive resume and preemptive repeat service disciplines. A counter-intuitive observation is that for a class of service time distributions, the repeat discipline performs better than the resume one. This revised version was published online in June 2006 with corrections to the Cover Date.     

An MAP/G/1 G-queues with preemptive resume and multiple vacations

In this paper, we consider an MAP/G/1 G-queues with possible preemptive resume service discipline and multiple vacations wherein the arrival process of negative customers is Markovian arrival process (MAP). The arrival of a negative customer may remove the customer being in service. The server leaves for a vacation as soon as the system empties and is allowed to take repeated (multiple) vacations. The service and vacation times are arbitrarily distributed. We obtain the queue length distributions with the method of supplementary variables, combined with the matrix-analytic method and censoring technique. We also obtain the mean of the busy period based on the renewal theory. Finally we provide expressions for a special case.     

Performance of service policies in a specialized service system with parallel servers

This paper considers a scheduling problem occurring in a specialized service system with parallel servers. In the system, customers are divided into the “ordinary” and “special” categories according to their service needs. Ordinary customers can be served by any server, while special customers can be served only by the flexible servers. We assume that the service time for any ordinary customer is the same and all special customers have another common service time. We analyze three classes of service policies used in practice, namely, policies with priority, policies without priority and mixed policies. The worst-case performance ratios are obtained for all of these service policies.     

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     

On the Two-Class M/M/1 System under Preemptive Resume and Impatience of the Prioritized Customers

The paper deals with the two-class priority M/M/1 system, where the prioritized class-1 customers are served under FCFS preemptive resume discipline and may become impatient during their waiting for service with generally distributed maximal waiting times. The class-2 customers have no impatience. The required mean service times may depend on the class of the customer. As the dynamics of class-1 customers are related to the well analyzed M/M/1+GI system, our aim is to derive characteristics for class-2 customers and for the whole system. The solution of the balance equations for the partial probability generating functions of the detailed system state process is given in terms of the weak solution of a family of boundary value problems for ordinary differential equations, where the latter can be solved explicitly only for particular distributions of the maximal waiting times. By means of this solution formulae for the joint occupancy distribution and for the sojourn and waiting times of class-2 customers are derived generalizing corresponding results recently obtained by Choi et al. in case of deterministic maximal waiting times. The latter case is dealt as an example in our paper.     

Stability of a priority queueing system with customer transfers

This paper is concerned with the stability of a preemptive priority queueing system with customer transfers. Conditions for the queueing system to be stable/unstable are found. An interesting result is that the stability/instability conditions are independent of the service rates of lower priority customers and the transfer rates.     

Mixed gated/exhaustive service in a polling model with priorities

In this paper we consider a single-server polling system with switch-over times. We introduce a new service discipline, mixed gated/exhaustive service, that can be used for queues with two types of customers: high and low priority customers. At the beginning of a visit of the server to such a queue, a gate is set behind all customers. High priority customers receive priority in the sense that they are always served before any low priority customers. But high priority customers have a second advantage over low priority customers. Low priority customers are served according to the gated service discipline, i.e. only customers standing in front of the gate are served during this visit. In contrast, high priority customers arriving during the visit period of the queue are allowed to pass the gate and all low priority customers before the gate. We study the cycle time distribution, the waiting time distributions for each customer type, the joint queue length distribution of all priority classes at all queues at polling epochs, and the steady-state marginal queue length distributions for each customer type. Through numerical examples we illustrate that the mixed gated/exhaustive service discipline can significantly decrease waiting times of high priority jobs. In many cases there is a minimal negative impact on the waiting times of low priority customers but, remarkably, it turns out that in polling systems with larger switch-over times there can be even a positive impact on the waiting times of low priority customers.     

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

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

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.