Hostname: page-component-76fb5796d-x4r87 Total loading time: 0 Render date: 2024-04-25T10:18:13.278Z Has data issue: false hasContentIssue false
  • English
  • Français

ON THE OPTIMAL OPEN-LOOP CONTROL POLICY FOR DETERMINISTIC AND EXPONENTIAL POLLING SYSTEMS

Published online by Cambridge University Press:  27 February 2007

Bruno Gaujal ,
Arie Hordijk  and
Dinard van der Laan
Bruno Gaujal
Affiliation:
Lab. ID-IMAG (INRIA, CNRS, INPG, UJF), 38330 Montbonnot Saint Martin, France, E-mail: bruno.gaujal@imag.fr
Arie Hordijk
Affiliation:
Department of Mathematics, Leiden University, 2300 RA Leiden, The Netherlands, E-mail: hordijk@math.leidenuniv.nl
Dinard van der Laan
Affiliation:
Faculty of Economics and Business Administration, Department of Econometrics, Vrije Universiteit, 1081 HV Amsterdam, The Netherlands, E-mail: dalaan@feweb.vu.nl
Get access Rights & Permissions [Opens in a new window]

Abstract

In this article, we consider deterministic (both fluid and discrete) polling systems with N queues with infinite buffers and we show how to compute the best polling sequence (minimizing the average total workload). With two queues, we show that the best polling sequence is always periodic when the system is stable and forms a regular sequence. The fraction of time spent by the server in the first queue is highly noncontinuous in the parameters of the system (arrival rate and service rate) and shows a fractal behavior. Moreover, convexity properties are shown and are used in a generalization of the computation of the optimal control policy (in open loop) for the stochastic exponential case.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 21 , Issue 2 , April 2007 , pp. 157 - 187
Copyright
© 2007 Cambridge University Press

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

REFERENCES

Altman, E., Gaujal, B., & Hordijk, A. (2000). Optimal open-loop control of vacations, polling and service assignment. Queueing Systems 36: 303–325.Google Scholar
Altman, E., Gaujal, B., & Hordijk, A. (2003). Discrete-event control of stochastic networks: Multimodularity and regularity. New York: Springer-Verlag.
Arian, Y. & Levy, Y. (1992). Algorithms for generalized round robin routing. Operations Research Letters 12: 313–319.Google Scholar
Borst, S. (1994). Polling systems. PhD thesis, Katholieke Universiteit Brabant, Tilburg.
Boxma, O.J., Levy, H., & Weststrate, J.A. (1991). Efficient vist frequencies for polling tables: Minimization of waiting cost. Queueing Systems 9: 133–162.Google Scholar
Boxma, O.J. & Tagaki, H. (eds.) (1992). Queueing Systems [Special issue on polling systems].
Coffman, E.G., Puhalskii, A.A., & Reiman, M.I. (1995). Polling systems with zero switchover times: A heavy-traffic averaging principle. Annals of Applied Probability 5: 681–719.Google Scholar
Combé, M.B. & Boxma, O.J. (1994). Optimization of static traffic allocation policies. Theoretical Computer Science 125: 17–43.Google Scholar
Gaujal, B. & Hyon, E. (2000). Optimal routing policy in two deterministic queues. Calculateurs Parallèles 13: 601–634.Google Scholar
Gaujal, B., Hyon, E., & Jean-Marie, A. (2004). Optimal open-loop routing in two parallel queues with exponential service times. In IEEE, Wodes, Reims, 2004. Long version available from http://www.inria.fr/rrrt/rr-5109.html.
Hardy, G.H. & Wright, E.M. (1960). An introduction to the theory of numbers, 4th ed. Oxford: Oxford University Press.
Hordijk, A. & Loeve, J.A. (1997). Optimal noncyclic server allocation in a polling model. In IEEE, Conference on Decision and Control, vol. 36, pp. 2941–2945.CrossRef
Hordijk, A. & van der Laan, D.A. (2003). Note on the convexity of the stationary waiting time as a function of the density. Probability in the Engineering and Information Sciences 17: 503–508.Google Scholar
Hordijk, A. & van der Laan, D.A. (2005). On the average waiting time for regular routing to deterministic queues. Mathematics of Operations Research 30: 521–544.Google Scholar
Kruskal, J.B. (1969). Work-scheduling algorithms: A non-probabilistic queueing study. Bell System Technical Journal 48: 2963–2974.Google Scholar
Lothaire, M. (2002). Algebraic combinatorics on words. Cambridge: Cambridge University Press.
Mack, C. (1957). The efficiency of n machines uni-directionally controlled by one operative when walking time and repair times are variable. Journal of the Royal Statistical Society Press, Series B 19(1): 173–178.Google Scholar
Mack, C., Murphy, T., & Webb, N.L. (1957). The efficiency of n machines uni-directionally controlled by one operative when walking time and repair times are constants. Journal of the Royal Statistical Society Press, Series B 19(1): 166–172.Google Scholar
Neuts, M.F. (1989). Structured stochastic matrices of M/G/1 type and their applications. New York: Marcel Dekker.
Perron, O. (1954). Die Lehre von den Kettenbrüchen. Stuttgart: Teubner.
Sinai, Y.G. (1976). Introduction to ergodic theory. Princeton, NJ: Princeton University Press.
Tagaki, H. (1986). Analysis of polling systems. Cambridge, MA: MIT Press.
Tijdeman, R. (2000). Fraenkel's conjecture for six sequences. Discrete Mathematics 222: 223–234.Google Scholar
van der Laan, D.A. (2003). The structure and performance of optimal routing sequences. PhD thesis, Leiden University.