The finite capacity multi-server queue with inhomogeneous arrival rate and discrete service time distribution — and its application to continuous service time problems

The finite capacity multi-server queueing model with inhomogeneous arrival rate and discrete service time distribution is developed. The system is formulated as an inhomogeneous Markov chain in discrete time. An algorithm is described to solve the model numerically. A method is then proposed for using this model to approximate the time dependent behaviour of multi-server queues with inhomogeneous arrival rate and continuous service time distribution. Empirical results are presented to show that this approximation will produce results that are accurate enough for most practical purposes.     

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.     

Queue Length Distribution in a FIFO Single-Server Queue with Multiple Arrival Streams Having Different Service Time Distributions

This paper considers the queue length distribution in a class of FIFO single-server queues with (possibly correlated) multiple arrival streams, where the service time distribution of customers may be different for different streams. It is widely recognized that the queue length distribution in a FIFO queue with multiple non-Poissonian arrival streams having different service time distributions is very hard to analyze, since we have to keep track of the complete order of customers in the queue to describe the queue length dynamics. In this paper, we provide an alternative way to solve the problem for a class of such queues, where arrival streams are governed by a finite-state Markov chain. We characterize the joint probability generating function of the stationary queue length distribution, by considering the joint distribution of the number of customers arriving from each stream during the stationary attained waiting time. Further we provide recursion formulas to compute the stationary joint queue length distribution and the stationary distribution representing from which stream each customer in the queue arrived.     

Distributional Form of Little's Law for FIFO Queues with Multiple Markovian Arrival Streams and Its Application to Queues with Vacations

This paper considers stationary queues with multiple arrival streams governed by an irreducible Markov chain. In a very general setting, we first show an invariance relationship between the time-average joint queue length distribution and the customer-average joint queue length distribution at departures. Based on this invariance relationship, we provide a distributional form of Little's law for FIFO queues with simple arrivals (i.e., the superposed arrival process has the orderliness property). Note that this law relates the time-average joint queue length distribution with the stationary sojourn time distributions of customers from respective arrival streams. As an application of the law, we consider two variants of FIFO queues with vacations, where the service time distribution of customers from each arrival stream is assumed to be general and service time distributions of customers may be different for different arrival streams. For each queue, the stationary waiting time distribution of customers from each arrival stream is first examined, and then applying the Little's law, we obtain an equation which the probability generating function of the joint queue length distribution satisfies. Further, based on this equation, we provide a way to construct a numerically feasible recursion to compute the joint queue length distribution.     

The analysis of batch sojourn-times in polling systems

We consider a cyclic polling system with general service times, general switch-over times, and simultaneous batch arrivals. This means that at an arrival epoch, a batch of customers may arrive simultaneously at the different queues of the system. For the exhaustive service discipline, we study the batch sojourn-time, which is defined as the time from an arrival epoch until service completion of the last customer in the batch. We obtain exact expressions for the Laplace–Stieltjes transform of the steady-state batch sojourn-time distribution, which can be used to determine the moments of the batch sojourn-time and, in particular, its mean. However, we also provide an alternative, more efficient way to determine the mean batch sojourn-time, using mean value analysis. We briefly show how our framework can be applied to other service disciplines: locally gated and globally gated. Finally, we compare the batch sojourn-times for different service disciplines in several numerical examples. Our results show that the best performing service discipline, in terms of minimizing the batch sojourn-time, depends on system characteristics.     

On the distribution of the number stranded in bulk-arrival, bulk-service queues of the M/G/1 form

Bulk-arrival queues with single servers that provide bulk service are widespread in the real world, e.g., elevators in buildings, people-movers in amusement parks, air-cargo delivery planes, and automated guided vehicles. Much of the literature on this topic focusses on the development of the theory for waiting time and number in such queues. We develop the theory for the number stranded, i.e., the number of customers left behind after each service, in queues of the M/G/1 form, where there is single server, the arrival process is Poisson, the service is of a bulk nature, and the service time is a random variable. For the homogenous Poisson case, in our model the service time can have any given distribution. For the non-homogenous Poisson arrivals, due to a technicality, we assume that the service time is a discrete random variable. Our analysis is not only useful for performance analysis of bulk queues but also in designing server capacity when the aim is to reduce the frequency of stranding. Past attempts in the literature to study this problem have been hindered by the use of Laplace transforms, which pose severe numerical difficulties. Our approach is based on using a discrete-time Markov chain, which bypasses the need for Laplace transforms and is numerically tractable. We perform an extensive numerical analysis of our models to demonstrate their usefulness. To the best of our knowledge, this is the first attempt in the literature to study this problem in a comprehensive manner providing numerical solutions.     

The Setting and Optimization of Quick Queue

