Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-27T09:27:29.625Z Has data issue: false hasContentIssue false
  • English
  • Français

M/G/∞ POLLING SYSTEMS WITH RANDOM VISIT TIMES

Published online by Cambridge University Press:  18 December 2007

M. Vlasiou  and
U. Yechiali
M. Vlasiou
Affiliation:
Georgia Institute of TechnologyH. Milton Stewart School of Industrial & Systems Engineering Atlanta, GA 30332-0205USA E-mail: [email protected]
U. Yechiali
Affiliation:
Department of Statistics and Operations Research School of Mathematical Sciences Raymond and Beverly Sackler Faculty of Exact SciencesTel Aviv UniversityTel Aviv 69978, Israel E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a polling system where a group of an infinite number of servers visits sequentially a set of queues. When visited, each queue is attended for a random time. Arrivals at each queue follow a Poisson process, and the service time of each individual customer is drawn from a general probability distribution function. Thus, each of the queues comprising the system is, in isolation, an M/G/∞-type queue. A job that is not completed during a visit will have a new service-time requirement sampled from the service-time distribution of the corresponding queue. To the best of our knowledge, this article is the first in which an M/G/∞-type polling system is analyzed. For this polling model, we derive the probability generating function and expected value of the queue lengths and the Laplace–Stieltjes transform and expected value of the sojourn time of a customer. Moreover, we identify the policy that maximizes the throughput of the system per cycle and conclude that under the Hamiltonian-tour approach, the optimal visiting order is independent of the number of customers present at the various queues at the start of the cycle.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 22 , Issue 1 , January 2008 , pp. 81 - 106
Copyright
Copyright © Cambridge University Press 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Altman, E. & Kushner, H.J. (2002). Control of polling in presence of vacations in heavy traffic with applications to satellite and mobile radio systems. SIAM Journal on Control and Optimization 41(1): 217–252.CrossRefGoogle Scholar
2.Asmussen, S. (2000). Matrix-analytic models and their analysis. Scandinavian Journal of Statistics: Theory and Applications 27(2): 193–226.CrossRefGoogle Scholar
3.Bernabéu-Aubán, J.M., Ammar, M.H., & Ahamad, M. (1995). Optimizing a generalized polling protocol for resource finding over a multiple access channel. Computer Networks and ISDN Systems 27(10): 1429–1445.CrossRefGoogle Scholar
4.Borst, S.C. (1996). Polling systems. CWI Tract. Vol. 115. Amsterdam: Stichting Mathematisch Centrum Centrum voor Wiskunde en Informatica.Google Scholar
5.Boxma, O.J. & Groenendijk, W.P. (1987). Pseudo conservation laws in cyclic service systems. Journal of Applied Probability 24: 949–964.Google Scholar
6.Boxma, O.J., Levy, H., & Yechiali, U. (1992). Cyclic reservation schemes for efficient operation of multiple-queue single-server systems. Annals of Operations Research 35(3): 187–208.CrossRefGoogle Scholar
7.Browne, S. & Yechiali, U. (1989). Dynamic priority rules for cyclic-type queues. Advances in Applied Probability 21(2): 432–450.Google Scholar
8.Browne, S. & Yechiali, U. (1988). Dynamic routing in polling systems. In Bonatti, M. (ed.), Teletraffic science for new cost-effective systems, networks, and services. Amsterdam: Elsevier Science, pp. 1455–1466.Google Scholar
9.Cooper, R.B. & Murray, G. (1969). Queues served in cyclic order. Bell System Technical Journal 48: 675–689.Google Scholar
10.Eliazar, I. & Yechiali, U. (1998). Polling under the randomly timed gated regime. Communications in Statistics: Stochastic Models 14(1–2): 79–93.Google Scholar
11.Levy, H. & Sidi, M. (1990). Polling systems: Applications, modeling, and optimization. IEEE Transactions on Communications 38(10): 1750–1760.CrossRefGoogle Scholar
12.Mack, C. (1957). The efficiency of N machines uni-directionally patrolled by one operative when walking time is constant and repair times are variable. Journal of the Royal Statistical Society, Series B, Methodological 19: 173–178.Google Scholar
13.Mack, C., Murphy, T., & Webb, N.L. (1957). The efficiency of N machines uni-directionally patrolled by one operative when walking time and repair times are constants. Journal of the Royal Statistical Society, Series B, Methodological 19: 166–172.Google Scholar
14.Nakdimon, O. & Yechiali, U. (2003). Polling systems with breakdowns and repairs. European Journal of Operational Research 149(3): 588–613.Google Scholar
15.Stidham, S. Jr. (1969). Optimal control of a signalized intersection. Part I: Introduction. structure of intersection models. Part II: Determining the optimal switching policies; Part III: Descriptive stochastic models. Technical reports 94, 95, and 96, Department of Operations Research, Cornell University, Ithaca, NY.Google Scholar
16.Takács, L. (1962). Introduction to the theory of queues. University Texts in the Mathematical Sciences. New York: Oxford University Press.Google Scholar
17.Takagi, H. (1986). Analysis of polling systems. Series In Research Reports and Notes: Computer Systems Series. Cambridge, MA: MIT Press.Google Scholar
18.Takagi, H. (1990). Queueing analysis of polling models: An update. In Dshalaow, J.H. (ed.), Stochastic analysis of computer and communication systems. Amsterdam: North-Holland, pp. 267–318.Google Scholar
19.Takagi, H. (1997). Queueing analysis of polling models: Progress in 1990–1994. In Takagi, H. (ed.), Frontiers in queueing, Probabability and Stochastics Series. Boca Raton, FL: CRC, pp. 119–146.Google Scholar
20.Tijms, H.C. (2003). A first course in stochastic models. Chichester: Wiley.Google Scholar
21.Twu, D.-C. & Chen, K.-C. (1996). A novel MAC protocol for broadband communication over CATV-based MANs. Computer Communications 19(11): 888–900.Google Scholar
22.van der Heijden, M., van Harten, A., & Ebben, M. (2001). Waiting times at periodically switched one-way traffic lanes: a periodic, two-queue polling system with random setup times. Probability in the Engineering and Informational Sciences 15(4): 495–517.Google Scholar
23.van der Wal, J. & Yechiali, U. (2003). Dynamic visit-order rules for batch-service polling. Probability in the Engineering and Informational Sciences 17(3): 351–367.Google Scholar
24.Van Vuuren, M. & Winands, E.M.M. (2006). Iterative approximation of k-limited polling systems. Technical report 2006-06, Eindhoven University of Technology. Available from http://www.win.tue.nl/math/bs/spor/.Google Scholar
25.Wang, Y.T. & Morris, R.J.T. (1985). Load sharing in distributed systems. IEEE Transactions on Computers C-34(3): 204–217.Google Scholar
26.Yechiali, U. (1993). Analysis and control of polling systems. In Donatiello, L. & Nelson, R. (eds.), Performance evaluation of computer and communication systems. Lecture Notes in Computer Science, Vol. 729. Berlin: Springer-Verlag, pp. 630–650.CrossRefGoogle Scholar