Системы массового обслуживания: понятия, примеры, модели

1.

Системы массового
обслуживания: понятия, примеры,
модели

2.

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

3.

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

4.

СМО
Обслуживание — это непосредственное взаимодействие с клиентом,
которое направлено на удовлетворение его спроса.
Системой массового обслуживания (СМО) называется система, в
которой:
• возникает массовые требования на выполнения каких-либо видов
услуг
• происходит удовлетворение этих требований — обслуживание
Главной особенностью процессов массового обслуживания является их
случайность. Выделяются две взаимодействующие стороны, одна из
которых обслуживает, а вторая выступает в качестве обслуживаемой.
Присутствие случайности в поведении одной из сторон приводит к
случайному протеканию всего процесса обслуживания. Причины
случайности заключаются в массовом характере потребностей, а также
в случайности работы обслуживающей системы.

5.

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

6.

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

7.

СМО
• Примерами СМО могут служить:
автобусный маршрут и перевозка
пассажиров; производственный конвейер
по обработке деталей; влетающая на чужую
территорию эскадрилья самолетов, которая
«обслуживается» зенитками ПВО; ствол и
рожок автомата, которые «обслуживают»
патроны; электрические заряды,
перемещающиеся в некотором устройстве
и т. д.

8.

СМО
Примеры процессов массового обслуживания
• обслуживание покупателей в сфере
мелкооптовой и розничной торговли;
• транспортное обслуживание;
• работа телекоммуникационных сетей;
• медицинское обслуживание;
• гостиничный бизнес;
• обслуживание в бистро, кафе, ресторанах;
• обработка документов в системе управления;
• туристический бизнес и многие др.

9.

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

10.

Пример
• К примеру, пусть сказано: «заявки в среднем приходят в
количестве 5 штук в час». Это означает, что времена
между приходом двух соседних заявок случайны,
например: 0.1; 0.3; 0.1; 0.4; 0.2, как это показано на рис.,
но в сумме они дают в среднем 1 (обратите внимание,
что в примере это не точно 1, а 1.1 — но зато в другой час
эта сумма, например, может быть равной 0.9); и только за
достаточно большое время среднее этих чисел станет
близким к одному часу.

11.

• Результат (например, пропускная
способность системы), конечно, тоже будет
случайной величиной на отдельных
промежутках времени. Но измеренная на
большом промежутке времени, эта
величина будет уже, в среднем,
соответствовать точному решению. То есть
для характеристики СМО интересуются
ответами в статистическом смысле.

12.

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

13.

Система массового обслуживания
считается заданной, если
определены:
3) время обслуживания требования каждым прибором, которое
является случайной величиной и характеризуется некоторым законом
распределения;
4) дисциплина ожидания, т. е. совокупность правил,
регламентирующих количество требований, находящихся в один и тот
же момент времени в системе. Система, в которой поступившее
требование получает отказ, когда все приборы заняты, называется
системой без ожидания. Если требование, заставшее все приборы
занятыми, становится в очередь и ожидает до тех пор,
пока освободиться один из приборов, то такая система называется
чистой системой с ожиданием. Система, в которой требование,
заставшее все приборы занятыми, становится в очередь только в том
случае, когда число требований, находящихся в системе, не превышает
определенного уровня (в противном случае происходит потеря
требования), называется смешанной системой обслуживания;

14.

Система массового обслуживания
считается заданной, если
определены:
5) дисциплина обслуживания, т. е. совокупность правил, в
соответствии с которыми требование выбирается из очереди для
обслуживания. Наиболее часто на практике используются следующие
правила:
- заявки принимаются к обслуживанию в порядке очереди;
- заявки принимаются к обслуживанию по минимальному времени
получения отказа;
- заявки принимаются к обслуживанию в случайном порядке в
соответствии с заданными вероятностями;
6) дисциплина очереди, т.е. совокупность правил, в соответствии с
которыми требование отдает предпочтение той или иной очереди
(если их не сколько) и располагается в выбранной очереди.
Например, поступившее требование может занять место в самой
короткой очереди; в этой очереди оно может расположиться
последним (такая очередь называется упорядоченной), а может
пойти на обслуживание вне очереди. Возможны и другие варианты.

