Waiting times of a finite-capacity multi-server model with non-preemptive priorities

We consider a non-preemptive head of the line multi-server priority model with finite capacity. The arrival processes of the different priority classes are independent Poisson processes. The service times are exponentially distributed and identical for the different priority classes. The model is described by a homogeneous continuous-time Markov chain. For the two-class model we derive an explicit representation of its steady-state distribution. Applying matrix-analytic methods we calculate the Laplace-Stieltjes Transform of the actual waiting time of each priority class of a p-class system.     

Waiting time in a multi-server cutoff-priority gueue, and its application to an urban ambulance service

We consider a priority queue in steady state with N servers, two classes of customers, and a cutoff service discipline. Low priority arrivals are "cut off" (refused immediate service) and placed in a queue whenever N1 or more servers are busy, in order to keep N-N1 servers free for high priority arrivals. A Poisson arrival process for each class, and a common exponential service rate, are assumed. Two models are considered: one where high priority customers queue for service and one where they are lost if all servers are busy at an arrival epoch. Results are obtained for the probability of n servers busy, the expected low priority waiting time, and (in the case where high priority customers do not queue) the complete low priority waiting time distribution. The results are applied to determine the number of ambulances required in an urban fleet which serves both emergency calls and low priority patients transfers.     

Class clustering destroys delay differentiation in priority queues

This paper considers a discrete-time priority queueing model with one server and two types (classes) of customers. Class-1 customers have absolute (service) priority over class-2 customers. New customer batches enter the system at the rate of one batch per slot, according to a general independent arrival process, i.e., the batch sizes (total numbers of arrivals) during consecutive time slots are i.i.d. random variables with arbitrary distribution. All customers entering the system during the same time slot (i.e., belonging to the same arrival batch) are of the same type, but customer types may change from slot to slot, i.e., from batch to batch. Specifically, the types of consecutive customer batches are correlated in a Markovian way, i.e., the probability that any batch of customers has type 1 or 2, respectively, depends on the type of the previous customer batch that has entered the system. Such an arrival model allows to vary not only the relative loads of both customer types in the arrival stream, but also the amount of correlation between the types of consecutive arrival batches. The results reveal that the amount of delay differentiation between the two customer classes that can be achieved by the priority mechanism strongly depends on the amount of such interclass correlation (or, class clustering) in the arrival stream. We believe that this phenomenon has been largely overlooked in the priority-scheduling literature.     

A Two Priority Queue with Crossover Feedback

This paper considers the delay distributions in a two-class non-preemptive priority queue with crossover feedback. Specifically, there are two priority classes, and the Poisson arrival process for each class can be subdivided into two groups: one group which only requires service at the priority level to which it arrives, and another group which requires subsequent service after it feeds back to the other queue. Our main result is the determination of explicit expressions for the distribution of delay until final service commences for each the four types of customers.     

Delay analysis of multiclass queues with correlated train arrivals and a hybrid priority/FIFO scheduling discipline

We analyze the delay experienced in a discrete-time priority queue with a train-arrival process. An infinite user population is considered. Each user occasionally sends packets in the form of trains: a variable number of fixed-length packets is generated and these packets arrive to the queue at the rate of one packet per slot. This is an adequate arrival process model for network traffic. Previous studies assumed two traffic classes, with one class getting priority over the other. We extend these studies to cope with a general number M of traffic classes that can be partitioned in an arbitrary number N of priority classes (1 ≤ N ≤ M). The lengths of the trains are traffic-class-dependent and generally distributed. To cope with the resulting general model, an (M × )∞-sized Markovian state vector is introduced. By using probability generating functions, moments and tail probabilities of the steady-state packet delays of all traffic classes are calculated. Since this study can be useful in deciding how to partition traffic classes in priority classes, we demonstrate the impact of this partitioning for some specific cases.     

Analysis of a finite buffer model with two servers and two nonpreemptive priority classes

In this paper, we analyze a finite buffer queueing model with two servers and two nonpreemptive priority service classes. The arrival streams are independent Poisson processes, and the service times of the two classes are exponentially distributed with different means. One of the two servers is reserved exclusively for one class with high priority and the other server serves the two classes according to a nonpreemptive priority service schedule. For the model, we describe its dynamic behavior by a four-dimensional continuous-time Markov process. Applying recursive approaches we present the explicit representation for the steady-state distribution of this Markov process. Then, we calculate the Laplace–Stieltjes Transform and the steady-state distribution of the actual waiting times of two classes of customers. We also give some numerical comparison results with other queueing models.     

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.     

Using different response-time requirements to smooth time-varying demand for service

Many service systems have demand that varies significantly by time of day, making it costly to provide sufficient capacity to be able to respond very quickly to each service request. Fortunately, however, different service requests often have very different response-time requirements. Some service requests may need immediate response, while others can tolerate substantial delays. Thus it is often possible to smooth demand by partitioning the service requests into separate priority classes according to their response-time requirements. Classes with more stringent performance requirements are given higher priority for service. Lower capacity may be required if lower-priority-class demand can be met during off-peak periods. We show how the priority classes can be defined and the resulting required fixed capacity can be determined, directly accounting for the time-dependent behavior. For this purpose, we exploit relatively simple analytical models, in particular, M_t/G/∞ and deterministic offered-load models. The analysis also provides an estimate of the capacity savings that can be obtained from partitioning time-varying demand into priority classes.     

