Nonexhaustive Policies in Polling Systems and Vacation Models: Qualitative and Approximate Approach

Abstract

We consider a polling system which consists of a number of queues attended by a single server. The server switches from one queue to another following a fixed cyclic order. Such a system finds a wide variety of applications in the computer, communication and manufacturing fields. Polling systems under the exhaustive service policy, where the server serves each queue until it becomes empty, have been extensively studied in the literature. This thesis studies nonexhaustive service policies, in particular the so-called limited and Bernoulli policies. Unlike the exhaustive policy, nonexhaustive policies usually do not lend themselves to exact analysis. We show that approaches based on heavy and light traffic analysis, and stochastic comparison techniques, can provide useful information about the performance of these policies. In the first part of the thesis, we consider polling systems with a single queue, more commonly known as a vacation models. In a fairly general setting, we prove heavy traffic limit theorems for vacation models under the Bernoulli and limited policies. We then establish light traffic results for vacation models with Poisson arrivals which are subsequently combined with the heavy traffic results to form the bases for interpolation approximations. Using stochastic comparison techniques, we identify some general conditions under which two service policies can be stochastically compared. In this framework, we establish bounds, nonotonicity and comparison results for various service policies. The comparison between the limited and Bernoulli policies represents a relatively harder problem and cannot be established in the general framework. However, we show that under more restrictive conditions, a weaker comparison in the increasing convex ordering indeed holds. In the second part of the thesis, we study M/GI/1 polling systems. Taking advantage of a recently established decomposition result, we first derive a pseudo-conservation law for the Bernoulli policy which, in the homogeneous case, leads to closed-form formulae for some performance measures. As a by-product, we obtain a comparison result between the Bernoulli and limited policies in homogeneous polling systems. For the limited policy, we propose and study an approximation algorithm which is based on the interpolation approximation developed for the vacation models.