Advanced Queueing Theory (LNMB)
Lecturer:
Prof.dr R.J. Boucherie,
department of Applied Mathematics, University of Twente, P.O. Box 217, 7500 AE
Enschede
office: Ravelijn H 219
T: 053-4893432
E: r.j.boucherie@utwente.nl
Time/location:
Time: Mondays: 13.00 - 14.45 (February 27
– April 10 & April 24 & May 1)
Location: Room 107A, Buys Ballot
Laboratorium, Princetonlaan 4, The Uithof, Utrecht
Course material:
- F.P. Kelly, Reversibility
and Stochastic Networks, Wiley, 1979. http://www.statslab.cam.ac.uk/~frank/BOOKS/book/whole.pdf
- R. Nelson, Probability,
Stochastic Processes and Queueing Theory, Springer, 1995.
- R.W. Wolff, Stochastic
Modeling and the Theory of Queues, Prentice-Hall, 1989.
- G. Latouche, V Ramaswami.
Introduction to Matrix Analytic Methods in Stochastic Modeling, SIAM,
Philadelphia, 1999.
- M.F. Neuts.
Matrix-geometric solutions in stochastic models, An
algorithmic approach, Dover, New York, 1981.
- P. Whittle, Partial
balance and insensitivity, J. Appl. Prob. 22, pp 168-176 (1985)
- N.M.
van Dijk, Bounds and error bounds for queueing networks, Ann. Oper. Res,
79, pp 295-319 (1998)
- IJBF Adan, J. Wessels, and
WHM Zijm. Analysis of the symmetric shortest queue problem. Stochastic
Models, 6:691--713, 1990.
see thesis for details http://alexandria.tue.nl/extra3/proefschrift/PRF8A/9106931.pdf
- OJ Boxma, GJ van Houtum. The
compensation approach applied to a 2x2 switch, Prob. Inf
Sci, 7: 471-493, 1993.
- Tutorial on Matrix
analytic methods: http://www-net.cs.umass.edu/pe2002/papers/nelson.pdf
- V.
Ramaswami. Algorithmic
analysis of stochastic models; The changing face
of Mathematics.
Ramanujan Endowment Lecture at Anna University, Chennai, India, 2000.
- S.C.
Borst. Polling Systems, CWI: Tract, chapters 1 – 3. Borst
chapters 1 to 3, references
- S.W. Fuhrmann,
R.B. Cooper, Robert B.. Stochastic
Decomposition in the M/G/1 Queue with Generalized Vacations. Operations Research, Sep/Oct 1985, Vol. 33 Issue 5, p1117-1129
- J.A.C.
Resing. Polling systems and multitype branching
processes, Queueing Systems, 13, p 409 - 426
http://www.springerlink.com/media/cmw75594fjcqtwde4c3u/contributions/n/p/w/1/npw1360377056q11.pdf
Content:
Complex stochastic systems, like
communication systems, computer networks and manufacturing systems, may often
be modeled as queueing networks with multiple nodes and/or multiple classes.
The performance of these systems may thus be evaluated in terms of queue
lengths, sojourn times or blocking probabilities in queueing networks.
Specific topics include (a
selection from):
- Networks of queues
(product-form distribution, reversibility, output theorem, tandem
networks, partial balance, blocking, insensitivity, BCMP networks,
mean-value analysis, Norton's theorem, sojourn times)
- Analytical-numerical
techniques (matrix-analytical methods, compensation method, error bound
method, approximate decomposition method)
- Polling systems (cycle
times, queue lengths, waiting times, conservation laws, service policies,
visit orders)
Prerequisits
Basic knowledge of
probability theory, Markov chains, and elementary queueing theory, e.g., at the
level of Queueing Theory in the LNMB master programme.
Announcements:
none
Examination:
Take
home exercises
Content per lecture
Lecture
1: R.
Nelson, chapter 10, sections 10.1 – 10.2, F.P. Kelly, chapter 1
Lecture 2: R.
Nelson, chapter 10, sections 10.3, F.P. Kelly, chapter 2
Lecture 3: R.
Nelson, chapter 10, sections 10.4-10.7, F.P. Kelly, chapter 3
Lecture 4: P. Whittle, Partial
balance and insensitivity, J. Appl. Prob. 22, pp 168-176 (1985)
Lecture 5:
error bound technique: N.M. van Dijk, Bounds and error bounds for
queueing networks, Ann. Oper. Res, 79, pp 295-319 (1998)
Lecture
6: compensation
method: IJBF Adan, J. Wessels, and WHM Zijm. Analysis of the symmetric shortest queue problem. Stochastic Models, 6:691--713, 1990.
OJ Boxma, GJ van Houtum. The compensation approach applied to a 2x2
switch, Prob. Inf Sci, 7: 471-493, 1993.
Lecture
7: Matrix
analytical techniques, see http://www-net.cs.umass.edu/pe2002/papers/nelson.pdf
for tutorial
Lecture 8: Polling:
vacation models:
S.W. Fuhrmann,
R.B. Cooper, Robert B.. Stochastic Decomposition in the M/G/1 Queue with Generalized Vacations. Operations
Research, Sep/Oct
1985, Vol. 33 Issue 5, p1117-1129
S.C. Borst. Polling Systems, CWI: Tract, chapters 1 – 3. Borst
chapters 1 to 3
Lecture 9: Polling:
branching processes: J.A.C. Resing. Polling systems
and multitype branching processes, Queueing Systems, 13, p 409 –
426
http://www.springerlink.com/media/cmw75594fjcqtwde4c3u/contributions/n/p/w/1/npw1360377056q11.pdf
Hand-outs
Papers provided at
lectures.
Transparancies
R.J.
Boucherie
Last
modified: Fri, 24 Feb 2006