Теория массового обслуживания (ТМО)

1. Теория массового обслуживания (ТМО)

Основные понятия, модели и применение

2. Определение

Теория массового обслуживания – раздел математики, изучающий
процессы обслуживания требований в системах с очередями.
Цель: выработка рекомендаций по рациональному построению СМО,
рациональной организации их работы и регулированию потока заявок для
обеспечения высокой эффективности функционирования СМО.

3. В сфере производства и обслуживания примерами СМО могут служить:

различные системы
связи (в том числе
телефонные
станции),
погрузочноразгрузочные
комплексы (порты,
товарные станции),
автозаправочные
станции,
пункты пропуска
через границу,
пункты
таможенного
оформления,
парикмахерские,
билетные кассы,
пункты обмена
валюты, ремонтные
мастерские,
больницы и т.д.

4. Случайные процессы и потоки событий

В качестве аппарата теории систем массового обслуживания используют понятия
теории случайных величин, а также теории случайных процессов.
Случайным процессом, или случайной функцией S(t), называется
функция, которая каждому моменту времени t; из некоторого временного
промежутка ставит в соответствие единственную случайную величину S(t).
Если состояния системы S изменяются во времени случайным образом,
то будем говорить, что в системе S протекает случайный процесс.
По множеству состояний системы S протекающий в ней случайный процесс может
быть дискретным или непрерывным.
Случайный процесс, протекающий в системе S , называется марковским, если
обладает свойством отсутствия последействия, или отсутствия памяти, т.е. для
любого фиксированного момента времени t0 вероятность состояния в будущем (при )
зависит только от состояния системы в настоящем (при ) и не зависит от того, как
развивался этот процесс в прошлом (при ).

5.

Потоком называется последовательность событий,
наступающих одно за другим, в общем случае, в
случайные моменты времени.
События в потоке называются однородными, если они
различаются только по моментам времени их
наступления, и неоднородными в противном случае.
Поток событий называется потоком без последействия, или
потоком без памяти, если для любой пары
непересекающихся промежутков времени число событий
за один из этих промежутков не зависят от числа событий
за другой.
Очевидно, что регулярный поток событий, в котором
события наступают через строго определенные промежутки
времени, не обладает свойством отсутствия последействия,
поскольку регулярность этого потока порождает
последействие.

6. Основные понятия ТМО

Система массового обслуживания (СМО) – объект исследования
(например, call-центр, супермаркет).
Входящий поток заявок – клиенты, звонки, пакеты данных.
Очередь – заявки, ожидающие обслуживания.
Канал обслуживания – сервер, оператор, касса.
Дисциплина обслуживания:
FIFO (First In, First Out)
LIFO (Last In, First Out)
Приоритетное обслуживание

7. Классификация СМО (по Кендаллу)

Формат: A/B/C/D/E/F
• A – распределение времени между заявками (например, M –
экспоненциальное).
• B – распределение времени обслуживания (M – экспоненциальное, G –
произвольное).
• C – количество каналов обслуживания.
• D – ёмкость очереди (максимальное число заявок).
• E – дисциплина очереди (FIFO, LIFO).
• F – размер популяции клиентов.
Пример: *M/M/1/∞/FIFO* – одноканальная СМО с экспоненциальным
временем между заявками и обслуживанием, бесконечной очередью и
дисциплиной FIFO.

8. Основные характеристики СМО

• Интенсивность входящего потока (λ) – среднее число заявок в
единицу времени.
• Интенсивность обслуживания (μ) – среднее число заявок,
обслуживаемых за единицу времени.
• Коэффициент загрузки (ρ = λ/μ) – показывает загруженность
системы.
• Среднее время ожидания (W) и средняя длина очереди (L).

9. По числу каналов

Классификация систем массового
обслуживания
Одноканальные
• Имеется один канал
обслуживания
Многоканальные
• Количество каналов n ≥ 2
Могут состоять из
• однородных каналов
• разнородных каналов
• Каналы отличаются длительностью
обслуживания одной заявки.
Практически время обслуживания каналом одной заявки T об является непрерывной случайной
величиной. Однако при условии абсолютной однородности поступающих заявок и каналов
время обслуживания может быть и величиной постоянной (T об = const).

10. По дисциплине обслуживания СМО подразделяют на три класса

1. СМО с отказами. Заявка, поступившая на вход СМО в
момент, когда все каналы заняты, получает «отказ» и
покидает СМО.
Чтобы эта заявка все же была обслужена, она должна снова
поступить на вход СМО и рассматриваться при этом как
заявка, поступившая впервые.
2. СМО с ожиданием (неограниченным ожиданием или
очередью).
В таких системах заявка, поступившая в момент занятости
всех каналов, становится в очередь и ожидает
освобождения канала, который примет ее к обслуживанию.

11.

3. СМО смешанного типа (с ограниченным
ожиданием).
Это такие системы, в которых на пребывание заявки
в очереди накладываются некоторые ограничения.
Ограничения ожидания могут касаться времени пребывания заявки в
очереди, по истечению которого она выходит из очереди и покидает
систему, либо касаться общего времени пребывания заявки в СМО

12. Простейшая модель M/M/1

• Одноканальная система с экспоненциальным распределением.

13. Многоканальная модель M/M/n

14. Применение ТМО

1.Логистика – оптимизация складов и транспорта.
2.IT – балансировка нагрузки серверов.
3.Медицина – планирование работы больниц.
4.Розничная торговля – управление очередями в магазинах.

15. Пример расчета (M/M/1)