Considering that customer arrival is a peak and post-peak period, we establish a fluid model of queuing behavior. In order to reduce the sum of waiting time of customers, we study the method of the setting and optimization of quick queue in a random service system. Under the premise of the total number of service equipment, we construct two queuing models, with one including only common queues and the other including both common and quick queues and propose the formulas for calculating the sum of the waiting time of the two models. In the two cases of peak and post-peak periods, we analyze the effect of quick queue on service system performance. And we present the method for calculating the number of quick queues that gives the best overall system performance. Taking the quick queue setting and optimization of the supermarket service system as an example, we verify the validity of the proposed method, which indicates the reference value of the method to the management practice.     

A single-server batch arrival queue with returning customers

We consider a new class of batch arrival retrial queues. By contrast to standard batch arrival retrial queues we assume if a batch of primary customers arrives into the system and the server is free then one of the customers starts to be served and the others join the queue and then are served according to some discipline. With the help of Lyapunov functions we have obtained a necessary and sufficient condition for ergodicity of embedded Markov chain and the joint distribution of the number of customers in the queue and the number of customers in the orbit in steady state. We also have suggested an approximate method of analysis based on the corresponding model with losses.     

Single-Server Queues with Markov-Modulated Arrivals and Service Speed

This paper considers single-server queues with several customer classes. Arrivals of customers are governed by the underlying continuous-time Markov chain with finite states. The distribution of the amount of work brought into the system on arrival is assumed to be general, which may differ with different classes. Further, the service speed depends on the state of the underlying Markov chain. We first show that given such a queue, we can construct the corresponding new queue with constant service speed by means of a change of time scale, and the time-average quantities of interest in the original queue are given in terms of those in the new queue. Next we characterize the joint distribution of the length of a busy period and the number of customers served during the busy period in the original queue. Finally, assuming the FIFO service discipline, we derive the Laplace–Stieltjes transform of the actual waiting time distribution in the original queue.     

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.     

The MM CPP/GE/c G-Queue: Sojourn Time Distribution

We obtain the sojourn time probability distribution function at equilibrium for a Markov modulated, multi-server, single queue with generalised exponential (GE) service time distribution and compound Poisson arrivals of both positive and negative customers. Such arrival processes can model both burstiness and correlated traffic and are well suited to models of ATM and other telecommunication networks. Negative customers remove (ordinary) customers in the queue and are similarly correlated and bursty. We consider both the cases where negative customers remove positive customers from the front and the end of the queue and, in the latter case, where a customer currently being served can and cannot be killed by a negative customer. These cases can model an unreliable server or load balancing respectively. The results are obtained as Laplace transforms and can be inverted numerically. The MM CPP/GE/c G-Queue therefore holds the promise of being a viable building block for the analysis of queues and queueing networks with bursty, correlated traffic, incorporating load balancing and node-failures, since the equilibrium behaviour of both queue lengths and response times can be determined in a tractable way.     

Exact Analysis of the State-Dependent Polling Model

