Abstract
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 \(U \varGamma \), where \(U\) and \(\varGamma \) 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 \(U \varGamma \), (2) for ROS is of the form \(\tilde{U} \varGamma \), where \(\tilde{U}\) has a trapezoidal distribution, and (3) for PS and SJF is of the form \(\tilde{U}^* \varGamma \), where \(\tilde{U}^*\) 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.
Similar content being viewed by others
References
Aalto, S., Ayesta, U., Righter, R.: Properties of the Gittins index with application to optimal scheduling. Probab. Eng. Inf. Sci. 25, 269–288 (2011)
Ayesta, U., Boxma, O.J., Verloop, I.M.: Sojourn times in a processor sharing queue with multiple vacations. Queueing Syst. 71, 53–78 (2012)
Boon, M.A.A., Adan, I.J.B.F., Boxma, O.J.: A polling model with multiple priority levels. Perform. Eval. 67, 468–484 (2010a)
Boon, M.A.A., Adan, I.J.B.F., Boxma, O.J.: A two-queue polling model with two priority levels in the first queue. Discret. Event Dyn. Syst. 20, 511–536 (2010b)
Boon, M.A.A., Winands, E.M.M., Adan, I.J.B.F., Van Wijk, A.C.C.: Closed-form waiting time approximations for polling systems. Perform. Eval. 68, 290–306 (2010c)
Boon, M.A.A., Van der Mei, R.D., Winands, E.M.M.: Applications of polling systems. Surv. Oper. Res. Manag. Sci. 16, 67–82 (2011)
Boxma, O.J., Bruin, J., Fralix, B.: Sojourn times in polling systems with various service disciplines. Perform. Eval. 66, 621–639 (2009)
Coffman, E.G., Puhalskii, A.A., Reiman, M.I.: Polling systems with zero switch-over times: a heavy-traffic principle. Ann. Appl. Probab. 5, 681–719 (1995)
Coffman, E.G., Puhalskii, A.A., Reiman, M.I.: Polling systems in heavy-traffic: a Bessel process limit. Math. Oper. Res. 23, 257–304 (1998)
Dorp, J.R., Kotz, S.: Generalized trapezoidal distributions. Metrika 58, 85–97 (2003)
Dorsman, J.L., Van der Mei, R.D., Winands, E.M.M.: A new method for deriving waiting-time approximations in polling systems with renewal arrivals. Stoch. Models 27, 318–332 (2011)
Levy, H., Sidi, M.: Polling models: applications, modeling and optimization. IEEE Trans. Commun. 38, 1750–1760 (1991)
Mack, C.: The efficiency of N machines uni-directionally patrolled by one operative when walking time is constant and repair times are variable. J. R. Stat. Soc. Series B 19, 173–178 (1957)
Mack, C., Murphy, T., Webb, N.: The efficiency of N machines uni-directionally patrolled by one operative when walking time and repair times are constants. J. R. Stat. Soc. Series B 19, 166–172 (1957)
Olsen, T.L., Van der Mei, R.D.: Periodic polling systems in heavy-traffic: distribution of the delay. J. Appl. Probab. 40, 305–326 (2003)
Olsen, T.L., Van der Mei, R.D.: Periodic polling systems in heavy-traffic: renewal arrivals. Oper. Res. Lett. 33, 17–25 (2005)
Olvera-Cravioto, M., Blanchet, J., Glynn, P.: On the transition from heavy traffic to heavy tails for the M/G/1 queue: the regularly varying case. Ann. Appl. Probab. 21, 645–668 (2011)
Resing, J.A.C.: Polling systems and multitype branching processes. Queueing Syst. 13, 409–426 (1993)
Takagi, H.: Analysis of Polling Systems. MIT Press, Cambridge, MA (1986)
Takagi, H.: Queueing analysis of polling models: an update. In: Takagi, H. (ed.) Stochastic Analysis of Computer and Communication Systems, pp. 267–318. Amsterdam, North-Holland (1990)
Takagi, H.: Application of polling models to computer networks. Comput. Netw. ISDN Syst. 22, 193–211 (1991)
Takagi, H.: Queueing analysis of polling models: progress in 1990–1994. In: Dshalalow, J.H. (ed.) Frontiers in Queueing: Models and Applications in Science and Technology, pp. 119–146. CRC Press, Boca Raton, FL (1997)
Tijms, H.C.: Stochastic Models: An Algorithmic Approach. Wiley, Chichester (2003)
Van der Mei, R.D.: Delay in polling systems with large switch-over times. J. Appl. Probab. 36, 232–243 (1999a)
Van der Mei, R.D.: Distribution of the delay in polling systems in heavy traffic. Perform. Eval. 31, 163–182 (1999b)
Van der Mei, R.D.: Polling systems in heavy traffic: higher moments of the delay. Queueing Syst. 31, 265–294 (1999c)
Van der Mei, R.D.: Polling systems with switch-over times under heavy load: moments of the delay. Queueing Syst. 36, 381–404 (2000)
Van der Mei, R.D.: Towards a unifying theory on branching-type polling systems in heavy traffic. Queueing Syst. 57, 29–46 (2007)
Vishnevskii, V.M., Semenova, O.V.: Mathematical methods to study the polling systems. Autom. Remote Control 67, 173–220 (2006)
Wierman, A., Winands, E.M.M., Boxma, O.J.: Scheduling in polling systems. Perform. Eval. 64, 1009–1028 (2007)
Williams, D.: Probability with Martingales. Cambridge University Press, Cambridge (1991)
Winands, E.M.M., Adan, I.J.B.F., Van Houtum, G.J.: Mean value analysis for polling systems. Queueing Syst. 54, 35–44 (2006)
Acknowledgments
The research of J.L. Dorsman is funded in the framework of the STAR-project “Multilayered queueing systems” by the Netherlands Organization for Scientific Research (NWO).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bekker, R., Vis, P., Dorsman, J.L. et al. The impact of scheduling policies on the waiting-time distributions in polling systems. Queueing Syst 79, 145–172 (2015). https://doi.org/10.1007/s11134-014-9416-8
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11134-014-9416-8