The Impact of Scheduling Policies on the Waiting-time Distributions in Polling Systems

We consider polling models consisting of a single server that visits the queues in a cyclic order. In the vast majority of papers that have appeared on polling models, it is assumed that at each of the individual queues, the customers are served on a first-come-first-served (FCFS) basis. In this paper, we study polling models where the local scheduling policy is not FCFS but instead is varied as last-come-first-served (LCFS), random order of service (ROS), processor sharing (PS), and shortest-job-first (SJF). The service policies are assumed to be either gated or globally gated. The main result of the paper is the derivation of asymptotic closed-form expressions for the Laplace-Stieltjes transform of the scaled waiting-time and sojourn-time distributions under heavy-traffic assumptions. For FCFS service, the asymptotic sojourn-time distribution is known to be of the form (Formula presented.), where (Formula presented.) and (Formula presented.) are uniformly and gamma distributed with known parameters. In this paper, we show that the asymptotic sojourn-time distribution (1) for LCFS is also of the form (Formula presented.), (2) for ROS is of the form (Formula presented.), where (Formula presented.) has a trapezoidal distribution, and (3) for PS and SJF is of the form (Formula presented.), where (Formula presented.) has a generalized trapezoidal distribution. These results are rather intriguing and lead to new fundamental insight into the impact of the local scheduling policy on the performance of polling models. As a by-product, the heavy-traffic results suggest simple closed-form approximations for the complete waiting-time and sojourn-time distributions for stable systems with arbitrary load values. The accuracy of the approximations is evaluated by simulations. © 2014 Springer Science+Business Media New York