Higher order approximations for tandem queueing networks

In this paper a higher order approximation for single server queues and tandem queueing networks is proposed and studied. Different from the most popular two-moment based approximations in the literature, the higher order approximation uses the higher moments of the interarrival and service distributions in evaluating the performance measures for queueing networks. It is built upon the MacLaurin series analysis, a method that is recently developed to analyze single-node queues, along with the idea of decomposition using higher orders of the moments matched to a distribution. The approximation is computationally flexible in that it can use as many moments of the interarrival and service distributions as desired and produce the corresponding moments for the waiting and interdeparture times. Therefore it can also be used to study several interesting issues that arise in the study of queueing network approximations, such as the effects of higher moments and correlations. Numerical results for single server queues and tandem queueing networks show that this approximation is better than the two-moment based approximations in most cases.     

A Poisson–Charlier approximation for nonstationary queues

In this paper, we develop a new approximation for nonstationary multiserver queues with abandonment. Our method uses the Poisson–Charlier polynomials, which are a discrete orthogonal polynomial sequence that is orthogonal with respect to the Poisson distribution. We show that by appealing to the Poisson–Charlier polynomials that we can estimate the mean, variance, and probability of delay of our nonstationary queueing system with good accuracy. Lastly, we provide a numerical example that illustrates that our approximations are effective.     

Effect of global FCFS and relative load distribution in two-class queues with dedicated servers

In this paper, we investigate multi-class multi-server queueing systems with global FCFS policy, i.e., where customers requiring different types of service—provided by distinct servers—are accommodated in one common FCFS queue. In such scenarios, customers of one class (i.e., requiring a given type of service) may be hindered by customers of other classes. The purpose of this paper is twofold: to gain (qualitative and quantitative) insight into the impact of (i) the global FCFS policy and (ii) the relative distribution of the load amongst the customer classes, on the system performance. We therefore develop and analyze an appropriate discrete-time queueing model with general independent arrivals, two (independent) customer classes and two class-specific servers. We study the stability of the system and derive the system-content distribution at random slot boundaries; we also obtain mean values of the system content and the customer delay, both globally and for each class individually. We then extensively compare these results with those obtained for an analogous system without global FCFS policy (i.e., with individual queues for the two servers). We demonstrate that global FCFS, as well as the relative distribution of the load over the two customer classes, may have a major impact on the system performance.     

Transient and asymptotic behavior of synchronization processes in assembly-like queues

This paper analyzes the synchronization process of an assembly-like queueing system in which two distinct types of items/customers arrive at separate buffers, according to independent Poisson processes, so as to be synchronized into pairs at a synchronization node. Once a pair is synchronized it then queues up for service from a single server on a first-in-first-out basis as pairs. It is assumed that the service times of pairs are exponentially distributed and that the system has infinite capacity. Despite their practical significance, such queueing systems have not been adequately treated in the literature due to their transience or null recurrence. We first investigate the transient and asymptotic properties of the synchronization process’ first two moments, both analytically and numerically. Motivated by the observed asymptotic behavior, we then propose an M/M/1 approximation to describe the behavior of such assembly-like queueing systems. Finally, a numerical study of the proposed approximation reveals that it performs sufficiently well for practical applications.     

A Markovian single server with upstream job and downstream demand arrival stream

In this paper we consider a Markovian single server system which processes items arriving from an upstream region (as usual in queueing systems) and is controlled by a demand arrival stream for finished items from a downstream area. A finite storage is available at the server to store finished items not immediately needed in the downstream area. The system considered corresponds to an assembly-like queue with two input streams. The system is stable in a strict sense only if all queues are finite, i.e., both random processes are synchronized via blocking. This notion leads to a complementary system with a very similar state space which is a pair of Markovian single servers with synchronous arrivals. In the mathematical analysis the main focus is on the state probabilities and expectation of minimum and maximum of the two input queues. This revised version was published online in June 2006 with corrections to the Cover Date.     

Delay Distribution of (Im)Patient Customers in a Discrete Time D-MAP/PH/1 Queue with Age-Dependent Service Times

This paper presents an algorithmic procedure to calculate the delay distribution of (im)patient customers in a discrete time D-MAP/PH/1 queue, where the service time distribution of a customer depends on his waiting time. We consider three different situations: impatient customers in the waiting room, impatient customers in the system, that is, if a customer has been in the waiting room, respectively, in the system for a time units it leaves the waiting room, respectively, the system. In the third situation, all customers are patient – that is, they only leave the system after completing service. In all three situations the service time of a customer depends upon the time he has spent in the waiting room. As opposed to the general approach in many queueing systems, we calculate the delay distribution, using matrix analytic methods, without obtaining the steady state probabilities of the queue length. The trick used in this paper, which was also applied by Van Houdt and Blondia [J. Appl. Probab., Vol. 39, No. 1 (2002) pp. 213–222], is to keep track of the age of the customer in service, while remembering the D-MAP state immediately after the customer in service arrived. Possible extentions of this method to more general queues and numerical examples that demonstrate the strength of the algorithm are also included.     

