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

Office

Phone

Email

Office Hours

Li Xia

FIT 3618

62793029

xial@tsinghua.edu.cn

By
Appointment

 Time/Place:
Friday 15:2016:55 at Room 6B306, Lecture
Building 6, 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: 20%
 Final Project: 40%
 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 seriously prohibited.
Date

Topics

Readings

Comments/Details





0918

Introduction and examples


 Introduction
of queueing theory
 Application
area
 Counterintuitive
examples

0925

Probabilities and typical
distributions in queueing theory


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

1009

Stochastic process, Markov chain


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

1010

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

1010

Assignment
1


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

1016

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

1023

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

1023

Assignment
2



1030

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

1106

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

1106

Assignment simulation

 Assignment simulation [PDF]


1113

M/G/1


 M/G/1
queue
 Residual
service time
 Inspection paradox

1113

Midterm



1120

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

1120

Assignment 3



1127

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

1127

Final
project selection

 Project
Description
[PDF]

 No group, select an application area
of queueing theory, do literature review/model
formulation/analysis and optimization/ simulation, finish a brief
paper and do presentation on
1225 (Due)

1204

Closed
queueing network


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

1204

Assignment
4



1211

Mean value analysis method, variants
of Jackson networks


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

1218

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)

1225

Optimal control of queues and
sensitivitybased method


 Sensitivitybased
optimization (difference equation and derivative equation)
 Service rate control of closed networks
 Admission
control of open networks

1225

Final
Project Presentation


 Presentation 15min, discussion 5min
 Actively participate the discussion
 Everyone asks question and discusses

0101

No class



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



