Simon Fraser University
Engaging the World

Course Outlines

Spring 2025 - MATH 895 G100

Reading (4)

Queuing Theory

Class Number: 2764

Delivery Method: In Person

Overview

  • Course Times + Location:

    Jan 6 – Apr 9, 2025: Mon, Wed, 1:30–3:20 p.m.
    Burnaby

Description

COURSE DETAILS:

Course Title: Queueing Theory

Meetings: Two 2-hour meetings per week (times tbd)

Outline:

1. Stochastic Processes

  • Markov chains
  • continuous time Markov chains
  • birth-and-death processes
  • Poisson processes
  • renewal processes
  • regenerative processes

2. General Concepts in Queueing Systems
  • queueing processes
  • steady-state behaviour (stochastic equilibrium)
  • Little's formula
  • characteristics of Poisson arrival processes

3. Birth-and-Death Queueing Systems: Exponential Models
  • single server exponential queue (M/M/1 queues)
  • queues with bounded waiting space (M/M/1/K queues)
  • exponential queue with an infinite number of servers (M/M/∞ queues)
  • Erlang loss model (M/M/c/c queues)
  • models with finite input source
  • multichannel queues

4. Non-Birth-and-Death Queueing Systems
  • bulk queueing models
  • queueing models with batch service

5. Queue Networks
  • networks of Markovian queues
  • Jackson networks

6. Non-Markovian Queueing Systems
  • embedded Markov chain technique
  • Pollaczek-Khinchin formula for the M/G/1 queue
  • G/M/1 queues
  • generalization of the Pollaczek-Khinchin formula for G/G/1 queues

7. Heavy Traffic Approximations
  • Kingman's approximation for G/G/1 queues
  • heavy traffic approximation for G/M/c queues

8. Discrete Event Simulation of Queueing Systems
  • event-based simulation
  • application to queueing systems

9. Accumulating Priority Queues (optional)
  • waiting time for the two-class accumulating priority queue (APQ)
  • waiting time for the multi-class APQ
  • simulation approaches

10. Queueing Games (optional)
  • Nash equilibria
  • social optimality and the price of anarchy
  • fluid models

COURSE-LEVEL EDUCATIONAL GOALS:

Students will gain an understanding of queueing theory, and more broadly of theory and applications of stochastic modelling. The course will focus primarily on Markovian queue models. Embedded Markov chain techniques for non-Markovian models and heavy traffic approximations will be studied with a view to applying our much richer mathematical understanding of Markovian models to applied models, which are often non-Markovian. If time allows, the course will end by exploring some optional topics: accumulating priority queues and queueing games.

Grading

  • Presentation of reading material in class (organization, understanding, and clarity) 30%
  • Biweekly homework assignments (correctness and exposition) 30%
  • Final course project (20% for written report and 20% for 20-minute presentation) 40%

Materials

MATERIALS + SUPPLIES:

Text: Medhi, J. Stochastic Models in Queueing Theory, 2nd edition, Academic Press (2003).


Additional Reading:

Gross, D., Shortle, J. F., Thompson, J. M., Harris, C. M., Fundamentals of Queueing Theory, 4th edition, Wiley (2008).

Ross, S. M., Simulation, 5th edition, Academic Press (2013).

Stanford, D. A., Taylor, P., Ziedins, I., Waiting time distributions in the accumulating priority queue. Queueing Systems, 77, 297–330 (2014).

Haviv, M. and Ravner, L., A survey of queueing systems with strategic timing of arrivals. Queueing Systems, 99, 163–198 (2021).

REQUIRED READING NOTES:

Your personalized Course Material list, including digital and physical textbooks, are available through the SFU Bookstore website by simply entering your Computing ID at: shop.sfu.ca/course-materials/my-personalized-course-materials.

Graduate Studies Notes:

Important dates and deadlines for graduate students are found here: http://www.sfu.ca/dean-gradstudies/current/important_dates/guidelines.html. The deadline to drop a course with a 100% refund is the end of week 2. The deadline to drop with no notation on your transcript is the end of week 3.

Registrar Notes:

ACADEMIC INTEGRITY: YOUR WORK, YOUR SUCCESS

SFU’s Academic Integrity website http://www.sfu.ca/students/academicintegrity.html is filled with information on what is meant by academic dishonesty, where you can find resources to help with your studies and the consequences of cheating. Check out the site for more information and videos that help explain the issues in plain English.

Each student is responsible for his or her conduct as it affects the university community. Academic dishonesty, in whatever form, is ultimately destructive of the values of the university. Furthermore, it is unfair and discouraging to the majority of students who pursue their studies honestly. Scholarly integrity is required of all members of the university. http://www.sfu.ca/policies/gazette/student/s10-01.html

RELIGIOUS ACCOMMODATION

Students with a faith background who may need accommodations during the term are encouraged to assess their needs as soon as possible and review the Multifaith religious accommodations website. The page outlines ways they begin working toward an accommodation and ensure solutions can be reached in a timely fashion.