Простейшие системы массового обслуживания и их характеристики

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

 

Задача Эрланга

Рассмотрим одну из первых по времени «классических» задач теории массового обслуживания; эта задача возникла из практических нужд телефонии и была решена в начале нашего века датским математиком Эрлангом. Задача ставится так: имеется n каналов, на которые поступает поток заявок с интенсивностью l. Поток обслуживания одним каналом имеет интенсивность m (величина, обратная среднему времени обслуживания t_ob). Найти финальные вероятности состояний СМО, а также характеристики ее эффективности:

А – абсолютную пропускную способность, то есть среднее число заявок, обслуживаемых в единицу времени;

Q – относительную пропускную способность, то есть среднюю долю пришедших заявок, обслуживаемых системой;

Р_отк - вероятность отказа, то есть того, что заявка покинет СМО необслуженной;

– среднее число занятых каналов.

Состояние системы массового обслуживания S будем нумеровать по числу заявок, находящихся в системе (в данном случае оно совпадает с числом занятых каналов):

S₀ – в СМО нет ни одной заявки;

S₁ - в СМО находится одна заявка (один канал занят, остальные свободны);

.....

S_k - в СМО находится k заявок (k каналов заняты, остальные свободны)

S_n - в СМО находятся n заявок (все n каналов заняты).

Граф состояний СМО выглядит следующим образом (рисунок 3.7):

Рисунок 3.7 – Граф состояний многоканальной СМО
с отказами

 

Разметим этот граф – проставим у стрелок интенсивности потоков событий. Интенсивности потоков l все одинаковы, что естественно, так как на СМО действует один и тот же внешний поток заявок на обслуживание. Интенсивности же потоков обслуживания увеличиваются с каждым занятым каналом. А теперь, зная все интенсивности, воспользуемся уже готовыми формулами для финальных вероятностей в системе гибели-размножения. Получим:

(3.22)

где! обозначает факториал.

Члены разложения ,...  будут представлять собой коэффициенты при P₀ в выражениях для P₁, P₂,...P_n:

                                                       (3.23)

 

Заметим, что в формулы (3.22), (3.23) интенсивности l и m  входят не по отдельности, а только в виде отношения l / m. Обозначим

                                                                 (3.24)

и будем называть величину  приведенной интенсивностью потока заявок. Ее смысл - среднее число заявок, приходящее за среднее время обслуживания одной заявки. Пользуясь этим обозначением, перепишем формулы (3.22), (3.23) в виде:

                           (3.25)

Формулы (3.25) для финальных вероятностей состояний называются формулами Эрланга - в честь основателя теории массового обслуживания.

По финальным вероятностям можно вычислить характеристики эффективности СМО. Сначала найдем P_otk - вероятность того, что пришедшая заявка получит отказ. Для этого нужно, чтобы все n каналов были заняты, значит,

                                                (3.26)

Отсюда находим относительную пропускную способность - вероятность того, что заявка будет обслужена:

                                       (3.27)

Абсолютную пропускную способность получим, умножая интенсивность потока заявок  на Q:

                                      (3.28)

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

                                        (3.29)

3.5.2. Одноканальная СМО с неограниченной
очередью

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

L_сист - среднее число заявок в системе;

W_сист - среднее время пребывания заявки в системе;

L_оч - среднее число заявок в очереди;

W_оч - среднее время пребывания заявки в очереди;

Р_зан - вероятность того, что канал занят (степень загрузки канала).

Что касается абсолютной пропускной способности А и относительной Q, то вычислять их нет надобности: в силу того, что очередь не ограничена, каждая заявка рано или поздно будет обслужена, поэтому А =  , по той же причине Q=1.

Решение. Состояния системы будем нумеровать по числу заявок, находящихся в СМО:

S₀- канал свободен;

S₁- канал занят, очереди нет;

S₂- канал занят, одна заявка стоит в очереди; и т.д.

Теоретически число состояний ничем не ограничено. Граф состояний имеет вид (рисунок 3.8).

 

Рисунок 3.8 – Граф состояний одноканальной СМО с неограниченной очередью

 

