Queueing Theory (0365.4436)

uriy@tauex.tau.ac.il

Office Hours: By appointment (via email), Room 325, Schreiber Building

Class Hours

Fall semester 2024-2025: Sunday 16-19, Schreiber 007

Final Exam:

Moed A: 16.02.25, 9 AM; Moed B: 21.03.25 9 AM

Prerequisites

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

Reading preparation: Yechiali, U. and Boxma, O.J.,"Poisson Processes, Ordinary and Compound", Encyclopedia of Statistics in Quality and Reliability" (F. Ruggeri, R.S. Kenett and F.W. Faltin, Eds.), Wiley, New York, 2007.

Course Content

Queueing Theory deals with the analysis and design of complex stochastic systems where several 'servers' serve randomly-arriving 'customers' (e.g. jobs, calls, messages), each requiring service of random duration. While waiting for servers to become available, the customers form 'waiting lines', or queues. On the other hand, when no customers are present, the servers stay idle waiting for customers to arrive. Due to the stochastic nature of queues, neither of the two sources of idleness can be entirely eliminated. The aim of the course is to study probabilistic anlytical methods to analyse queueing systems, and to optimaly design their configurations.

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.

Classification 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/infinity, 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/infinity 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.
9. Introduction to Strategic Queues.

Naor's model for M/M/1; Yechiali's model for GI/M/1 and GI/M/c.

Helpful Reference Books

• Cox, D.R. and Smith, W.L., Queues, Wiley, 1961.
• Saaty, T.L., Elements of Queueing Theory, McGraw-Hill, 1961.
• Takacs, L., Introd. to the Theory of Queues, Oxford University Press, 1962.
• Conway, R.W., Maxwell, W.L. and Miller, L.W., Theory of Scheduling, Addison-Wesley, 1967.
• Cohen, J.W., The Single Server Queue, North Holland 1969 (revised 1982).
• Kleinrock, L., Queueing Systems (Vol. 1: Theory, Vol. 2: Computer Applications), Wiley, 1975 & 1976.
• Kelly, F. P., Reversibility and Stochastic Networks, Wiley, 1979.
• Karlin, S. and Taylor, H.M., A Second Course in Stochastic Processes (Chap. 18), Academic Press, 1981
• Cooper, R.B., Introd. to Queueing Theory, North Holland, 1981.
• Neuts, M.F., Matrix-Geometric Solutions in Stochastic Models, The John Hopkins Univ. Press, 1981.
• Chaudhry, M.L. and Tempelton, J.G.C., A First Course in Bulk Queues, Wiley, 1982.
• Takagi, H., Analysis of Polling Systems, The MIT Press, 1986.
• 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.
• Falin, G.I. and Tempelton, J.G.C., Retrial Queues, Chapman & Hall, 1997.
• Latouche, G. and Ramaswami, V., Introd. to Matrix Analytic Methods in Stochastic Modeling, ASA-SIAM Series, 1999.
• Chen, H. and Yao, D.D., Fundamentals of Queueing Networks, Springer, 2001.
• Gross, D. and Harris, C.M., Fundamentals of Queueing Theory (4th ed.), Wiley, 2008.
• Harchol-Balter, M., Performance Modeling and Design of Computer Systems, Cambridge University Press, 2013.
• Haviv, M., Queues, Springer, 2013.
• Hassin, R. and Haviv, M., To Queue or Not to Queue, Springer, 2013.
• Hassin, R., Rational Queueing, CRC Press, 2016.

Last update: October 2024