
previous archives: 2012Fall;
2014Fall; 2015Fall;
Course
Name: Queueing Theory and Stochastic
Service Systems (#80250872, 2018Fall)
Instructor/TA

Office

Phone

Email

Office Hours

Li Xia

FIT 3618

62793029

xial@tsinghua.edu.cn

By
Appointment

 Time/Place:
Friday 9:5011:25 at Room 1111, Lecture Building
3, Tsinghua Univ.
 Required
textbook:
Mor
HarcholBalter, 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
stateofart 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.
Date

Topics

Readings

Comments/Details





0921

Introduction and examples


 Introduction
of queueing theory
 Application
area
 Counterintuitive
examples

0928

Probabilities and typical distributions
in queueing theory


 Elementary
probabilities
 Ztransform,
Laplacetransform
 Geo/MixGeo/Binomial/Poisson
distribution
 Exp/HyperExp/Erlang/Coxian distribution
 PhaseType
distribution

1012

Stochastic process, Markov chain


 Stochastic
process
 Point/Renewal/Poisson
process
 MMPP,
Markov arrival process(MAP)
 Discrete
time Markov chain

1019

Markov process and birthdeath
process

 Lecture Note [PDF]
 Reschedule
for National Holiday

 Discrete
time Markov chain, ergodicity
 Continuous
time Markov process
 Birthdeath
process and CK equation

1019

Assignment
1


 Due 1026, in English, use
Latex
 Solution [PDF]

1026

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


 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

1102

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


 M/M/1
with preemptive priority
 M/M/1
with nonpreemptive priority
 M/M/m/m
and ErlangB fromula
 M/M/m/m and ErlangC formula

1102

Assignment
2



1109

Discrete event simulation, choose
number of servers,
statedependent service


 Generate random
variables: Inversetransform method, acceptreject method
 Simulation:
event scheduling approach
 Square
root law to choose # of servers
 Load(or
state)dependent service rate

1116

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


 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/E_{k}/1, E_{k}/M/1

1123

M/G/1


 M/G/1
queue
 Residual
service time
 Inspection paradox

1123

Midterm



1123

Simulation project


 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. 1228 (Due)

1130

Queues with priority, retrial queue


 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

1130

Assignment 3



1207

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


 Series
queues
 Burke’s
theorem
 Time
reversible Markov chain
 Open
Jackson networks
 Jackson’s
theorem
 Product
form solution

1214

Closed
queueing network


 Closed Jackson
networks
 Visit
ratio by traffic equations
 Buzen’s
algorithm, computing
G(N)

1214

Assignment
4



1221

Mean value analysis method, variants
of Jackson networks


 Mean
value analysis for queueing networks
 Arrival
theorem
 Cyclic
networks
 General
Jackson networks
 BCMP
networks

1228

Application examples (12 lect, 4 example)


 Google page rank (use Markov chain)
 Aloha protocol analysis
 Storeandforward
packetswitched network (use open Jackson network model)
 Virtual circuit with
window flow control (use closed Jackson network model)

0104

Optimal control of queues，sensitivitybased
optimization, reinforcement learning


 Optimal control of queueing systems
(service rate, admission, routing probability, etc.)
 Economics
in queueing systems (pricing, utility function, game, equilibrium)
 Sensitivitybased
optimization (difference formula and derivative formula)
 Reinforcement
learning vs MDP vs optimal control
 Datadriven
vs modeldriven

xxxx

Other topics of queues


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

xxxx

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 eCommercial 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



