OR 647: Queueing Theory

School of Information Technology and Engineering

Department of Systems Engineering and Operations Research

SPRING 2002

 

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%

 

COURSEOVERVIEW:

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

 

 

OR 647 Course Coverage

 

Problem�������������������������������� What you need to know������������������������������������� What the computer does

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