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.     

Factorization and Stochastic Decomposition Properties in Bulk Queues with Generalized Vacations

This paper considers a class of stationary batch-arrival, bulk-service queues with generalized vacations. The system consists of a single server and a waiting room of infinite capacity. Arrivals of customers follow a batch Markovian arrival process. The server is unavailable for occasional intervals of time called vacations, and when it is available, customers are served in groups of fixed size B. For this class of queues, we show that the vector probability generating function of the stationary queue length distribution is factored into two terms, one of which is the vector probability generating function of the conditional queue length distribution given that the server is on vacation. The special case of batch Poisson arrivals is carefully examined, and a new stochastic decomposition formula is derived for the stationary queue length distribution.AMS subject classification: 60K25, 90B22, 60K37     

Discrete time queues with delayed information

We study the behavior of a single-server discrete-time queue with batch arrivals, where the information on the queue length and possibly on service completions is delayed. Such a model describes situations arising in high speed telecommunication systems, where information arrives in messages, each comprising a variable number of fixed-length packets, and it takes one unit of time (a slot) to transmit a packet. Since it is not desirable to attempt service when the system may be empty, we study a model where we assume that service is attempted only if, given the information available to the server, it is certain that there are messages in the queue. We characterize the probability distribution of the number of messages in the queue under some general stationarity assumptions on the arrival process, when information on the queue size is delayedK slots, and derive explicit expressions of the PGF of the queue length for the case of i.i.d. batch arrivals and general independent service times. We further derive the PGF of the queue size when information onboth the queue length and service completion is delayedK=1 units of time. Finally, we extend the results to priority queues and show that when all messages are of unit length, thec rule remains optimal even in the case of delayed information.     

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.     

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.     

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.     

Conditional and unconditional distributions forM/G/1 type queues with server vacations

M/G/1 queues with server vacations have been studied extensively over the last two decades. Recent surveys by Boxma [3], Doshi [5] and Teghem [14] provide extensive summary of literature on this subject. More recently, Shanthikumar [11] has generalized some of the results toM/G/1 type queues in which the arrival pattern during the vacations may be different from that during the time the server is actually working. In particular, the queue length at the departure epoch is shown to decompose into two independent random variables, one of which is the queue length at the departure epoch (arrival epoch, steady state) in the correspondingM/G/1 queue without vacations. Such generalizations are important in the analysis of situations involving reneging, balking and finite buffer cyclic server queues. In this paper we consider models similar to the one in Shanthikumar [11] but use the work in the system as the starting point of our investigation. We analyze the busy and idle periods separately and get conditional distributions of work in the system, queue length and, in some cases, waiting time. We then remove the conditioning to get the steady state distributions. Besides deriving the new steady state results and conditional waiting time and queue length distributions, we demonstrate that the results of Boxma and Groenendijk [2] follow as special cases. We also provide an alternative approach to deriving Shanthikumar's [11] results for queue length at departure epochs.     

Insensitivity in discrete time queues with a moving server

Queues in which customers request service consisting of an integral number of segments and in which the server moves from service station to service station are of considerable interest to practitioners working on digital communications networks. In this paper, we present insensitivity theorems and thereby equilibrium distributions for two discrete time queueing models in which the server may change from one customer to another after completion of each segment of service. In the first model, exactly one segment of service is provided at each time point whether or not an arrival occurs, while in the second model, at most one arrival or service occurs at each time point. In each model, customers of typet request a service time which consists ofl segments in succession with probabilityb _t(l). Examples are given which illustrate the application of the theorems to round robin queues, to queues with a persistent server, and to queues in which server transition probabilities do not depend on the server's previous position. In addition, for models in which the probability that the server moves from one position to another depends only on the distance between the positions, an amalgamation procedure is proposed which gives an insensitive model on a coarse state space even though a queue may not be insensitive on the original state space. A model of Daduna and Schassberger is discussed in this context.This work was supported by the Australian Research Council.     

Geo/G/1 queues with disasters and general repair times

This paper discusses discrete-time single server Geo/G/1 queues that are subject to failure due to a disaster arrival. Upon a disaster arrival, all present customers leave the system. At a failure epoch, the server is turned off and the repair period immediately begins. The repair times are commonly distributed random variables. We derive the probability generating functions of the queue length distribution and the FCFS sojourn time distribution. Finally, some numerical examples are given.     

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.     