15.

Классификация систем массового
обслуживания
СМО могут быть двух видов:
♦ СМО с отказами;
♦ СМО с ожиданием (т. е. с очередью).
Обслуживание в системах с очередью может
иметь различный характер:
Ø обслуживание может быть упорядоченным;
Ø обслуживание в случайном порядке;
Ø обслуживание с приоритетом, при этом
приоритет может быть с прерыванием и без
прерывания.

16.

Системы с очередью делятся на:
• системы с неограниченным ожиданием, при
этом поступившая в СМО задача становится в
очередь и ждет обслуживания. Рано или
поздно она будет обслужена;
• системы с ограниченным ожиданием, при
этом на заявку в очереди накладываются
ограничения, например ограниченное время
пребывания в очереди, длина очереди, общее
время пребывания в СМО. В зависимости от
типа СМО для оценки эффективности могут
быть применены разные показатели.

17.

Классификация
• Для СМО с отказами используются следующие
показатели эффективности:абсолютная
пропускная способность А – среднее число
заявок, которое может быть обслужено в
единицу времени;
• относительная пропускная способность Q –
относительное среднее число заявок. При этом
относительную пропускную способность
можно найти по формуле
Q=A/ λ
где λ – это интенсивность поступления заявок в
СМО.

18.

Классификация
Для СМО с ожиданием абсолютная пропускная
способность А и относительная пропускная
способность Q теряют смысл, но важными
становятся другие характеристики:
Ø единица времени ожидания в очереди;
Ø среднее число заявок в очереди;
Ø среднее время пребывания в системе.
Для СМО с ограниченной очередью интересны
обе группы характеристик.

19.

Классификация

20.

Описание модели
На вход n-канальной СМО с m-очередью поступает простейший поток заявок с
интенсивностью λi в зависимости от состояния системы.
Интенсивность простейшего потока обслуживания каналом или каналами μi в
зависимости от состояния системы.
Если заявка застаёт все каналы свободными, то она принимается на
обслуживание и обслуживается одним из n каналов.
После окончания обслуживания один канал освобождается.
Если вновь прибывшая заявка застаёт в системе свободным хотя бы один
канал, то она принимается на обслуживание одним из свободных каналов и
обслуживается до конца.
Если заявка застаёт все каналы занятыми, то она становится в очередь и
«терпеливо» ждёт своего обслуживания.
Дисциплина очереди естественная: кто раньше пришёл, тот раньше и
обслуживается. Максимальное число мест в очереди m.
Если вновь прибывшая заявка застаёт в очереди m-заявок, то она получает
отказ и исключается из обслуживания.
Состояние рассмотренной системы будем связывать с числом заявок,
находящихся в системе.

21.

Граф состояний
Состояние рассмотренной системы будем связывать с числом заявок, находящихся в системе.
Рассмотрим множество состояний системы:
S0 — в системе нет ни одной заявки, все каналы свободны;
S1 — в системе имеется одна заявка, она обслуживается каналами и уходит с определённой
интенсивностью;
S2 — в системе имеется две заявки, они обслуживаются каналами и уходят с определённой
интенсивностью;
…;
Sn — в системе имеется n-заявок, они обслуживаются n-каналами и уходят с определённой интенсивностью;
Sn+1 — в системе имеется (n+1)-заявок, они обслуживаются n-каналами и уходят с определённой
интенсивностью;
…;
Sn+m-1 — в системе имеется (n+m-1)-заявок, они обслуживаются n-каналами и уходят с определённой
интенсивностью;
Sn+m — в системе имеется (n+m)-заявок, они обслуживаются n-каналами и уходят с определённой
интенсивностью.

22.

Система дифференциальных
уравнений
• Система дифференциальных уравнений,
описывающих поведение системы, имеет вид:

23.

Жду Ваши труды на СДО))))