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.     

Waiting time distributions in the accumulating priority queue

We are interested in queues in which customers of different classes arrive to a service facility, and where performance targets are specified for each class. The manager of such a queue has the task of implementing a queueing discipline that results in the performance targets for all classes being met simultaneously. For the case where the performance targets are specified in terms of ratios of mean waiting times, as long ago as the 1960s, Kleinrock suggested a queueing discipline to ensure that the targets are achieved. He proposed that customers accumulate priority as a linear function of their time in the queue: the higher the urgency of the customer’s class, the greater the rate at which that customer accumulates priority. When the server becomes free, the customer (if any) with the highest accumulated priority at that time point is the one that is selected for service. Kleinrock called such a queue a time-dependent priority queue, but we shall refer to it as the accumulating priority queue. Recognising that the performance of many queues, particularly in the healthcare and human services sectors, is specified in terms of tails of waiting time distributions for customers of different classes, we revisit the accumulating priority queue to derive its waiting time distributions, rather than just the mean waiting times. We believe that some elements of our analysis, particularly the process that we call the maximum priority process, are of mathematical interest in their own right.     

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.     

An Iterative Algorithm for a Multiple Finite-source Queueing Model with Dynamic Priority Scheduling

A multiple finite source queueing model with a single server and dynamic, non-preemptive priority service discipline is studied in this paper. The times the customers spend at the corresponding sources are exponentially distributed. The service times of the customers can follow exponential, Erlang or hyperexponential probability density function. By using results published earlier and an extension of mean value analysis, an iterative algorithm was developed to obtain approximate values of the mean waiting times in queues for the priority classes. The mean number of waiting customers and the server utilization of each class are obtained using the result of this algorithm and Little's formula. The algorithm is preferable to the earlier method, because it does not increase in complexity as the number of customer classes increases.     

Analysis of M/G/1-Queues with Setup Times and Vacations under Six Different Service Disciplines

Single server M/G/1-queues with an infinite buffer are studied; these permit inclusion of server vacations and setup times. A service discipline determines the numbers of customers served in one cycle, that is, the time span between two vacation endings. Six service disciplines are investigated: the gated, limited, binomial, exhaustive, decrementing, and Bernoulli service disciplines. The performance of the system depends on three essential measures: the customer waiting time, the queue length, and the cycle duration. For each of the six service disciplines the distribution as well as the first and second moment of these three performance measures are computed. The results permit a detailed discussion of how the expected value of the performance measures depends on the arrival rate, the customer service time, the vacation time, and the setup time. Moreover, the six service disciplines are compared with respect to the first moments of the performance measures.     

Two competing discrete-time queues with priority

This paper considers a class of two discrete-time queues with infinite buffers that compete for a single server. Tasks requiring a deterministic amount of service time, arrive randomly to the queues and have to be served by the server. One of the queues has priority over the other in the sense that it always attempts to get the server, while the other queue attempts only randomly according to a rule that depends on how long the task at the head of the queue has been waiting in that position. The class considered is characterized by the fact that if both queues compete and attempt to get the server simultaneously, then they both fail and the server remains idle for a deterministic amount of time. For this class we derive the steady-state joint generating function of the state probabilities. The queueing system considered exhibits interesting behavior, as we demonstrate by an example.     

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.     

A single server queue with service interruptions

In this paper we characterize the queue-length distribution as well as the waiting time distribution of a single-server queue which is subject to service interruptions. Such queues arise naturally in computer and communication problems in which customers belong to different classes and share a common server under some complicated service discipline. In such queues, the viewpoint of a given class of customers is that the server is not available for providing service some of the time, because it is busy serving customers from a different class. A natural special case of these queues is the class of preemptive priority queues. In this paper, we consider arrivals according the Markovian Arrival Process (MAP) and the server is not available for service at certain times. The service times are assumed to have a general distribution. We provide numerical examples to show that our methods are computationally feasible. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

On multiple priority multi-server queues with impatience

We consider Markovian multi-server queues with two types of impatient customers: high- and low-priority ones. The first type of customer has a non-preemptive priority over the other type. After entering the queue, a customer will wait a random length of time for service to begin. If service has not begun by this time he or she will abandon and be lost. We consider two cases where the discipline of service within each customer type is first-come first-served (FCFS) or last-come first-served (LCFS). For each type of customer, we focus on various performance measures related to queueing delays: unconditional waiting times, and conditional waiting times given service and given abandonment. The analysis we develop holds also for a priority queue with mixed policies, that is, FCFS for the first type and LCFS for the second one, and vice versa. We explicitly derive the Laplace–Stieltjes transforms of the defined random variables. In addition we show how to extend the analysis to more than two customer types. Finally we compare FCFS and LCFS and gain insights through numerical experiments.     

A two-queue model with Bernoulli service schedule and switching times

In this paper, we present a detailed analysis of a cyclic-service queueing system consisting of two parallel queues, and a single server. The server serves the two queues with a Bernoulli service schedule described as follows. At the beginning of each visit to a queue, the server always serves a customer. At each epoch of service completion in the ith queue at which the queue is not empty, the server makes a random decision: with probability p_i, it serves the next customer; with probability 1-p_i, it switches to the other queue. The server takes switching times in its transition from one queue to the other. We derive the generating functions of the joint stationary queue-length distribution at service completion instants, by using the approach of the boundary value problem for complex variables. We also determine the Laplace-Stieltjes transforms of waiting time distributions for both queues, and obtain their mean waiting times. This revised version was published online in June 2006 with corrections to the Cover Date.     

Polling systems in heavy traffic: Exhaustiveness of service policies

