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

 

 

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

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

previous archives:  2012-Fall; 2014-Fall;

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

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

Instructor/TA

Office

     Phone

Email

Office Hours

Li Xia

FIT 3-618

    62793029

xial@tsinghua.edu.cn

By Appointment

  • Time/Place: Friday 15:20-16:55 at Room 6B306, Lecture Building 6, 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: 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.
  • Course Calendar:

Date

Topics

Readings

Comments/Details

 

 

 

09-18

Introduction and examples

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

09-25

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

10-09

Stochastic process, Markov chain

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

10-10

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

10-10

Assignment 1

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

10-16

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

10-23

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

10-23

Assignment 2

  • Due 11-06
  • Solution [PDF]

10-30

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

11-06

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

11-06

Assignment simulation

  • Assignment simulation [PDF]
  • Due 11-20

11-13

M/G/1

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

11-13

Midterm

  • Midterm
  • 1-1.5 hour test

11-20

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

11-20

Assignment 3

  • Due 11-27
  • Solution [PDF]

11-27

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

11-27

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 12-25 (Due)

12-04

Closed queueing network

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

12-04

Assignment 4

  • Due 12-11

12-11

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

 

 

12-18

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)

12-25

Optimal control of queues and sensitivity-based method

  • Lecture Note [PDF]
  • Sensitivity-based optimization (difference equation and derivative equation)
  • Service rate control of closed networks
  • Admission control of open networks

12-25

Final Project Presentation

 

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

01-01

No class

  • New year holiday
  •  

xx-xx

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
  • ……

xx-xx

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

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

 

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