OR 647: Queueing Theory
School of Information Technology and Engineering
Department of Systems Engineering and Operations Research
OR 647: Queueing Theory
Dr. Frederick Wieland
Phone: 703-883-5385 (Office – MITRE/CAASD); Email: fwieland@mitre.org
Office Hours: By arrangement with instructor
TEXT: Fundamentals of Queueing Theory (3rd Edition)
Donald Gross & Carl M. Harris, John Wiley & Sons
COMPUTATIONAL PACKAGE:
QTS, Queueing Theory Software, for use in conjunction with the textbook. The software is available in the format of self-extracting Windows zip files for EXCEL and Quattro Pro 8 for Windows 95, 98 and 2000. The latest is an Enhanced Version of the software called QtsPlus by James M. Thompson, Carl Harris and Donald Gross for Excel 97 and above.
Download the software from ftp://ftp.wiley.com/public/sci_tech_med/queueing_theory/
The URL for the book errata is:
http://mason.gmu.edu/~dgross1/gross-harris/gh3.html
GRADING:
Mid-term Exam: 40% (half take-home using software, half in class – open book)
Final Exam: 40% (half take-home using software, half in class – open book -- cumulative)
Homework #1: 10%
Homework #2: 10%
COURSE OVERVIEW:
The intent of this course is to provide a modern perspective on the analysis of stochastic waiting-line systems. There will be an emphasis on the underlying random processes, ultimately leading to the development of practical strategies for dealing with the design and control of queues in a contemporary technological environment. Prerequisites are a knowledge of the fundamental elements of probability (no background in statistical inference is needed) and a general graduate level maturity in applied math. There will be a special emphasis on the numerical solution of queueing problems using the computational package.
CLASS SCHEDULE
Week Topic Assignments
1/22/02 Course overview Read Ch 1, G&H
Notation/ Measures of Effectiveness/Lindley’s Equation Download QTS software
Poisson Process and the Exponential Distribution
1/29/02 Markovian Property of the Exponential Distribution Read Ch 1, G&H
Stochastic Processes and Markov Chains
Long-run Behavior of Markov Processes
2/5/02 Birth-Death Processes Read Ch 1, G&H
Steady-state solution for the M/M/1 model
Methods of solving steady-state difference equations
2/12/02 M/M/1 Measures of Effectiveness and Waiting-time distributions Read Ch 2, G&H
Queues with Parallel Channels (M/M/c)
2/19/02 Queues with Parallel Channels (M/M/c) (cont) Read Ch 2, G&H
Queues with Parallel Channels and Truncation (M/M/c/K) Assign. #1 given
Erlang’s Formula (M/G/c/c)
2/26/02 Queues with Unlimited Service Read Ch 2, G&H
Finite-Source Queues
State-Dependent Service
Queues with Impatience
3/5/02 Transient Solution to M/M/1 Read Ch 3, G&H
Bulk Input/ Bulk Service Assign. #1 due
Takehome midterm given
3/12/02 Erlangian Models
3/19/02 Spring Break
3/26/02 MIDTERM: In-class portion Takehome midterm due
4/2/02 Series Queues Read Ch 4, G&H
Open Jackson Networks/ Closed Jackson Networks
4/9/02 Jackson Networks Read Ch 5, G&H
M/G/1 queues Assign. #2 given
4/16/02 G/M/1 queues Read Ch 6.2,6.3,6.6 G&H
G/G/1 queues
4/23/02 Matrix Geometric Methods and Call Center Example Assign. #2 due
M/D/c queues Read 7.1,7.2,7.4 G&H
Design of queues
4/30/02 Bounds and Approximations Takehome final given
Simulation
Last Day of Class!
5/7/02 Final exam: In-class portion, 7:30-10:15 Takehome final due
Poisson probabilities properties and simple calculations more extensive calculations
Erlang probabilities properties and simple calculations more extensive calculations
Markov chains basic theory and solution to 3x3 solution to more than 3x3
Linear difference eqns formulation and solution to 3rd order solution when order > 3
Prob. difference eqns formulation and solution to 3rd order solution when order > 3
Finite birth/death soln approx. Nmax = 4 Nmax > 4
Infinite birth/death soln soln when in closed form complete soln
Little’s Law how to use automatic calculation
M/M/1 calculate all major measures --
M/M/c c=2, all formulas c > 2
M/M/c/K c=1, all K, all formulas c > 1
M/G/c/c all G, c < 4 c ³ 4
M/G/¥ all G --
Finite Sources c = 1 only c > 1
Balking/Reneging M/M/1 only, simple fns. --
M[X]/M/1 simple distrib for X complete
M[K]/M/1 K £ 3 K > 3
M/M[K]/1 (1): K = 2 K > 2
M/Ek/1 all k: P-K formula, etc. everything else
Ek/M/1 as G/M/1, etc.
M/M/c Queues in Series basic formulation; MOEs for c=1 c > 1
Single-Server N/Ws two nodes and all MOEs more than 2 nodes
Multi-Server N/W traffic eqns only remainder
Mean Value Analysis traffic eqns only everything
M/G/1 P-K formula and related MOEs --
M/D/1 P-K formula and related MOEs complete solution
G/M/1 formulation & simple solution more complex solution
D/M/1 solution --
G/G/1 simple transform analysis --
M/D/c simple transform analysis remainder
G/G/c Bounds complete --
Heavy-Traffic Approxs. complete
Design of Queues simple optimizations