Queueing Theory

Course Syllabus

Click here to get a copy of the syllabus in postscript format.

Course Objective

This course provides a systematic study of queues. A significant emphasis is placed on the development of sample-path methods for the analysis of queueing models.

Office Hours

Mondays, 3:00pm--5:00pm
Jonsson 4.912

TA

To be announced.

Text and References

Text: Stochastic Modeling and the Theory of Queues, by Ronald W. Wolff. Prentice-Hall, Englewood Cliffs, New Jersey, 1989.

References:

Heyman, D. P., and Stidham, S., Jr. [1980]. "The Relation Between Customer and Time Averages in Queues." Operations Research, 28, pp. 983-994.
Niu, S.-C. [1984]. "Inequalities Between Arrival Averages and Time Averages in Stochastic Processes Arising from Queueing Theory." Operations Research, 32, pp. 785-795.
Niu, S.-C. [1988]. "Representing Workloads in GI/G/1 Queues through the Preemptive-Resume LIFO Queue Discipline." Queueing Systems, 3, pp. 157-178.
Niu, S.-C., and Cooper, R. B. [1989]. "Duality and Other Results for M/G/1 and GI/M/1 Queues, via a New Ballot Theorem." Mathematics of Operations Research, 14, pp. 281-293.
Niu, S.-C., and Cooper, R. B. [1993]. "Transform-Free Analysis of M/G/1/K and Related Queues." Mathematics of Operations Research, 18, pp. 486-510.
Wolff, R. W. [1982]. "Poisson Arrivals See Time Averages." Operations Research, 30, pp. 223-231.

Prerequisites

OPRE 6330 and OPRE 6331; or consent of the instructor.

Grading Scheme

Final: 50% (take-home exam)
Presentation: 50%

Course Outline

Chapters 5, 8, 9, 11, 10, 6, 7, and references listed above. Topics include:

Basic queueing laws - L=\lambda W and PASTA
Markovian queues
M/G/1 and GI/M/c queues
Busy-period analysis
GI/G/1 queues, random walk, and duality
M/G/1/K finite-capacity queues and extensions
Insensitive queueing models
Bounds and approximations
Comparison of queues
Priority queues
Networks of queues

Papers Suggested for Presentation

Sarkar, D., and Zangwill, W. I. [1989]. "Expected Waiting Time for Nonsymmetric Cyclic Queueing Systems - Exact Results and Applications. Management Science, 35, pp. 1463-1474.
Boxma, O. J., and Groenendijk, W. P. [1987]. "Pseudo-Conservation Laws in Cyclic-Service Systems." Journal of Applied Probability, 24, pp. 949-964.
Tembe, S. V., and Wolff, R. W. [1974]. "The Optimal Order of Service in Tandem Queues." Operations Research, 24, pp. 824-832.
Fuhrmann, S. W., and Cooper, R. B. [1985]. "Stochastic Decompositions in the M/G/1 Queue with Generalzed Vacations." Operations Research, 33, pp. 1117-1129.
Courtois, P.-J., and Scheys, G. [1991]. "Minimization of the Total Loss Rate for Two Finite Queues in Series." IEEE Transactions on Communications, 39, pp. 1651-1661.
Ott, T. J. [1984]. "The Sojourn Time in the M/G/1 Queue with Processor Sharing." Journal of Applied Probability, 21, pp. 360-378.
Tak\'acs, L. [1969]. "On Erlang's Formula." Annals of Mathematical Statistics, 40, pp. 71-78.
Lavenberg, S. S. [1975]. "The Steady-State Queueing Time Distribution for the M/G/1 Finite-Capacity Queue." Management Science, 21, pp. 501-506.
Shanthikumar, J. G., and Sumita, U. [1987]. "Convex Ordering of Sojourn Times in Single-Server Queues: Extremal Properties of FIFO and LIFO Service Disciplines." Journal of Applied Probability, 24, pp. 734-748.
Wolff, R. W. [1970]. "Time Sharing with Priorities." SIAM Journal of Applied Mathematics, 19, pp. 566-574.

Assignments

Assignment #1
Assignment #2