Queuing Theory
EP2930  ( HF2000)
(Computer Networks, Master of Science Program)

Credits: 7,5
ECTS Credits: 7,5
Level: D
Grading: A-F
Language: Engelska / English
Time: Period 1, 2010/11
Coordinator: Armin Halilovic
office: 5046
tel. 08-790 4810
www.sth.kth.se/armin
armin@kth.se

Aim

After completion of the course the student should be able to:

* Define and explain the basic concepts of the theory Markov processes, M/M/m, M/M/m/K, and M/M/m/K/C queuing systems.
* Derive and apply main formulas for some properties (such as stationary probabilities, average waiting and system time, expected number of customers in the queue, etc.) of M/M/m, M/M/m/K, and M/M/m/K/C queuing systems.
* Calculate traffic intensity, blocked traffic, and the utilization of some queuing systems.
* Solve some simple problems on queuing networks.
* Analyze and solve problems using computer aid (Maple, Matlab, or Mathematica)

Content:

* Stochastic processes. Markov chains in discrete and continuous time. Chapman-Kolmogorov equations. Stationary probabilities. Poisson process. Birth-death processes.
* Basic concepts in queuing theory. Little’s theorem.
* Arrival processes and service time. Queuing disciplines. Stationary probabilities. Offered load (traffic). Blocked load. Effective load. Utilization. Blocking probability.
* Markovian wait systems.
* M/M/m: Queuing systems with m servers, infinite number of waiting positions, and infinite number of customers.
* M/M/m/K: queuing system with m servers, limited number (=K) waiting positions, and infinite number of customers.
* M/M/m/K/C: queuing system with m servers, limited number (=K) waiting positions, and limited number of customers (=C).
* Markovian loss systems: Erlang’s loss system, Engset’s loss system, Binomial (Bernoulli’s) loss system.
* Semi-markovian M/G/1 and G/M/l queuing systems. Pollacsek-Khinchin formula.
* Survey on open and closed Jackson queuing networks.

Prerequisites
The student should posses a basic knowledge in calculus, linear algebra and mathematical statistics.

Requirements
Passed exam (TEN1; 4.5 c.), grading A-F.
Passed lab work (RED1; 3 cr.), grading P/F.

Text books and recommending reading:
QUEUEING MODELLING FUNDAMENTALS,
Ng Cheee Hock, John Wiley & Sons LTD
Recommending reading (PDF)
--------------------------

Queueing theory books ( FREE ) online

==================

A little Swedish -English glossary of basic terms in queueing theory

==================
EXERCISES AND REPETITION BEFORE THE EXAMINATION

Prelimineries:
P1. Logic, Algebra of Sets
P2. Probability
P3. Laplace transforms P3.
P4. Geometric series. Taylor series

Formula Tables
T1. Table with some discrete and continuous random variables
T2. Table with Laplace transforms
T3. Table with Z-transforms

Exercises:
1a) Discrete -Time Markov chains
1b) Poisson Process
2) Continuous -Time Markov chains. Q matrix
2b) Birth-and-Death Process
3) M/M/1 system
4) M/M/1 system
4b) M/M/m system
5) M/M/m/K system (m servers, K waiting positions)
6) M/M/m/K system (m servers, K waiting positions)
7) M/M/m/K/C system (m servers, K waiting positions, C customers )
8) ERLANG LOSS SYSTEM (m servers, 0 waiting positions, "unlimited number of customers")
9) ENGSET LOSS SYSTEM (m servers, 0 waiting positions, C customers, C>m)
10) BINOMIAL (BERNOULLI) LOSS SYSTEM (m servers, 0 waiting positions, C customers, C<=m )
11) MIXED PROBLEMS
12) M/G/1 queueing system
13) Queueing networks

==================

COMPUTER ASSIGNMENTS (inlämningsuppgifter) , (RED1; 3cr.) :

Group work is allowed only for the first assignment: a maximum of two students can work together on the assignment 1.

Assignment #1
Assignment #2
Assignment #3
Assignment #4

Date and time for presentation:
12 Oct 2010, 13:15-15:00, in room 7097D
or 14 Oct 2010, 13:15-15:00, in room 7097D.
Questions related to lab work will be included in the exam.

====================

TESTS AND BONUS POINTS

Two "in-class" tests will be organized during the course.

	Date	Time	room
Test1	21 Sep	10:00-12:00	2093
Test2	7 Oct	13:15-15:00	5023

1 . If you pass Test1 [Test2], then you get 2 "bonus" points that will be added to the results of your final written examination ( and you need not answer question 1 [ question 2 ] on the exam ).
2 . Earned bonus points are valid until 31 Aug 2011.
-------------------------------------

The old tests with solutions:
TEST 1:
test 1, version A, 21 Sep 10
test 1, version B, 21 Sep 10
=========================
TEST 1:
test 1, version A, 17 Sep 09
test 1, version B, 17 Sep 09

TEST2:
test 2, version A, 8 Oct 09
test 2, version B, 8 Oct 09

TEST 1:
test 1, version A, 18 Sep 08
test 1, version B, 18 Sep 08

  TEST 2:
test 2 , version A, 7 Oct 08
test 2, version B, 7 Oct 08

=========================
TEST 1: test 1: 19 Sep 06
TEST 1: test 1: Sep 05
--------------------------------------
TEST 2: test 2: 12 Oct 07
TEST 2A: test 2A: 6 Oct 06
=======================
TEST 2B: test 2B: 6 Oct 06
TEST 2: test 2: Oct 05

====================

WRITTEN EXAMINATION (TEN1; 4.5cr.)

Datum: ..............Time: ...........

Instructions:
1. Students ARE allowed to use calculators and the textbook.
2. Students are NOT allowed to use their own tables of mathematical formulas on the exam.
3. Use of any communication device when taking this examination is strictly prohibited.
4. Grading: Credit will be given or presentation and methods of solutions.
5. A maximum of 30 points can be earned. Points can also be deducted for unsubstantiated answers.
At least 15 points are required to pass the exam.

Grading scale: The total number of possible points is 30.
27 -30 points are required for an “A” grade;
24 -26 points are required for a “B” grade;
21 -23 points are required for a “C” grade;
18 - 20 points are required for a “D” grade;
15 - 17 points are required for an “E” grade;
14 points result in a “Fx”;
0-13 points result in a “F” grade.

There will be a complementary exam for those students who receive 14 points (Fx ) on the exam
The complementary exam will be different from the regularly scheduled exam, though it will cover the same material.
The old exams