4.12. Простейшие системы массового обслуживания
1. n-канальная система массового обслуживания с отказами (задача Эрланга).
Это
одна из первых задач теории массового
обслуживания. Она возникла из нужд
телефонии и была решена в начале 20 века
датским ученым Эрлангом. Задача ставится
так: имеется n
каналов (линий связи), на который поступает
поток заявок с интенсивностью λ.
Поток обслуживаний имеет интенсивность
μ
(величина, обратная среднему времени
обслуживания
).
Найти финальные вероятности состояний
системы массового обслуживания, а также
характеристики ее эффективности:
А – абсолютную пропускную способность, т.е. среднее число заявок, обслуживаемых в единицу времени;
Q – относительную пропускную способность, т.е. среднюю долю пришедших заявок, обслуживаемых системой;
–вероятность
отказа, т.е. того, что заявка покинет
систему необслуженной;
–среднее
число занятых каналов.
Решение.
Состояния системы S будем нумеровать по числу заявок, находящихся в системе (в данном случае оно совпадает с числом занятых каналов):
–в
системе нет ни одной заявки,
– в системе находится одна заявка (один
канал занят, остальные – свободны), …,
– в системе находитсяk
заявок (k
каналов заняты, остальные свободны), …,
– в системе находитсяn
заявок (все каналы заняты). Граф состояний
системы массового обслуживания
представлен на рис. 19.
Воспользуемся уже готовыми формулами для финальных вероятностей в схеме гибели и размножения. Получим:
Обозначим отношение λ к μ через ρ:
.
Тогда:
.
Последняя формула называется формулой Эрланга.
Исходя из полученной формулы, найдем все остальные характеристики системы массового обслуживания:
.
Отсюда найдем относительную пропускную способность – вероятность того, что заявка будет обслужена:
.
Абсолютную пропускную способность получим, умножая интенсивность потока заявок на λ на Q:
Среднее число занятых каналов можно рассчитать по следующей формуле:
.
2. Одноканальная система массового обслуживания с неограниченной очередью.
Пусть
имеется одноканальная систем массового
обслуживания с очередью, на которую не
наложено никаких ограничений. На эту
систему поступает поток заявок
интенсивностью λ;
поток обслуживания имеет интенсивность
μ,
обратную среднему времени обслуживания
.
Требуется найти финальные вероятности
состояний системы массового обслуживания
и характеристики ее эффективности:
–среднее
число заявок в системе,
–среднее
время пребывания заявки в системе,
–среднее
число заявок в очереди,
–среднее
время пребывания заявки в очереди,
–вероятность
занятости канала (степень занятости
канала).
Решение.
Вследствие неограниченности очереди A=Q=1.
Состояния
системы S
будем нумеровать по числу заявок,
находящихся в системе:
– канал свободен,
– канал занят, очереди нет, …,
– канал занят, в очередиk-1
заявок. Граф состояний системы массового
обслуживания представлен на рис. 20.
Воспользуемся уже готовыми формулами для финальных вероятностей в схеме гибели и размножения. Получим:
Получили сумму бесконечного ряда. Ряд – геометрическая прогрессия. При ρ<1 ряд сходится (бесконечная убывающая геометрическая прогрессия со знаменателем ρ). При ρ≥1 ряд расходится.
Предположим, что ρ<1. Тогда:
,
Отсюда:
.
Тогда
,
,
…,
.
Найдем
среднее число заявок
.
Случайная величинаZ
– число заявок в системе – имеет
возможные значения 0, 1, 2, 3, …, k,
… с вероятностями
Ее математическое ожидание равно:
.
Подставив
в формулу, получим:
.
Вынесем ρ(1-ρ) за знак суммы:
.
–производная
поk.
.
Отсюда
.
Так
как ρ<0, то сумма, стоящая под знаком
дифференциала равна
,
а ее производная
.
Значит:
.
Применяя формулу Литтла, получим:
Найдем
среднее число заявок в очереди
.
Число заявок в очереди равно общему
числу заявок в системе минус число
обслуживаемых заявок. Значит, среднее
число заявок в очереди равно среднему
числу заявок в системе минус среднее
число заявок под обслуживанием. Среднее
число заявок под обслуживанием может
быть 0 или 1. Математическое ожидание
такой случайной величины равно вероятности
того, что канал занят:
.
.
Следовательно, общее число заявок под обслуживанием равно ρ. Отсюда:
.
Окончательно:
.
По второй формуле Литтла найдем:
.
Мы рассмотрели только два простейших примера, об остальных можно прочитать в научной литературе.