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.     

Monotonicity and stability of periodic polling models

This paper deals with the stability of periodic polling models with a mixture of service policies. Customers arrive according to independent Poisson processes. The service times and the switchover times are independent with general distributions. The necessary and sufficient condition for the stability of such polling systems is established. The proof is based on the stochastic monotonicity of the state process at the polling instants. The stability of only a subset of the queues is also analyzed and, in case of heavy traffic, the order of explosion of the queues is given. The results are valid for a model with set-up times, and also when there is a local priority rule at the queues.This work was supported in part by a Fellowship of the Netherlands Organization for Scientific Research NWO-ECOZOEK.     

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

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.     

Finite buffer polling models with routing

This paper analyzes a finite buffer polling system with routing. Finite buffers are used to model the limited capacity of the system, and routing is used to represent the need for additional service. The most significant results of the analysis are the derivation of the generating function for queue length when buffer sizes are limited and a representation of the system workload. The queue lengths at polling instants are determined by solving a system of recursive equations; an embedded Markov chain analysis and numerical inversion are used to derive the queue length distributions. This system may be used to represent production models with setups and lost sales or expediting.     

Gated polling with stationary ergodic walking times, Markovian routing and random feedback

We investigate a gated polling system with semi-linear feedback and Markovian routing. We thereby relax the classical independence assumption on the walking times; the walking times constitute a sequence of stationary ergodic random variables. It is shown that the dynamics of this polling system can be described by semi-linear stochastic recursive equations in a Markovian environment. We obtain expressions for the first and second order moments of the workload and queue content at polling instants and for the mean queue content and workload at random instants.     

Towards a unifying theory on branching-type polling systems in heavy traffic

For a broad class of polling models the evolution of the system at specific embedded polling instants is known to constitute a multi-type branching process (MTBP) with immigration. In this paper it is shown that for this class of polling models the vector that describes the state of the system at these polling instants, say X=(X ₁,…,X _M ), satisfies the following heavy-traffic behavior (under mild assumptions):

A polling model with smart customers

In this paper we consider a single-server, cyclic polling system with switch-over times. A distinguishing feature of the model is that the rates of the Poisson arrival processes at the various queues depend on the server location. For this model we study the joint queue length distribution at polling epochs and at the server’s departure epochs. We also study the marginal queue length distribution at arrival epochs, as well as at arbitrary epochs (which is not the same in general, since we cannot use the PASTA property). A generalised version of the distributional form of Little’s law is applied to the joint queue length distribution at customer’s departure epochs in order to find the waiting time distribution for each customer type. We also provide an alternative, more efficient way to determine the mean queue lengths and mean waiting times, using Mean Value Analysis. Furthermore, we show that under certain conditions a Pseudo-Conservation Law for the total amount of work in the system holds. Finally, typical features of the model under consideration are demonstrated in several numerical examples.     

On ergodicity conditions in a polling model with Markov modulated input and state-dependent routing

A polling system with switchover times and state-dependent server routing is studied. Input flows are modulated by a random external environment. Input flows are ordinary Poisson flows in each state of the environment, with intensities determined by the environment state. Service and switchover durations have exponential laws of probability distribution. A continuous-time Markov chain is introduced to describe the dynamics of the server, the sizes of the queues and the states of the environment. By means of the iterative-dominating method a sufficient condition for ergodicity of the system is obtained for the continuous-time Markov chain. This condition also ensures the existence of a stationary probability distribution of the embedded Markov chain at instants of jumps. The customers sojourn cost during the period of unloading the stable queueing system is chosen as a performance metric. Numerical study in case of two input flows and a class of priority and threshold routing algorithms is conducted. It is demonstrated that in case of light inputs a priority routing rule doesn’t seem to be quasi-optimal.     

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.