Queueing Theory (0365.4436)

uriy@post.tau.ac.il

Office Hours: TBA (and by appointment); Room 325, Schreiber Building (School of Mathematical Sciences)

Class Hours

Fall semester 2013-14: Tuesday 15:00 - 18:00; Room: TBA.

Final Exam

February 2014 (exact date will be announced)

Prerequisites

Probability Theory, Operations Research 1 (or equivalent), Introd. to Stochastic Processes (or equivalent)

Course Content

Queueing Theory deals with the analysis and design of complex systems where several 'servers' serve randomly-arriving 'customers' (e.g. jobs, calls, messages), each requiring service of random-duration length. While waiting for servers to become available, the customers form 'waiting lines', or queues.

Queueing theory is extensively used and applied in various areas, including Communication and Computer Networks, Service Systems, Manufacturing Systems, Road Traffic Analysis, Maintenance and Reliability, and more.

Queueing theory started in 1909 with the pioneering work of the Danish Scientist, Agner Krarup Erlang (born on January 1st, 1878), who published his paper, "The theory of probabilities and telephone conversations" (Nyt Tidsskrift for Matematik B, Vol. 20, 1909).

The course is directed to Graduate and 3rd year Undergraduate students with solid background in Probability Theory and some knowledge in Stochastic Processes.

Topics

1. Introduction.

Clasification of queueing systems; The Poisson process; Exponential and Erlang (Gamma) probability distribution functions; Laplace- Stieltjes Transforms (LSTs); Probability Generating Functions (PGFs); Order Statistics; The M/G/infinity queue.

2. The M/G/1 System.

Discrete-time model; Embedded Markov chain; The Stationary distribution and its PGF; PASTA; Khinchine-Pollaczek formula; Waiting times; Little's Law; The Busy Period and its LST; Delay Busy Period; Vacation models; Polling Systems (if time permits).

3. Birth and Death Processes (Markovian Queues).

The M/M/1, M/M/inf and M/M/c queues; Limited Buffer systems and Erlang's Loss formula; Multi-dimensional systems.

4. Matrix-Geometric Formulation and Solutions (if time permits).
5. Jackson Queueing Networks; Applications to Communication Systems.
6. Additional Models.

The G/M/1, G/M/c, G/Ek/1, M/D/c and M/D/inf queues.

7. Priority Queues (if time permits).

Head-of-the-Line and Pre-emptive disciplines; The c-mue rule; Last-come first-served (LCFS) versus First-come first served (FCFS); Random Order of Service (ROS); Processor Sharing; Shortest Remaining Processing Time (SRPT); Right-of-Way policy.

8. Optimization and Design of Queueing and Communication Systems.

Helpful Reference Books

• Kleinrock, L., Queueing Systems (Vol. 1: Theory, Vol.2: Computer Applications), Wiley, 1975 & 1976.
• Cooper, R.B., Introd. to Queueing Theory, North Holland, 1981.
• Bertsekas, D. and Gallager, R., Data Networks, Prentice-Hall, 1987.
• Walrand, J., An Introd. to Queueing Networks, Prentice-Hall, 1988.
• Wolff, R.W., Stochastic Modeling and the Theory of Queues, Prentice-Hall, 1989.
• Takagi, H., Queueing Analysis (Vol. I: Vacations and Priority Systems), North-Holland, 1991.