说明: 说明: 说明: 说明: 说明: 说明: 说明: 说明: 说明: 说明: 说明: 说明: 说明: D:\XiaLi\ImportantData\课程资料\1.排队论与随机服务系统\2015\web\course_queues.htm



previous archives:  2012-Fall; 2014-Fall; 2015-Fall;

说明: 说明: 说明: 说明: 说明: 说明: 说明: 说明: 说明: 说明: 说明: 说明: 说明: image002

Course Name:  Queueing Theory and Stochastic Service Systems (#80250872, 2018-Fall)





Office Hours

Li Xia

FIT 3-618



By Appointment

  • Time/Place: Friday 9:50-11:25 at Room 1111, Lecture Building 3, Tsinghua Univ.
  • Required textbook:  Mor Harchol-Balter, Performance Modeling and Design of Computer Systems—Queueing Theory in Action, Cambridge Press, 2013. (copy is provided)
  • Reference books:
    • D. Gross, J.F. Shortle, J.M. Thompson, and C.M. Harris, Fundamentals of Queueing Theory, 4th Edition, Hoboken: Wiley, 2008.
    • Leonard Kleinrock, Queueing Systems, Vol. I: Theory, John Wiley, 1975.
    • Caltech course (Prof. Adam Wierman): http://courses.cms.caltech.edu/cs147/
    • Research papers.
  • Course description: Queueing theory is a research branch of the field of operation research. Queueing theory discusses the system modeling, performance analysis and optimization for a type of service systems with resource constraints and random scenarios. This course aims to offer students systematic knowledge about the fundamentals of queueing theory, how to apply queueing theory to analyze the performance of systems such as computer systems, communication networks, manufacturing systems, supply chain and logistics. The course also offers the introduction of the state-of-art of queueing theory. The goal of the course is to let students acquire the fundamentals of queueing theory, and learn the basic analysis methods to model and analyze the practical engineering systems. The course has a schedule of course paper or project discussion to improve the students’ active learning capability and train the basic research methods and skills.
  • Audiences: Graduate students
  • Prerequisites: The knowledge of probability and stochastic process is the prerequisite of this course.
  • Recommended Departments: Automation, Electronic Engineering, Industrial Engineering
  • Recommended Disciplines: Control Science and Engineering, Management Science and Engineering
  • Grading:
    • Homework: 30%
    • Midterm or Presentation: 30%
    • Final Project: 30%
    • Course Interaction: 10%

  • Homework policy:  Homework is required to use Latex to edit in English, submitted in the form of pdf file.
    All assignments, paper presentations, projects should be done by students independently. Student should clearly cite or mark if they refer to others’ publications or they have discussion with others. When students use the actual words of a source, they must put those words inside quotation marks. Plagiarization is strictly prohibited.
  • Course Calendar:









Introduction and examples

  • Lecture Note [PDF]
  • Introduction of queueing theory
  • Application area
  • Counterintuitive examples


Probabilities and typical distributions in queueing theory

  • Lecture Note [PDF]
  • Elementary probabilities
  • Z-transform, Laplace-transform
  • Geo/Mix-Geo/Binomial/Poisson distribution
  • Exp/Hyper-Exp/Erlang/Coxian distribution
  • Phase-Type distribution


Stochastic process, Markov chain

  • Lecture Note [PDF]
  • Stochastic process
  • Point/Renewal/Poisson process
  • MMPP, Markov arrival process(MAP)
  • Discrete time Markov chain


Markov process and birth-death process

  • Lecture Note [PDF]
  • Reschedule for National Holiday
  • Discrete time Markov chain, ergodicity
  • Continuous time Markov process
  • Birth-death process and C-K equation


Assignment 1

  • Due 10-26, in English, use Latex
  • Solution [PDF]


PASTA theorem and M/M/1 queue (thorough)

  • Lecture Note [PDF]
  • PASTA theorem
  • Analysis results of M/M/1
  • Local/Global balance equation
  • Steady state distribution of M/M/1
  • Mean value of queue length/response time/waiting time/busy period
  • Distribution of response time/waiting time


M/M/1 with priority, M/M/m, M/M/m/m, Erlang formulas

  • Lecture Note [PDF]
  • M/M/1 with preemptive priority
  • M/M/1 with non-preemptive priority
  • M/M/m/m and Erlang-B fromula
  • M/M/m/m and Erlang-C formula


Assignment 2

  • Due 11-09
  • Solution [PDF]


Discrete event simulation, choose number of servers,
state-dependent service

  • Lecture Note [PDF]
  • Generate random variables: Inverse-transform method, accept-reject method
  • Simulation: event scheduling approach
  • Square root law to choose # of servers
  • Load(or state)-dependent service rate


Finite source queue M/M/c//K, queues with impatience, Advanced Markovian queues

  • Lecture Note [PDF]
  • Finite source queue M/M/c//K
  • Balking/reneging/jockeying/retrial queue
  • Batch queue, M[X]/M/1, M/M[Y]/1
  • Erlang queue, M/Ek/1, Ek/M/1



  • Lecture Note [PDF]
  • M/G/1 queue
  • Residual service time
  • Inspection  paradox



  • Midterm
  • 1-1.5 hour test


Simulation project

  • Simulation project [PDF]
  • Finish the simulation programs, do numerical analysis and theoretical analysis, finish a detailed simulation report and give your discussion and conclusion, do necessary literature review to support your results.  12-28 (Due)


Queues with priority, retrial queue

  • Lecture Note [PDF]
  • M/M/1 queue with priority for multiple classes
  • M/G/1 queue with priority for multiple classes
  • Comparison of 4 different types of M/M/1 queue with/without priority
  • Retrial queue for M/M/1, M/M/c


Assignment 3

  • Due 12-07
  • Solution [PDF]


Open queueing netowrkd M/G/1 with priority queuey refer to others'mselveswork

  • Lecture Note [PDF]
  • Series queues
  • Burke’s theorem
  • Time reversible Markov chain
  • Open Jackson networks
  • Jackson’s theorem
  • Product form solution


Closed queueing network

  • Lecture Note [PDF]
  • Closed Jackson networks
  • Visit ratio by traffic equations
  • Buzen’s algorithm, computing G(N)


Assignment 4

  • Due 12-21


Mean value analysis method, variants of Jackson networks

  • Lecture Note [PDF]
  • Mean value analysis for queueing networks
  • Arrival theorem
  • Cyclic networks
  • General Jackson networks
  • BCMP networks



Application examples (1-2 lect, 4 example)

  • Lecture Note [PDF]
  • Google page rank (use Markov chain)
  • Aloha protocol analysis
  • Store-and-forward packet-switched network (use open Jackson network model)
  • Virtual circuit with window flow control (use closed Jackson network model)


Optimal control of queuessensitivity-based optimization, reinforcement learning

  • Lecture Note [PDF]
  • Optimal control of queueing systems (service rate, admission, routing probability, etc.)
  • Economics in queueing systems (pricing, utility function, game, equilibrium)
  • Sensitivity-based optimization (difference formula and derivative formula)
  • Reinforcement learning vs MDP vs optimal control
  • Data-driven vs model-driven


Other topics of queues

  • Lecture Note [PDF]
  • Matrix Analytical Method (MAM), QBD
  • GI/M/1 queues
  • Other queues, such as retrial, poll, or queues with vacations
  • Asymptotical analysis of complicated queues
  • ……


Research papers (complemental)

  • Example project1 [PDF]
  • Example project2 [PDF]
  • Dynamic pricing control, Manage. Sci., 2006 [PDF]
  • Dynamic pricing control, Oper. Res., 2001 [PDF]
  • Service rate control, [PDF]
    Adv. Appl. Prob., 1987 [PDF]
  • Admission control [PDF]
  • Queues in communication
  • Queues in healthcare
  • Queues in transportation
  • Queues in inventory/logistics

  • Modeling of e-Commercial website
  • Modeling of Data Center
  • Dynamic control of an M/M/1 service system with adjustable arrival and service rates(Ata)
  • Dynamic control of a queue with adjustable service rate (George & Harrison)
  • Optimal control of service rates in networks of queues (Weber & Stidham)
  • Optimal control of admission in networks
  • Queuing theory in communication system
  • Queuing theory in healthcare
  • Queuing theory in transportation system
  • Queuing theory in inventory and logistics