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.     

Questionnaire design improvement and missing item scores estimation for rapid and efficient decision making

In this paper we consider a single-server, cyclic polling system with switch-over times and Poisson arrivals. The service disciplines that are discussed, are exhaustive and gated service. The novel contribution of the present paper is that we consider the reneging of customers at polling instants. In more detail, whenever the server starts or ends a visit to a queue, some of the customers waiting in each queue leave the system before having received service. The probability that a certain customer leaves the queue, depends on the queue in which the customer is waiting, and on the location of the server. We show that this system can be analysed by introducing customer subtypes, depending on their arrival periods, and keeping track of the moment when they abandon the system. In order to determine waiting time distributions, we regard the system as a polling model with varying arrival rates, and apply a generalised version of the distributional form of Little??s law. The marginal queue length distribution can be found by conditioning on the state of the system (position of the server, and whether it is serving or switching).     

Decomposition results for general polling systems and their applications

In this paper we derive decomposition results for the number of customers in polling systems under arbitrary (dynamic) polling order and service policies. Furthermore, we obtain sharper decomposition results for both the number of customers in the system and the waiting times under static polling policies. Our analysis, which is based on distributional laws, relaxes the Poisson assumption that characterizes the polling systems literature. In particular, we obtain exact decomposition results for systems with either Mixed Generalized Erlang (MGE) arrival processes, or asymptotically exact decomposition results for systems with general renewal arrival processes under heavy traffic conditions. The derived decomposition results can be used to obtain the performance analysis of specific systems. As an example, we evaluate the performance of gated Markovian polling systems operating under heavy traffic conditions. We also provide numerical evidence that our heavy traffic analysis is very accurate even for moderate traffic. This revised version was published online in June 2006 with corrections to the Cover Date.     

On open problems in polling systems

In the present paper we address two open problems concerning polling systems, viz., queueing systems consisting of multiple queues attended by a single server that visits the queues one at a time. The first open problem deals with a system consisting of two queues, one of which has gated service, while the other receives 1-limited service. The second open problem concerns polling systems with general (renewal) arrivals and deterministic switch-over times that become infinitely large. We discuss related, known results for both problems, and the difficulties encountered when trying to solve them.     

Optimal control for an MX/G/1 queue with two service modes

A practically important model is the queueing model with controllable service rate. This paper considers a single-server model with batch Poisson input and two service modes, where switch-over times are involved when changing the service mode. A class of simple switch-over rules is considered and, using Markov decision theory, a tailor-made policy-iteration algorithm is developed for computing a rule that mimimizes the long-run average number of customers in the system.     

Single-server queues with spatially distributed arrivals

Consider a queueing system where customers arrive at a circle according to a homogeneous Poisson process. After choosing their positions on the circle, according to a uniform distribution, they wait for a single server who travels on the circle. The server's movement is modelled by a Brownian motion with drift. Whenever the server encounters a customer, he stops and serves this customer. The service times are independent, but arbitrarily distributed. The model generalizes the continuous cyclic polling system (the diffusion coefficient of the Brownian motion is zero in this case) and can be interpreted as a continuous version of a Markov polling system. Using Tweedie's lemma for positive recurrence of Markov chains with general state space, we show that the system is stable if and only if the traffic intensity is less than one. Moreover, we derive a stochastic decomposition result which leads to equilibrium equations for the stationary configuration of customers on the circle. Steady-state performance characteristics are determined, in particular the expected number of customers in the system as seen by a travelling server and at an arbitrary point in time.     

Polling systems in heavy traffic: Higher moments of the delay

We study an asymmetric cyclic polling model with general mixtures of exhaustive and gated service, and with zero switch-over times, in heavy traffic. We derive closed-form expressions for all moments of the steady-state delay at each of the queues, under standard heavy-traffic scalings. The expressions obtained provide new and useful insights into the behavior of polling systems under heavy-load conditions. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Polling systems with state-dependent setup times

