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: [email protected]
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�����������������������������������������������������������