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

!!! ВНИМАНИЕ !!! Этот раздел будет состоять из нескольких страниц, остальные из которых в данный момент находится в стадии написания. Но уже написанная часть достаточно интересная, поэтому я считаю, что будет полезно уже сейчас сделать её доступной читателям

Давно-давно, когда мы были студентами, этот раздел математики у нас выпил немало студенческой крови. А между тем, этот раздел чрезвычайно интересный!

Датский инженер Агнер Эрланг работал в телефонной компании и занялся в начале XX в. рассчётами, касающимися работы телефонной станции: какая доля попыток позвонить не будет успешной, т.к. заняты все линии, сколько нужно иметь линий связи, если абоненты могут дожидаться освобождения линии или если будут прекращать попытку. В технике фамилия датского инженера осталась в виде единицы измерения абонентской нагрузки Эрланг (Эрл).

1 Эрл - это занятие одной телефонной линии в течение 1 часа.

Позже возник целый раздел математики - Теория Массового Обслуживания, который позволяет решать различные задачи, касающиеся далеко не только телефонии.


Я не ставлю себе целью написать целый учебник по ТМО. Такого роду материалов в интернете много. «Изюминкой» моей статьи должен стать интерактивный онлайн-расчётник, который позволит менять исходные данные и смотреть, как будет меняться поведение системы.

Главные понятия Теории:

Система массового обслуживания (СМО)
объект, принимающий заявки и осуществляющий их обслуживание. Для обслуживания в состав СМО может входить один или несколько приборов
Сеть массового обслуживания (СеМО)
несколько СМО, между которыми заявки циркулируют. Заявка поступает в какую-либо СМО сети, а получив обслуживание, может поступить в другую СМО сети либо покинуть её.
Заявка
объект, поступающий в СМО и требующий обслуживания. Также может называться требованием, запросом или как-то ещё.
Прибор
часть СМО, которая осуществляет обслуживание заявки. Также может называться обслуживающим устройством, каналом, либо это может быть работник или целая бригада.
Очередь
множество заявок, поступивших в СМО, обслуживание которых ещё не началось по причине занятости всех приборов в системе.
Накопитель
Часть СМО, в которой содержится очередь.

Исходные данные для рассчётов в ТМО

λ - интенсивность потока заявок
среднее количество заявок, поступающих в систему в течение заданного количества времени. Единица измерения - заявок в час (час-1)
μ - интенсивность обслуживания
среднее количество заявок, которое прибор может обслужить в течение заданного количества времени. Единица измерения - заявок в час (час-1)
n - количество обслуживающих приборов
количество приборов в составе СМО, каждый из которых может обслуживать заявки. Поступающая заявка обслуживается в любом свободном приборе, т.е. все приборы работают параллельно.
Характер потока заявок и обслуживания
По своей сути, закон распределения случайной величины времени между поступлением заявок (если речь идёт о потоке заявок) или продолжительности обслуживания конкретной заявки (если речь идёт об интенсивности обслуживания). Может иметь экспоненциальное, нормальное, равномерное или ещё какое угодно распределение. Поток заявок может вообще иметь детерминированный характер (по расписанию), а продолжительность обслуживания может быть и константной
m - Размер накопителя
Размером накопителя определяется характер СМО: при нулевом размере заявка получает отказ в обслуживании при отсутствии свободных приборов. Если накопитель бесконечный, все заявки будут ожидать обслуживания по мере освобождения приборов. Если же размер накопителя конечный, то при наличии свободных мест заявка помещается в очередь, а при заполнении накопителя заявка получает отказ в обслуживании

Основные показатели работы СМО

ρ - коэффициент загрузки
отношение интенсивности потока заявок к суммарной интенсивности обслужвания. Коэффициент загрузки позволяет определить, будет ли система справляться с задачами или из-за перегрузки будет неработоспособной.
Вероятность наличия в системе n заявок, вероятность простоя системы
наибольшее количество задач ТМО требует найти оптимальное количество обслуживающих приборов или размер накопителя.
Вероятность и среднее время ожидания
доля заявок, которые попадают в очередь, среднее время пребывания заявок в ожидании начала обслуживания
Вероятность отказа
доля заявок, получающих отказ в обслуживании. Неактуально для систем с бесконечным накопителем.

Какие задачи позволяет решать ТМО?

Вот несколько типичных задач, которые могут быть решены с применением аппарата теории массового обслуживания. На этой странице скоро появится расчётник, который позволит найти решение этих задач.

Пора уже что-то посчитать!

Вычислительные мощности, доступные каждому в XXI веке колоссальны, и позволяют легко и непринуждённо проводить ресурсоёмкий расчёт - имитационное моделирование. В таблице ниже осуществляется моделирование простенькой одиночной системы массового обслуживания. Можно изменять любые из исходных данных и наблюдать, как система отзывается. Можно, например, увеличить интенсивность потока заявок и наблюдать, как система будет «утопать» в заявках (или увеличится поток отказов, если размер накопителя конечен). А вслед за этим можно увеличить количество приборов в системе и наблюдать, как показатели работы придут в норму. В этом расчёте предельная длина очереди равна 1000. Для большинства применений это можно считать бесконечно большим накопителем, однако следует помнить, что если в накопителе окажется больше тысячи заявок, расчёт будет некорректным.

Параметр Величина Пояснение
Исходные данные
λ в час - Интенсивность потока заявок
Pμ(t) Эксп.
Эрл.		 Закон распределения времени обслуживания: экспоненциальный.
Подробнее о законах распределения
μ в час - Интенсивность потока обслуживания (каждым прибором)
25% за минут 50% за минут 99% за минут
50% в интервале минут 95% в интервале минут
n Количество каналов обслуживания (не более 50)
Результаты моделирования (на момент)
t Время моделирования
S Состояние СМО, т.е. количество заявок на обслуживании + в накопителе
S-n Длина очереди
Статистика, показатели работы системы
— Количество поступивших заявок
p0 Вероятность простоя СМО
P1-n Загруженность обслуживающих приборов
SMAX Максимальное количество заявок в системе за время моделирования
pW Вероятность ожидания
TW Среднее время ожидания, мин.
TWmax Максимальное время ожидания, мин.
Pn Распределение вероятностей пребывания СМО в различных состояниях
TW Распределение времени ожидания в очереди

Если интересно, см. подробное описание математической модели в этой таблице. Даже такая модель позволяет делать интересные наблюдения. Например, можно сравнить несколько СМО с одинаковой производительностью μ×n, обслуживающих одинаковый поток заявок λ, но содержащих различное количество обслуживающих приборов n. В зависимости от того, стремимся ли мы сократить количество обслуживающих аппаратов или же вероятность ожидания, выгодным будет либо наличие одного высокопроизводительного прибора, или десятка низкопроизводительных. Также видно, что среднее арифметическое времени ожидания - величина коварная. Надо будет сделать расчёт медианной величины...

См. также:

Яндекс.Метрика