We analyze a polling system with multiple stations (queues) attended by a cycling server, in which a setup occurs only when the queue that is polled by the server has one or more customers present. Although such systems are appropriate for modeling numerous manufacturing and telecommunication systems, their analysis is not well developed in the literature. We provide an exact analysis for the 2 station model and present two approximation schemes to determine the mean station waiting times for models with 3 or more stations. We show that some approximate models which have been proposed in the literature for providing upper bounds on the mean station waiting times do not always yield upper bounds. Extensive numerical tests indicate that a simple average of the two approximation schemes yields a close estimate of the true mean station waiting time. This average-of-approximations procedure appears to be robust for a large range of parameter values.Research supported in part by the Natural Sciences and Engineering Research Council of Canada under grant OGP0045904.Research supported in part by the National Science Foundation under grant DMI-9500471.     

Stochastic bounds for a polling system

In this note we consider two queueing systems: a symmetric polling system with gated service at allN queues and with switchover times, and a single-server single-queue model with one arrival stream of ordinary customers andN additional permanently present customers. It is assumed that the combined arrival process at the queues of the polling system coincides with the arrival process of the ordinary customers in the single-queue model, and that the service time and switchover time distributions of the polling model coincide with the service time distributions of the ordinary and permanent customers, respectively, in the single-queue model. A complete equivalence between both models is accomplished by the following queue insertion of arriving customers. In the single-queue model, an arriving ordinary customer occupies with probabilityp _i a position at the end of the queue section behind theith permanent customer,i = l, ...,N. In the cyclic polling model, an arriving customer with probabilityp _i joins the end of theith queue to be visited by the server, measured from its present position.For the single-queue model we prove that, if two queue insertion distributions {p _{i, i} = l, ...,N} and {q _{i, i} = l, ...,N} are stochastically ordered, then also the workload and queue length distributions in the corresponding two single-queue versions are stochastically ordered. This immediately leads to equivalent stochastic orderings in polling models.Finally, the single-queue model with Poisson arrivals andp ₁ = 1 is studied in detail.Part of the research of the first author has been supported by the Esprit BRA project QMIPS.     

Waiting-Time Distributions in Polling Systems with Simultaneous Batch Arrivals

We study the delay in asymmetric cyclic polling models with general mixtures of gated and exhaustive service, with generally distributed service times and switch-over times, and in which batches of customers may arrive simultaneously at the different queues. We show that (1–)X _i converges to a gamma distribution with known parameters as the offered load tends to unity, where X _i is the steady-state length of queue i at an arbitrary polling instant at that queue. The result is shown to lead to closed-form expressions for the Laplace–Stieltjes transform (LST) of the waiting-time distributions at each of the queues (under proper scalings), in a general parameter setting. The results show explicitly how the distribution of the delay depends on the system parameters, and in particular, on the simultaneity of the arrivals. The results also suggest simple and fast approximations for the tail probabilities and the moments of the delay in stable polling systems, explicitly capturing the impact of the correlation structure in the arrival processes. Numerical experiments indicate that the approximations are accurate for medium and heavily loaded systems.     

A polling model with an autonomous server

This paper considers polling systems with an autonomous server that remains at a queue for an exponential amount of time before moving to a next queue incurring a generally distributed switch-over time. The server remains at a queue until the exponential visit time expires, also when the queue becomes empty. If the queue is not empty when the visit time expires, service is preempted upon server departure, and repeated when the server returns to the queue. The paper first presents a necessary and sufficient condition for stability, and subsequently analyzes the joint queue-length distribution via an embedded Markov chain approach. As the autonomous exponential visit times may seem to result in a system that closely resembles a system of independent queues, we explicitly investigate the approximation of our system via a system of independent vacation queues. This approximation is accurate for short visit times only.      

Unified analysis of <Emphasis Type="Italic">BMAP</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/1 cyclic polling models

