We study cyclic polling models with exhaustive service at each queue under a variety of non-FCFS (first-come-first-served) local service orders, namely last-come-first-served with and without preemption, random-order-of-service, processor sharing, the multi-class priority scheduling with and without preemption, shortest-job-first, and the shortest remaining processing time policy. For each of these policies, we first express the waiting-time distributions in terms of intervisit-time distributions. Next, we use these expressions to derive the asymptotic waiting-time distributions under heavy-traffic assumptions, i.e. when the system tends to saturate. The results show that in all cases the asymptotic waiting-time distribution at queue i is fully characterized and of the form Γ Θi, with Γ and Θi independent, and where Γ is gamma distributed with known parameters (and the same for all scheduling policies). We derive the distribution of the random variable Θi which explicitly expresses the impact of the local service order on the asymptotic waiting-time distribution. The results provide new fundamental insight into the impact of the local scheduling policy on the performance of a general class of polling models. The asymptotic results suggest simple closed-form approximations for the complete waiting-time distributions for stable systems with arbitrary load values.

This paper considers a Markovian bulk-arriving queue modified to allow both mass arrivals when the queue is idle and mass departures which allow for the possibility of removing the entire workload. Properties of queues which terminate when the server becomes idle are developed first, since these play a key role in later developments. Results for the case of mass arrivals, but no mass annihilation, are then constructed with specific attention being paid to recurrence properties, equilibrium queue-size structure, and waiting-time distribution. A closed-form expression for the expected queue size and its Laplace transform are also established. All of these results are then generalised to allow for the removal of the entire workload, with closed-form expressions being developed for the equilibrium size and waiting-time distributions.

This paper deals with the single-server queue with batch arrivals. We show that under suitable conditions the waiting-time distribution of an individual customer has an asymptotically exponential expansion. Computationally useful characterizations of the amplitude factor and the decay parameter are given for the practically important case in which the interarrival time and the service time have phase-type distributions.

A classical result in queueing theory states that in the stable M/G/1 queue, the stationary distribution W(x) of the waiting time of an arriving customer or of the virtual waiting time satisfies a linear Volterra integral equation of the second kind, of convolution type. For many variants of the M/G/1 queue, there are corresponding integral equations, which in most cases differ from the Pollaczek–Khinchin equation only in the form of the inhomogeneous term. This leads to interesting factorizations of the waiting-time distribution and to substantial algorithmic simplifications. In a number of priority queues, the waiting-time distributions satisfy Volterra integral equations whose kernel is a functional of the busy-period distribution in related M/G/1 queues. In other models, such as the M/G/1 queue with Bernoulli feedback or with limited admissions of customers per service, there is a more basic integral equation of Volterra type, which yields a probability distribution in terms of which the waiting-time distributions are conveniently expressed.

For several complex queueing models with an embedded Markov renewal process of M/G/1 type, one obtains matrix Volterra integral equations for the waiting-time distributions or for related vectors of mass functions. Such models include the M/SM/1 and the N/G/1 queues, as well as the M/G/1 queue with some forms of bulk service.

When the service-time distributions are of phase type, the numerical computation of waiting-time distributions may commonly be reduced to the solution of systems of linear differential equations with constant coefficients.

A new upper bound on the stationary waiting-time distribution of a GI/G/1 queue is derived following Kingman's martingale approach. This bound is generally stronger than Kingman's upper bound and is sometimes stronger than an upper bound derived by Ross.

Exponential bounds for the stationary waiting-time distribution of the type ae–θt are considered. These bounds are obtained by the use of Kingman's method of ‘integral inequalities’. Approximations of Θ and a are given which are useful especially if the service and/or inter-arrival time distribution functions are NBUE or NWUE.