We consider a polling model in which a number of queues are served, in cyclic order, by a single server. Each queue has its own distinct Poisson arrival stream, service time, and switchover time (the server's travel time from that queue to the next) distribution. A setup time is incurred if the polled queue has one or more customers present. This is the polling model with State-Dependent service (the SD model). The SD model is inherently complex; hence, it has often been approximated by the much simpler model with State-Independent service (the SI model) in which the server always sets up for a service at the polled queue, regardless of whether it has customers or not. We provide an exact analysis of the SD model and obtain the probability generating function of the joint queue length distribution at a polling epoch, from which the moments of the waiting times at the various queues are obtained. A number of numerical examples are presented, to reveal conditions under which the SD model could perform worse than the corresponding SI model or, alternately, conditions under which the SD model performs better than a corresponding model in which all setup times are zero. We also present expressions for a variant of the SD model, namely, the SD model with a patient server.     

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.     

Approximate analysis of exponential tandem queues with blocking

In this paper, an approximate method for the analysis of open networks of queues in tandem and with blocking is proposed. The network consists of M single server queuing stations with exogenous Poisson arrival processes and exponentially distributed service times. The analysis is based on the method of decomposition where the total network is broken down into queues which are analyzed as M/C₂/1/N queues assuming Poisson arrival and departure processes to find the steady-state probabilities of the number of customers at each station. The procudure reduces the problem to a number of elementary operations which can be performed efficiently with the aid of a computer. We also compare different definitions of blocking. Numerical results are given to demonstrate the accuracy of the new method.     

Tandem queueing system with infinite and finite intermediate buffers and generalized phase-type service time distribution

A tandem queueing system with infinite and finite intermediate buffers, heterogeneous customers and generalized phase-type service time distribution at the second stage is investigated. The first stage of the tandem has a finite number of servers without buffer. The second stage consists of an infinite and a finite buffers and a finite number of servers. The arrival flow of customers is described by a Marked Markovian arrival process. Type 1 customers arrive to the first stage while type 2 customers arrive to the second stage directly. The service time at the first stage has an exponential distribution. The service times of type 1 and type 2 customers at the second stage have a phase-type distribution with different parameters. During a waiting period in the intermediate buffer, type 1 customers can be impatient and leave the system. The ergodicity condition and the steady-state distribution of the system states are analyzed. Some key performance measures are calculated. The Laplace–Stieltjes transform of the sojourn time distribution of type 2 customers is derived. Numerical examples are presented.     

具有位相型修理的离散时间可修排队系统

本文研究了具有一般独立输入，位相型修理的离散时间可修排队系统，假定服务台对顾客的服务时间和服务台寿命服从几何分布，运用矩阵解析方法我们给出系统嵌入在到达时刻的稳态队长分布和等待时间分布，并证明这些分布均为离散位相型分布．我们也得到在广义服务时间内服务台发生故障次数的分布，证明它服从一个修正的几何分布．我们对离散时间可修排队与连续时间可修排队进行了比较，说明这两种排队系统在一些性能指标方面的区别之处．最后我们通过一些数值例子说明在这类系统中顾客的到达过程、服务时间和服务台的故障率之间的关系．     

Two-parameter heavy-traffic limits for infinite-server queues with dependent service times

This paper is a sequel to our 2010 paper in this journal in which we established heavy-traffic limits for two-parameter processes in infinite-server queues with an arrival process that satisfies an FCLT and i.i.d. service times with a general distribution. The arrival process can have a time-varying arrival rate. In particular, an FWLLN and an FCLT were established for the two-parameter process describing the number of customers in the system at time t that have been so for a duration y. The present paper extends the previous results to cover the case in which the successive service times are weakly dependent. The deterministic fluid limit obtained from the new FWLLN is unaffected by the dependence, whereas the Gaussian process limit (random field) obtained from the FCLT has a term resulting from the dependence. Explicit expressions are derived for the time-dependent means, variances, and covariances for the common case in which the limit process for the arrival process is a (possibly time scaled) Brownian motion.     

Heavily loaded queue coupled to two underloaded queues

We consider a system of three parallel queues with Poisson arrivals and exponentially distributed service requirements. The service rate for the heavily loaded queue depends on which of the two underloaded queues are empty. We derive the lowest-order asymptotic approximation to the joint stationary distribution of the queue lengths, in terms of a small parameter measuring the closeness of the heavily loaded queue to instability. To this order the queue lengths are independent, and the underloaded queues and the heavily loaded queue have geometrically and, after suitable scaling, exponentially distributed lengths, respectively. The expression for the exponential decay rate for the heavily loaded queue involves the solution to an inhomogeneous linear functional equation. Explicit results are obtained for this decay rate when the two underloaded queues have vastly different arrival and service rates.     

The Periodic BMAP/PH/c Queue

In queueing theory, most models are based on time-homogeneous arrival processes and service time distributions. However, in communication networks arrival rates and/or the service capacity usually vary periodically in time. In order to reflect this property accurately, one needs to examine periodic rather than homogeneous queues. In the present paper, the periodic BMAP/PH/c queue is analyzed. This queue has a periodic BMAP arrival process, which is defined in this paper, and phase-type service time distributions. As a Markovian queue, it can be analysed like an (inhomogeneous) Markov jump process. The transient distribution is derived by solving the Kolmogorov forward equations. Furthermore, a stability condition in terms of arrival and service rates is proven and for the case of stability, the asymptotic distribution is given explicitly. This turns out to be a periodic family of probability distributions. It is sketched how to analyze the periodic BMAP/M _t /c queue with periodically varying service rates by the same method.     

Analysis of Markov Multiserver Retrial Queues with Negative Arrivals

Negative arrivals are used as a control mechanism in many telecommunication and computer networks. In the paper we analyze multiserver retrial queues; i.e., any customer finding all servers busy upon arrival must leave the service area and re-apply for service after some random time. The control mechanism is such that, whenever the service facility is full occupied, an exponential timer is activated. If the timer expires and the service facility remains full, then a random batch of customers, which are stored at the retrial pool, are automatically removed. This model extends the existing literature, which only deals with a single server case and individual removals. Two different approaches are considered. For the stable case, the matrix–analytic formalism is used to study the joint distribution of the service facility and the retrial pool. The approximation by more simple infinite retrial model is also proved. In the overloading case we study the transient behaviour of the trajectory of the suitably normalized retrial queue and the long-run behaviour of the number of busy servers. The method of investigation in this case is based on the averaging principle for switching processes.