In this paper we present a unified analysis of the BMAP/G/1 cyclic polling model and its application to the gated and exhaustive service disciplines as examples. The applied methodology is based on the separation of the analysis into service discipline independent and dependent parts. New expressions are derived for the vector-generating function of the stationary number of customers and for its mean in terms of vector quantities depending on the service discipline. They are valid for a broad class of service disciplines and both for zero- and nonzero-switchover-times polling models. We present the service discipline specific solution for the nonzero-switchover-times model with gated and exhaustive service disciplines. We set up the governing equations of the system by using Kronecker product notation. They can be numerically solved by means of a system of linear equations. The resulting vectors are used to compute the service discipline specific vector quantities.     

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.     

Workloads and waiting times in single-server systems with multiple customer classes

One of the most fundamental properties that single-server multi-class service systems may possess is the property of work conservation. Under certain restrictions, the work conservation property gives rise to a conservation law for mean waiting times, i.e., a linear relation between the mean waiting times of the various classes of customers. This paper is devoted to single-server multi-class service systems in which work conservation is violated in the sense that the server's activities may be interrupted although work is still present. For a large class of such systems with interruptions, a decomposition of the amount of work into two independent components is obtained; one of these components is the amount of work in the corresponding systemwithout interruptions. The work decomposition gives rise to a (pseudo)conservation law for mean waiting times, just as work conservation did for the system without interruptions.     

The 1-Center and 1-Highway problem revisited

We consider a two-queue polling model in which customers upon arrival join the shorter of two queues. Customers arrive according to a Poisson process and the service times in both queues are independent and identically distributed random variables having the exponential distribution. The two-dimensional process of the numbers of customers at the queue where the server is and at the other queue is a two-dimensional Markov process. We derive its equilibrium distribution using two methodologies: the compensation approach and a reduction to a boundary value problem.     

Performance analysis of polling systems with retrials and glue periods

We consider gated polling systems with two special features: (i) retrials and (ii) glue or reservation periods. When a type-i customer arrives, or retries, during a glue period of the station i, it will be served in the following service period of that station. Customers arriving at station i in any other period join the orbit of that station and will retry after an exponentially distributed time. Such polling systems can be used to study the performance of certain switches in optical communication systems. When the glue periods are exponentially distributed, we obtain equations for the joint generating functions of the number of customers in each station. We also present an algorithm to obtain the moments of the number of customers in each station. When the glue periods are generally distributed, we consider the distribution of the total workload in the system, using it to derive a pseudo-conservation law which in turn is used to obtain accurate approximations of the individual mean waiting times. We also investigate the problem of choosing the lengths of the glue periods, under a constraint on the total glue period per cycle, so as to minimize a weighted sum of the mean waiting times.     

Markovian polling systems with mixed service disciplines and retrial customers

A Markovian polling model with a mixture of exhaustive and gated type stations is considered. The cuttomers are ofn different tppes and arrive to the system acccording to the Poisson distribution, in batches containing customers of all types (correlated batch arrivals). The customers who find upon arrival the server unavailable repeat their arrival individually after a random amount of time (retrial customers). The service timesT _i and the switchover timesV _ij are arbitrarily distributed with different distributions for the different stations. For such a model we obtain formulae for the expected number of customers in each station in a steady state. Our formulae hold also for zero switchover periods and can easily be adapted to hold for the corresponding ordinary Markovian mixed polling models with/without switchover times and correlated batch arrivals. Numerical calculations are finally used to observe system's performance.     

Polling: past,present, and perspective

This is a survey on polling systems, focussing on the basic single-server multi-queue polling system in which the server visits the queues in cyclic order. The main goals of the paper are: (i) to discuss a number of the key methodologies in analyzing polling models; (ii) to give an overview of recent polling developments; and (iii) to present a number of challenging open problems.     

A note on polling models with renewal arrivals and nonzero switch-over times

We consider gated polling systems with general service and switch-over times and with renewal arrival processes. We derive closed-form expressions for the expected delay in heavy-traffic (HT). So far, proofs of HT limits have only been obtained for Poisson-type arrival processes, whereas for renewal arrivals limits are based on conjectures.