We study the expected delay in cyclic polling models with general ‘branching-type’ service disciplines. For this class of models, which contains models with exhaustive and gated service as special cases, we obtain closed-form expressions for the expected delay under standard heavy-traffic scalings. We identify a single parameter associated with the service discipline at each queue, which we call the ‘exhaustiveness’. We show that the scaled expected delay figures depend on the service policies at the queues only through the exhaustiveness of each of the service disciplines. This implies that the influence of different service disciplines, but with the same exhaustiveness, on the expected delays at the queues becomes the same when the system reaches saturation. This observation leads to a new classification of the service disciplines. In addition, we show monotonicity of the scaled expected delays with respect to the exhaustiveness of the service disciplines. This induces a complete ordering in terms of efficiency of the service disciplines. The results also lead to new rules for optimization of the system performance with respect to the service disciplines at the queues. Further, the exact asymptotic results suggest simple expected waiting-time approximations for polling models in heavy traffic. Numerical experiments show that the accuracy of the approximations is excellent for practical heavy-traffic scenarios. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Invariance relations in single server queues with LCFS service discipline

This paper is concerned with single server queues having LCFS service discipline. We give a condition to hold an invariance relation between time and customer average queue length distributions in the queues. The relation is a generalization of that in an ordinary GI/M/1 queue. We compare the queue length distributions for different single server queues with finite waiting space under the same arrival process and service requirement distribution of customer and derive invariance relations among them.This research was supported in part by a grant from the Tokyo Metropolitan Government. The latter part of this paper was written while the author resided at the University of California, Berkeley.     

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.     

Stability of a two-queue cyclic polling system with BMAPs under gated service and state-dependent time-limited service disciplines

The stability of a cyclic polling system, with a single server and two infinite-buffer queues, is considered. Customers arrive at the two queues according to independent batch Markovian arrival processes. The first queue is served according to the gated service discipline, and the second queue is served according to a state-dependent time-limited service discipline with the preemptive repeat-different property. The state dependence is that, during each cycle, the predetermined limited time of the server’s visit to the second queue depends on the queue length of the first queue at the instant when the server last departed from the first queue. The mean of the predetermined limited time for the second queue either decreases or remains the same as the queue length of the first queue increases. Due to the two service disciplines, the customers in the first queue have higher service priority than the ones in the second queue, and the service fairness of the customers with different service priority levels is also considered. In addition, the switchover times for the server traveling between the two queues are considered, and their means are both positive as well as finite. First, based on two embedded Markov chains at the cycle beginning instants, the sufficient and necessary condition for the stability of the cyclic polling system is obtained. Then, the calculation methods for the variables related to the stability condition are given. Finally, the influence of some parameters on the stability condition of the cyclic polling system is analyzed. The results are useful for engineers not only checking whether the given cyclic polling system is stable, but also adjusting some parameters to make the system satisfy some requirements under the condition that the system is stable.     

Pseudo-conservation laws in cyclic-service systems with a class of limited service policies

This paper considers a cyclic-service system with a class of limited service policies that consists of exhaustive limited, gated limited and general decrementing policies. Under these policies, the number of customers served consecutively during a server visit is limited by a vector of integers. The major results in this paper are derivations of expected amount of work left in the queues at the server departures for these three policies. Exact expressions of weighted sum of mean waiting times, known as pseudo-conservation laws, are subsequently obtained. The conservation laws for this class of policies contain unknown boundary probabilities. We estimate these probabilities using corresponding server vacation models. Numerical results presented for the exhaustive limited policy are noted to be very accurate compared with simulation results. Moreover, we have obtained analytical bounds for the weighted sums. Finally, we present a conservation law with mixed service policies, and mean waiting times for symmetric systems.This work was completed while the author was in the Ph.D. program at Rensselaer Polytechnic Institute.This work was partially supported by the Center for Advanced Technologies of the New York State.     

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.     

Stability,monotonicity and invariant quantities in general polling systems

Consider a polling system withK1 queues and a single server that visits the queues in a cyclic order. The polling discipline in each queue is of general gated-type or exhaustive-type. We assume that in each queue the arrival times form a Poisson process, and that the service times, the walking times, as well as the set-up times form sequences of independent and identically distributed random variables. For such a system, we provide a sufficient condition under which the vector of queue lengths is stable. We treat several criteria for stability: the ergodicity of the process, the geometric ergodicity, and the geometric rate of convergence of the first moment. The ergodicity implies the weak convergence of station times, intervisit times and cycle times. Next, we show that the queue lengths, station times, intervisit times and cycle times are stochastically increasing in arrival rates, in service times, in walking times and in setup times. The stability conditions and the stochastic monotonicity results are extended to the polling systems with additional customer routing between the queues, as well as bulk and correlated arrivals. Finally, we prove that the mean cycle time, the mean intervisit time and the mean station times are invariant under general service disciplines and general stationary arrival and service processes.     

A single server queue with gated processor-sharing discipline

In this paper we consider a single server queue in which arrivals occur according to a Poisson process and each customer's service time is exponentially distributed. The server works according to the gated process-sharing discipline. In this discipline, the server provides service to a batch of at mostm customers at a time. Once a batch of customers begins service, no other waiting customer can receive service until all members of the batch have completed their service. For this queue, we derive performance characteristics, such as waiting time distribution, queue length distribution etc. For this queue, it is possible to obtain the mean conditional response time for a customer whose service time is known. This conditional response time is a nonlinear function (as opposed to the linear case for the ordinary processor-sharing queue). A special case of the queue (wherem=) has an interesting and unusual solution. For this special case, the size of the batch for service is a Markov chain whose steady state distribution can be explicitly written down. Apart from the contribution to the theory of Markov chains and queues, the model may be applicable to scheduling of computer and communication systems.