Queuing Theory

2022/2023

Academic Year

RUS

Instruction in Russian

10

ECTS credits

Delivered by:

School of Software Engineering

Type:

Elective course

When:

4 year, 1-3 module

Instructor

Furmanov, Kirill K.

Программа дисциплины

Аннотация

Курс содержит подробное введение в теорию массового обслуживания и знакомит слушателей с подходами к аналитическому и симуляционному исследованию систем массового обслуживания (СМО), то есть систем, обрабатывающих поток заявок, обслуживание которых требует времени. Примеры СМО: (1) сервер, отвечающий на запросы пользователей; (2) больница, обслуживающая поступающих пациентов; (3) телекоммуникационная система, предоставляющая услуги связи; (4) коммутатор, пересылающий пакеты по компьютерной сети. Как правило, моменты поступления и продолжительность обслуживания заявок считаются случайными, поэтому при моделировании используется теория случайных процессов - её основы также излагаются в настоящем курсе. Для изучения процессов, аналитическое исследование которых практически не возможно, рассматриваются методы имитационного моделирования.

Цель освоения дисциплины

• познакомить студентов с теорией случайных процессов и её приложениями
• дать инструментарий, пригодный для описания и моделирования систем массового обслуживания
• дать теоретические знания, которые нужны для понимания академической литературы, затрагивающей проблемы массового обслуживания

Планируемые результаты обучения

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

Содержание учебной дисциплины

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

Элементы контроля

• Первая контрольная работа
• Первое домашнее задание
• Экзамен
• Вторая контрольная работа
• Второе домашнее задание

Промежуточная аттестация

• 2022/2023 учебный год 1 модуль
  0.6 * Первая контрольная работа + 0.4 * Первое домашнее задание
• 2022/2023 учебный год 3 модуль
  0.6 * Экзамен + 0.2 * Вторая контрольная работа + 0.2 * Второе домашнее задание

Список литературы

Рекомендуемая основная литература

• 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

Рекомендуемая дополнительная литература

• 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

Авторы

• Фурманов Кирилл Константинович