A two-queue,one-server model with priority for the longer queue

The queueing model studied consists of one server and two queues. Each queue has its own Poisson arrival stream and service time distribution. After a service completion, the server proceeds with a customer from the longer queue, if the queues are unequal; if the queues are equal, the server chooses with some probability a customer from one of the queues. The model is of practical interest in performance analysis, but also of theoretical interest because the functional equation to be solved has not yet been studied in the queueing literature. A basic analysis of this functional equation is presented. Some numerical results are given to assess the influence of the present service discipline. Some new properties of L.S. transforms of service time distributions are discussed in the appendix.Dr. T. Katayama has formulated the present problem and brought it to the author's attention during his visit in October/November 1984 to the NTT-Electr. Comm. Lab.'s Musashino, Tokyo 180.     

Limit non-stationary behavior of large closed queueing networks with bottlenecks

In this paper martingales methods are applied for analyzing limit non-stationary behavior of the queue length processes in closed Jackson queueing networks with a single class consisting of a large number of customers, a single infinite server queue, and a fixed number of single server queues with large state independent service rates. It is assumed that one of the single server nodes forms a bottleneck. For the non-bottleneck nodes we show that the queue length distribution at timet converges in generalized sense to the stationary distribution of the M/M/1 queue whose parameters explicitly depend ont. For the bottleneck node a diffusion approximation with reflection is proved in the moderate usage regime while fluid and Gaussian diffusion approximations are established for the heavy usage regime.     

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.     

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.     

有Bernoulli休假和可选服务的M/G/1重试反馈排队模型

考虑具有可选服务的M/G/1重试反馈排队模型,其中服务台有Bernoulli休假策略.系统外新到达的顾客服从参数为λ的泊松过程.重试区域只允许队首顾客重试,重试时间服从一般分布.所有的顾客都必须接受必选服务,然而只有其中部分接受可选服务.每个顾客每次被服务完成后可以离开系统或者返回到重试区域.服务台完成一次服务以后,可以休假也可以继续为顾客服务.通过嵌入马尔可夫链法证明了系统稳态的充要条件.利用补充变量的方法得到了稳态时系统和重试区域中队长分布.我们还得到了重试期间服务台处于空闲的概率,重试区域为空的概率以及其他各种指标.并证出在系统中服务员休假和服务台空闲的时间定义为广义休假情况下也具有随机分解特征.     

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

M/G/1/N vacation model with varying E-limited service discipline

We define and analyze anM/G/1/N vacation model that uses a service discipline that we call theE-limited with limit variation discipline. According to this discipline, the server provides service until either the system is emptied (i.e. exhausted) or a randomly chosen limit ofl customers has been served. The server then goes on a vacation before returning to service the queue again. The queue length distribution and the Laplace-Stieltjes transforms of the waiting time, busy period and cycle time distributions are found. Further, an expression for the mean waiting time is developed. Several previously analyzed service disciplines, including Bernoulli scheduling, nonexhaustive service and limited service, are special cases of the general varying limit discipline that is analyzed in this paper.     

On a Two-Queue Priority System with Impatience and its Application to a Call Center*

We consider an s-server priority system with a protected and an unprotected queue. The arrival rates at the queues and the service rate may depend on the number n of customers being in service or in the protected queue, but the service rate is assumed to be constant for n > s. As soon as any server is idle, a customer from the protected queue will be served according to the FCFS discipline. However, the customers in the protected queue are impatient. If the offered waiting time exceeds a random maximal waiting time I, then the customer leaves the protected queue after time I. If I is less than a given deterministic time, then he leaves the system, else he will be transferred by the system to the unprotected queue. The service of a customer from the unprotected queue will be started if the protected queue is empty and more than a given number of servers become idle. The model is a generalization of the many-server queue with impatient customers. The global balance conditions seem to have no explicit solution. However, the balance conditions for the density of the stationary state process for the subsystem of customers being in service or in the protected queue can be solved. This yields the stability conditions and the probabilities that precisely n customers are in service or in the protected queue. For obtaining performance measures for the unprotected queue, a system approximation based on fitting impatience intensities is constructed. The results are applied to the performance analysis of a call center with an integrated voice-mail-server.