Это - схема гибели и размножения, но с бесконечным числом состояний. По всем стрелкам поток заявок с интенсивностью  переводит систему слева направо, а справа налево - поток обслуживаний с интенсивностью . Если > , то канал с заявками не справляется, очередь растет до бесконечности. Если £ , то задача вполне разрешима. Воспользуемся формулами для финальных вероятностей из схемы гибели и размножения и для бесконечного числа состояний. Подсчитаем финальные вероятности:

 

                   (3.30)

 

Ряд в формуле (3.30) представляет собой геометрическую прогрессию. Известно, что при < 1 ряд сходится; при ³ 1 ряд расходится. Теперь предположим, что это условие выполнено, и < 1. Суммируя прогрессию в (3.30), получаем

откуда .                                         (3.31)

Вероятности p ₁, p ₂,..., p _k,... найдутся по формулам:

, ,..., ,...,

откуда с учетом (3.31) найдем окончательно:

, ,..., .(3.32)

Как видно, вероятности р ₀, р ₁... образуют геометрическую прогрессию со знаменателем . Как ни странно, максимальная из них р ₀- вероятность того, что канал будет вообще свободен. Как бы ни была загружена система с очередью, если только она вообще справляется с потоком заявок, самое вероятное число заявок в системе будет равно нулю.

Найдем среднее число заявок в СМО L_сист. Случайная величина Z – число заявок в системе- имеет возможные значения 0,1,2,...,k,... с вероятностями р ₀, р _1,..., p _k,... Ее математическое ожидание равно

(3.33)

Подставим в (3.33) выражение для р _k из (3.32):

 

Произведение  есть ни что иное, как производная по  от выражения ^k; значит,

  (3.34)

Но сумма в (3.34) есть не что иное, как сумма бесконечно убывающей геометрической прогрессии с первым членом  и знаменателем ; эта сумма равна , а ее производная . Подставляя это выражение в (3.34), получим:

.                                                       (3.35)

Теперь применим формулу Литтла и найдем среднее время пребывания заявки в системе:

                                                    (3.36)

Найдем среднее число заявок в очереди L_оч. Будем рассуждать так: число заявок в очереди равно числу заявок в системе минус число заявок, находящихся под обслуживанием. Значит (по правилу сложения математических ожиданий), среднее число заявок в очереди L_оч равно среднему числу заявок в системе L_сист минус среднее число заявок под обслуживанием. Число заявок под обслуживанием может быть либо нулем (канал свободен), либо единицей (канал занят). Математическое ожидание такой случайной величины равно вероятности того, что канал занят (Р_зан). Очевидно, Р_зан равно 1 минус вероятность р ₀ того, что канал свободен:

.                                               (3.37)

Следовательно, среднее число заявок под обслуживанием равно

                                                                (3.38)

отсюда

и окончательно

                                                            (3.39).

По формуле Литтла найдем среднее время пребывания заявки в очереди:

                                                       (3.40)

Таким образом, все характеристики эффективности СМО найдены.

 

3.5.3.Многоканальная СМО с неограниченной
очередью

Аналогично одноканальной СМО решается задача о многоканальной СМО с неограниченной очередью. Нумерация каналов- опять по числу заявок, находящихся в очереди:

S₀- все каналы свободны;

S₁- один канал занят, очереди нет;

S₂- занято два канала;

....................................

S_n- занято n каналов;

S_n+1- заняты все n каналов, одна заявка стоит в очереди;

...................................

S_n+r- занzты все n каналов, r заявок стоит в очереди;

..................................

 

 

Рисунок 3.9 – Граф состояний многоканальной СМО
с неограниченной очередью

 

Граф состояний показан на рисунке 3.9. Граф есть схема гибели и размножения, но с бесконечным числом состояний. Естественное условие существования финальных вероятностей- <1. Если , очередь растет до бесконечности. Предположим, что условие <1 выполнено, и финальные вероятности существуют. Применяя формулы для схемы гибели и размножения, найдем эти финальные вероятности. В выражении для Р ₀ будет стоять ряд членов, содержащих факториалы, плюс сумма бесконечно убывающей геометрической прогрессии со знаменателем . Суммируя ее, найдем

 

               (3.41)

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

                                           (3.42)

Прибавляя к нему среднее число заявок под обслуживанием (оно же- среднее число занятых каналов) , получаем:

                                                     (3.43)

Деля выражение для L_сист и L_оч на , по формуле Литтла получим средние времена пребывания заявки в очереди и в системе:

,                             (3.44)