Modeling traffic flow interrupted by incidents

A steady-state M/M/c queueing system under batch service interruptions is introduced to model the traffic flow on a roadway link subject to incidents. When a traffic incident happens, either all lanes or part of a lane is closed to the traffic. As such, we model these interruptions either as complete service disruptions where none of the servers work or partial failures where servers work at a reduced service rate. We analyze this system in steady-state and present a scheme to obtain the stationary number of vehicles on a link. For those links with large c values, the closed-form solution of M/M/∞ queues under batch service interruptions can be used as an approximation. We present simulation results that show the validity of the queueing models in the computation of average travel times.     

A disaster queue with Markovian arrivals and impatient customers

We consider a single server queueing system in which arrivals occur according to a Markovian arrival process. The system is subject to disastrous failures at which times all customers in the system are lost. Arrivals occurring during the time the system undergoes repair are stored in a buffer of finite capacity. These customers can become impatient after waiting a random amount of time and leave the system. However, these customers do not become impatient once the system becomes operable. When the system is operable, there is no limit on the number of customers who can be admitted. The structure of this queueing model is of GI/M/1-type that has been extensively studied by Neuts and others. The model is analyzed in steady state by exploiting the special nature of this type queueing model. A number of useful performance measures along with some illustrative examples are reported.     

On the stationary distribution of queue lengths in a multi-class priority queueing system with customer transfers

This paper deals with a multi-class priority queueing system with customer transfers that occur only from lower priority queues to higher priority queues. Conditions for the queueing system to be stable/unstable are obtained. An auxiliary queueing system is introduced, for which an explicit product-form solution is found for the stationary distribution of queue lengths. Sample path relationships between the queue lengths in the original queueing system and the auxiliary queueing system are obtained, which lead to bounds on the stationary distribution of the queue lengths in the original queueing system. Using matrix-analytic methods, it is shown that the tail asymptotics of the stationary distribution is exact geometric, if the queue with the highest priority is overloaded.      

An approximate analysis of a cyclic server queue with limited service and reservations

In this paper, we examine a queueing problem motivated by the pipeline polling protocol in satellite communications. The model is an extension of the cyclic queueing system withM-limited service. In this service mechanism, each queue, after receiving service on cyclej, makes a reservation for its service requirement in cyclej + 1. The main contribution to queueing theory is that we propose an approximation for the queue length and sojourn-time distributions for this discipline. Most approximate studies on cyclic queues, which have been considered before, examine the means only. Our method is an iterative one, which we prove to be convergent by using stochastic dominance arguments. We examine the performance of our algorithm by comparing it to simulations and show that the results are very good.     

Characterizing the departure process of a single server queue from the embedded Markov renewal process at departures

In the literature, performance analyses of numerous single server queues are done by analyzing the embedded Markov renewal processes at departures. In this paper, we characterize the departure processes for a large class of such queueing systems. Results obtained include the Laplace–Stieltjes transform (LST) of the stationary distribution function of interdeparture times and recursive formula for {_cn ≡ the covariance between interdeparture times of lag n}. Departure processes of queues are difficult to characterize and for queues other than M/G/1 this is the first time that {_cn} can be computed through an explicit recursive formula. With this formula, we can calculate {_cn} very quickly, which provides deeper insight into the correlation structure of the departure process compared to the previous research. Numerical examples show that increasing server irregularity (i.e., the randomness of the service time distribution) destroys the short-range dependence of interdeparture times, while increasing system load strengthens both the short-range and the long-range dependence of interdeparture times. These findings show that the correlation structure of the departure process is greatly affected by server regularity and system load. Our results can also be applied to the performance analysis of a series of queues. We give an application to the performance analysis of a series of queues, and the results appear to be accurate. This revised version was published online in June 2006 with corrections to the Cover Date.     

An approximation of known accuracy for single server queues with inhomogeneous arrival rate and continuous service time distribution

A practical method for obtaining approximate results for single server queues with inhomogeneous queues and continuous service time distribution is presented. The method is based on a discrete approximation to the continuous service time distribution. Exact results can be obtained for the corresponding queueing system with discrete service time distribution. These results are then corrected, and the likely accuracy of the corrected results is estimated. Four measures of performance are considered, idleness probability, mean and variance of number of customers in the system and virtual waiting time.     

Nonstationary analysis of the loss queue and of queueing networks of loss queues

