• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Queuing Theory

2020/2021
Academic Year
ENG
Instruction in English
8
ECTS credits
Course type:
Elective course
When:
4 year, 1-3 module

Instructor

Course Syllabus

Abstract

This course gives a detailed introduction into queueing theory along with insights into stochastic processes and simulation techniques useful for modeling queueing systems. A queue is a waiting line, and a queueing system is a system which provides service to some jobs (customers, clients) that arrive with time and wait to get served. Examples are: - a telecommunication system that processes requests for communication; - a hospital facing randomly occurring demand for hospital beds; - central processing unit that handles arriving jobs. Queueing theory is a branch of probability theory dealing with abstract representation of such systems. It helps obtain useful and unobvious answers to questions concerning waiting times for both jobs and servers, like “how much servers should a system have, so that a customer would not have to wait more than … on average?” or “what is the mean queue length corresponding to a certain capacity utilisation level?” Such questions arise, for example, in computer systems performance evaluation. These problems require knowledge of stochastic processes, therefore the course provides a review of point processes (Poisson, Erlang etc.) and Markov chains in discrete and continuous time, paying special attention to a birth-death process, often used in queueing models. It also includes a detailed insight into simulation, because queueing problems often do not have analytic solution. The course is aimed at students interested in applied probability, Monte Carlo simulation and computer systems performance evaluation.
Learning Objectives

Learning Objectives

  • to make students familiar with stochastic process theory and its applications
  • to develop mathematical and modeling skills required for evaluating queueing systems performance
  • to give a theoretical background needed to understand academic literature on the subject
Expected Learning Outcomes

Expected Learning Outcomes

  • Знать основные параметры и характеристики систем массового обслуживания
  • Знать типичные области применения ТМО
  • уметь найти стационарное распределение марковской цепи в дискретном и непрерывном времени
  • знать основы теории случайных процессов
  • уметь рассчитать основные характеристики эффективности систем M/M/1, M/M/1/K
  • знать основные подходы к генерированию случайных чисел и симуляции случайных процессов
  • уметь реализовать имитационную модель СМО
  • уметь рассчитать основные показатели эффективности систем M/M/c, M/M/c/c, M/M/c/inf, M/M/c/K.
  • уметь подобрать подходящую модель для описания реальной ситуации
  • уметь рассчитать основные показатели эффективности системы M/G/1
  • знать определение и основные свойства производящих функций случайных величин
  • уметь оценить параметры СМО по наблюдениям
  • уметь решать простые разностные и дифференциальные уравнения
  • знать основные вероятностные модели времени наступления событий: пуассоновский поток, поток Эрланга, поток восстановления.
Course Contents

Course Contents

  • Введение. Системы массового обслуживания и их основные характеристики.
  • Разностные и дифференциальные уравнения
  • Моделирование входящего потока заявок
  • Цепи Маркова
  • Одноканальные марковские СМО
  • Имитационное моделирование процесса обслуживания
  • Многоканальные марковские СМО
  • Система M/G/1
  • Производящие функции
  • Статистическое оценивание параметров СМО
Assessment Elements

Assessment Elements

  • non-blocking test
  • non-blocking homework
  • non-blocking exam
    The exam will be held offline
Interim Assessment

Interim Assessment

  • Interim assessment (3 module)
    0.5 * exam + 0.25 * homework + 0.25 * test
Bibliography

Bibliography

Recommended Core Bibliography

  • Gorain, G. C. (2014). Introductory Course on Differential Equations. New Delhi: Alpha Science Internation Limited. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1878058
  • Performance modeling and design of computer systems : queueing theory in action, Harchol-Balter, M., 2013
  • Simulation modeling handbook : a practical approach, Chung, C. A., 2004

Recommended Additional Bibliography

  • DORDA, M., TEICHMANN, D., & GRAF, V. (2019). Optimisation of Service Capacity Based on Queueing Theory. MM Science Journal, 2975–2981. https://doi.org/10.17973/MMSJ.2019_10_201889
  • Introduction to probability models, Ross, S. M., 2010