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:

 

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):

  1. 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)
  2. Analytical-numerical techniques (matrix-analytical methods, compensation method, error bound method, approximate decomposition method)
  3. 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

sheets Lecture 1
sheets Lecture 2
sheets Lecture 3
sheets Lecture 4
sheets Lecture 5
sheets Lecture 6, part a,
sheets Lecture 6, part b
sheets Lecture 7
sheets Lecture 8
sheets Lecture 9


                     

R.J. Boucherie

Last modified: Fri, 24 Feb 2006