We present an iterative scheme based on the fixed-point approximation method, for the numerical calculation of the time-dependent mean number of customers and blocking probability functions in a nonstationary queueing network with multi-rate loss queues. We first show how the proposed method can be used to analyze a single-class, multi-class, and multi-rate nonstationary loss queue. Subsequently, the proposed method is extended to the analysis of a nonstationary queueing network of multi-rate loss queues. Comparisons with exact and simulation results showed that the results are consistently close to the exact results and they are always within simulation confidence intervals.     

Marginal queue length approximations for a two-layered network with correlated queues

We consider an extension of the classical machine-repair model, where we assume that the machines, apart from receiving service from the repairman, also serve queues of products. The extended model can be viewed as a layered queueing network, where the first layer consists of the queues of products and the second layer is the ordinary machine-repair model. As the repair time of one machine may affect the time the other machine is not able to process products, the downtimes of the machines are correlated. This correlation leads to dependence between the queues of products in the first layer. Analysis of these queue length distributions is hard, as the exact dependence structure for the downtimes, or the queue lengths, is not known. Therefore, we obtain an approximation for the complete marginal queue length distribution of any queue in the first layer, by viewing such a queue as a single server queue with correlated server downtimes. Under an explicit assumption on the form of the downtime dependence, we obtain exact results for the queue length distribution for that single server queue. We use these exact results to approximate the machine-repair model. We do so by computing the downtime correlation for the latter model and by subsequently using this information to fine-tune the parameters we introduced to the single server queue. As a result, we immediately obtain an approximation for the queue length distributions of products in the machine-repair model, which we show to be highly accurate by extensive numerical experiments.     

Transient flows in queueing systems via closure approximations

We present a method for obtaining approximations to the distribution of flow times of customers in arbitrary queueing systems. We first propose approximations for uni-variate and multi-variate distributions of non-negative random variables. Then using a closure approximation, we show that the distribution of flow time can be calculated recursively. Computational results for the single server, multi-server and tandem queues are encouraging, with less than 5%average error in the mean flow time in most cases. The average error in the variance of flow times is found to be less than 10% for the more regular distributions.     

Queue-length balance equations in multiclass multiserver queues and their generalizations

A classical result for the steady-state queue-length distribution of single-class queueing systems is the following: The distribution of the queue length just before an arrival epoch equals the distribution of the queue length just after a departure epoch. The constraint for this result to be valid is that arrivals, and also service completions, with probability one occur individually, i.e., not in batches. We show that it is easy to write down somewhat similar balance equations for multidimensional queue-length processes for a quite general network of multiclass multiserver queues. We formally derive those balance equations under a general framework. They are called distributional relationships and are obtained for any external arrival process and state-dependent routing as long as certain stationarity conditions are satisfied and external arrivals and service completions do not simultaneously occur. We demonstrate the use of these balance equations, in combination with PASTA, by (1) providing very simple derivations of some known results for polling systems and (2) obtaining new results for some queueing systems with priorities. We also extend the distributional relationships for a nonstationary framework.     

Monotonicity properties in various retrial queues and their applications

We consider several multi-server retrial queueing models with exponential retrial times that arise in the literature of retrial queues. The effect of retrial rates on the behavior of the queue length process is investigated via sample path approach. We show that the number of customers in orbit and in the system as a whole are monotonically changed if the retrial rates in one system are bounded by the rates in second one. The monotonicity results are applied to show the convergence of generalized truncated systems that have been widely used for approximating the stationary queue length distribution in retrial queues. AMS subject classifications: Primary 60K25     

A finite capacity multi-queueing system with priorities and with repeated server vacations

In this paper, we study an M/G/1 multi-queueing system consisting ofM finite capacity queues, at which customers arrive according to independent Poisson processes. The customers require service times according to a queue-dependent general distribution. Each queue has a different priority. The queues are attended by a single server according to their priority and are served in a non-preemptive way. If there are no customers present, the server takes repeated vacations. The length of each vacation is a random variable with a general distribution function. We derive steady state formulas for the queue length distribution and the Laplace transform of the queueing time distribution for each queue.     

An Alternative Model for Queueing Systems with Single Arrivals,Batch Services and Customer Coalescence

In this paper we consider a queueing system with single arrivals, batch services and customer coalescence and we use it as a building block for constructing queueing networks that incorporate such characteristics. Chao et al. (1996) considered a similar model and they proved that it possesses a geometric product form stationary distribution, under the assumption that if the number of units present at a service completion epoch is less than the required number of units, then all the units coalesce into an incomplete (defective) batch which leaves the system. We drop this assumption and we study a model without incomplete batches. We prove that the stationary distribution of such a queue has a nearly geometric form. Using quasi-reversibility arguments we construct a network model with such queues which provides relevant bounds and approximations for the behaviour of assembly processes. Several issues about the validity of these bounds and approximations are also discussed.