State dependent polling models

We consider a polling model in which a single server serves a number of queues in a cyclic order. 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. Since the server always sets up in the SI model, it has been conjectured that this model would provide an upper bound on the mean waiting time experienced by customers in the more-realistic SD model. This conjecture is incorrect; as shown through examples by several authors, reducing setup times may, in fact, lead to larger mean waiting times. The presence of such counterintuitive behavior called for a better understanding of the complex interactions among the various components of the model, and reiterated the need for exact analytical techniques to analyze the SD model. In this dissertation, 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. Furthermore, in applications of polling models, the computational effort required to compute exact results is often not justified by the accuracy actually required. To this end, we present a technique that provides performance bound hierarchies. Using this technique, increasingly accurate results can be obtained at the expense of additional computational effort. We also present expressions for some variants of the SD model, namely, SD model with a patient server and a gated service discipline.