Abstract
In this paper, we develop a general framework to analyze polling systems with either the autonomous-server or the time-limited service discipline. According to the autonomous-server discipline, the server continues servicing a queue for a certain period of time. According to the time-limited service discipline, the server continues servicing a queue for a certain period of time or until the queue becomes empty, whichever occurs first. We consider Poisson batch arrivals and phase-type service times. It is known that these disciplines do not satisfy the well-known branching property in polling systems. Therefore, hardly any exact results exist in the literature. Our strategy is to apply an iterative scheme that is based on relating in closed-form the joint queue-lengths at the beginning and the end of a server visit to a queue. These kernel relations are derived using the theory of absorbing Markov chains.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abate, J., & Whitt, W. (1992). Numerical inversion of probability generating functions. Operations Research Letters, 12(4), 245–251.
Al Hanbali, A., de Haan, R., Boucherie, R. J., & van Ommeren, J.-K. (2008a). A tandem queueing model for delay analysis in disconnected ad hoc networks. In LCNS: Vol. 5055. Proc. of ASMTA (pp. 189–205), Nicosia, Cyprus, June 2008.
Al Hanbali, A., de Haan, R., Boucherie, R. J., & van Ommeren, J.-K. (2008b). Time-limited and k-limited polling systems: a matrix analytic solution. In Proc. of SMCTools, Athens, Greece, Oct. 2008.
Bernstein, D. S. (2005). Matrix mathematics. Princeton: Princeton University Press.
Blanc, J. (1992a). An algorithmic solution of polling models with limited service disciplines. IEEE Transactions on Communications, 40(7), 1152–1155.
Blanc, J. (1992b). Performance evaluation of polling systems by means of the power-series algorithm. Annals of Operation Research, 35(3), 155–186.
Blanc, J. (1998). The power-series algorithm for polling systems with time limits. Probability in the Engineering and Informational Sciences, 12, 221–237.
Bolch, G., Greiner, S., de Meer, H., & Trivedi, K. (2006). Queueing networks and Markov chains: modeling and performance evaluation with computer science applications. New York/Oxford: Wiley/Blackwell.
Cohen, J. W. (1982). The single server queue. Amsterdam: North-Holland.
Daigle, J. (1989). Queue length distributions from probability generating functions via discrete Fourier transforms. Operations Research Letters, 8(4), 229–236.
de Haan, R. (2009). Queueing models for mobile ad hoc networks. PhD thesis, Enschede, June 2009. http://doc.utwente.nl/61385/.
de Haan, R., Boucherie, R. J., & van Ommeren, J.-K. (2009). A polling model with an autonomous server. Queueing Systems, 62(3), 279–308.
Eisenberg, M. (1972). Queues with periodic service and changeover times. Operations Research, 20(2), 440–451.
Fricker, C., & Jaibi, M. (1994). Monotonicity and stability of periodic polling models. Queueing Systems, 15(1–4), 211–238.
Gaver, D. P., Jacobs, P. A., & Latouche, G. (1984). Finite birth-and-death models in randomly changing environments. Advances in Applied Probability, 16, 715–731.
Grinstead, C., & Snell, J. (1997). Introduction to Probability. Providence: American Mathematical Society.
Guillemin, F., & Simonian, A. (1995). Transient characteristics of an M/M/1/infinity system. Advances in Applied Probability, 27, 862–888.
Leung, K. (1991). Cyclic-service systems with probabilistically-limited service. IEEE Journal on Selected Areas in Communications, 9(2), 185–193.
Leung, K. (1994). Cyclic-service systems with non-preemptive time-limited service. IEEE Transactions on Communications, 42(8), 2521–2524.
Levy, H., & Sidi, M. (1990). Polling systems: applications, modeling, and optimization. IEEE Transactions on Communications, 38(10).
Malhis, L., & Sanders, W. (1996). An efficient two-stage iterative method for the steady-state analysis of Markov regenerative stochastic Petri net models. Performance Evaluation, 27, 583–601.
Nakatsuka, T. (2009). Queue length distribution in M/G/1, M x/G/1 and their variants with completion time. Journal of the Operations Research, 52(1), 11–34.
Neuts, M. (1981). Matrix-geometric solutions in stochastic models: an algorithmic approach. Baltimore: Johns Hopkins University Press.
Philippe, B., Saad, Y., & Stewart, W. (1992). Numerical methods in Markov chain modeling. Operations Research, 40(6), 1156–1179.
Resing, J. (1993). Polling systems and multitype branching processes. Queueing Systems, 13(10), 409–429.
Stewart, W. (2009). Probability, Markov chains, queues, and simulation: the mathematical basis of performance modeling. Princeton: Princeton University Press.
Takagi, H. (2000). Analysis and application of polling models. In LNCS: Vol. 1769. Performance evaluation: origins and directions (pp. 423–442). Berlin: Springer.
Tijms, H. (2003). A first course in stochastic models. New York: Wiley.
Titchmarsh, E. (1976). The theory of functions. Oxford: Oxford Science Publications.
Van Houdt, B. (2010). Numerical solution of polling systems for analyzing networks on chips. In Proc. of NSMC, Virginia, USA.
van Vuuren, M., & Winands, E. (2007). Iterative approximation of k-limited polling systems. Queueing Systems: Theory and Applications, 55(3), 161–178.
Yechiali, U., & Eliazar, I. (1998). Polling under the randomly-timed gated regime. Stochastic Models, 14(1), 79–93.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Al Hanbali, A., de Haan, R., Boucherie, R.J. et al. Time-limited polling systems with batch arrivals and phase-type service times. Ann Oper Res 198, 57–82 (2012). https://doi.org/10.1007/s10479-011-0846-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-011-0846-y