Software rejuvenation and resource reservation policies for optimizing server resource availability using cyclic nonhomogeneous Markov chains

Software rejuvenation is modeled in a client–server system, which provides resources to priority classes of users. To assure availability, resource reservation policies are adopted for the higher priority classes. In addition software rejuvenation is proposed to optimize resource availability. The system is modeled by a cyclic nonhomogeneous Markov chain to capture the variation of the arrival and service rates during a day period. An optimization problem is solved based on a similar previous work and given the optimal resource reservation policy obtained by its solution, rejuvenation is performed and the optimal rejuvenation policy is determined. As a measure of resource availability the blocking probability of each priority class is used. Performability indicators expressing the total cost are also derived, with respect to the optimal resource reservation and optimal rejuvenation policies, to examine whether rejuvenation benefits the system in terms of cost. To derive the blocking probabilities, the limiting probability distribution is computed using explicit generalized approximate inverse preconditioning for solving efficiently sparse linear systems of algebraic equations. Copyright © 2012 John Wiley & Sons, Ltd.     

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.     

Analysis of a two-class single-server discrete-time FCFS queue: the effect of interclass correlation

In this paper, we study a discrete-time queueing system with one server and two classes of customers. Customers enter the system according to a general independent arrival process. The classes of consecutive customers, however, are correlated in a Markovian way. The system uses a “global FCFS” service discipline, i.e., all arriving customers are accommodated in one single FCFS queue, regardless of their classes. The service-time distribution of the customers is general but class-dependent, and therefore, the exact order in which the customers of both classes succeed each other in the arrival stream is important, which is reflected by the complexity of the system content and waiting time analysis presented in this paper. In particular, a detailed waiting time analysis of this kind of multi-class system has not yet been published, and is considered to be one of the main novelties by the authors. In addition to that, a major aim of the paper is to estimate the impact of interclass correlation in the arrival stream on the total number of customers in the system, and the customer delay. The results reveal that the system can exhibit two different classes of stochastic equilibrium: a “strong” equilibrium where both customer classes give rise to stable behavior individually, and a “compensated” equilibrium where one customer type creates overload.     

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.     

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.     

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 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.     

Dynamic server allocation for unstable queueing networks with flexible servers

This paper is concerned with the dynamic assignment of servers to tasks in queueing networks where demand may exceed the capacity for service. The objective is to maximize the system throughput. We use fluid limit analysis to show that several quantities of interest, namely the maximum possible throughput, the maximum throughput for a given arrival rate, the minimum arrival rate that will yield a desired feasible throughput, and the optimal allocations of servers to classes for a given arrival rate and desired throughput, can be computed by solving linear programming problems. We develop generalized round-robin policies for assigning servers to classes for a given arrival rate and desired throughput, and show that our policies achieve the desired throughput as long as this throughput is feasible for the arrival rate. We conclude with numerical examples that illustrate the points discussed and provide insights into the system behavior when the arrival rate deviates from the one the system is designed for.     

Stability of Earliest-Due-Date,First-Served Queueing Networks

We study multiclass queueing networks with the earliest-due-date, first-served (EDDFS) discipline. For these networks, the service priority of a customer is determined, upon its arrival in the network, by an assigned random due date. First-in-system, first-out queueing networks, where a customer's priority is given by its arrival time in the network, are a special case. Using fluid models, we show that EDDFS queueing networks, without preemption, are stable whenever the traffic intensity satisfies _j <1 for each station j.     

带负顾客和强占优先权的不耐烦信元排队

考虑带有负顾客的两类信元的强占优先权M/M/1排队系统.两类信元及负顾客的到达过程均为泊松过程.两类信元到达后分别在各自有限的缓冲器内排队,第一类信元较第二类信元有强占优先权,同时第一类信元是不耐烦的.负顾客一对一抵消队尾的第一类信元(若有),若系统中无第一类信元,到达的负顾客就自动消失.负顾客不接受服务.采用矩阵分析的方法得到了两类信元各自的稳态分布,并作了相应的性能分析.     

New differentiated consensus problem with topology cost constraints

A new differentiated consensus problem is studied. The problem is, given a system with multiple classes, consensus is targeted for each class and the consensus values can be different among the classes. Specifically, differentiated consensus is studied in a distributed stochastic network of nodes (or agents), where tasks assigned with different priorities are serviced. The network is assumed to have a switching topology and involves noises, delays in measurements, and topology cost constraints. The goal is to reach a balanced load (i.e., consensus) across the network and, at the same time, to satisfy the topology cost constraint, both for each priority class. A new control protocol is proposed, with which the network resources are allocated in a randomized way with a probability assigned to each priority class. It is shown that the control protocol meets the topology cost constraint and can be used to reach an approximate consensus for each of the priority classes in the network.     

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.