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

СМО описываются некоторыми параметрами, которые характеризуют эффективность работы системы.

 – число каналов в СМО;

 – интенсивность поступления в СМО заявок;

 – интенсивность обслуживания заявок;

 – коэффициент загрузки СМО;

 – число мест в очереди;

 – вероятность отказа в обслуживании поступившей в СМО заявки;

 – вероятность обслуживания поступившей в СМО заявки (относительная пропускная способность СМО);

При этом:

                                                                             (8)

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

                                                                                           (9)

 – среднее число заявок, находящихся в СМО

 – среднее число каналов в СМО, занятых обслуживанием заявок. В тоже время это  – среднее число заявок, обслуживаемых в СМО за единицу времени. Величина  определяется как математическое ожидание случайного числа занятых обслуживанием n каналов.

,                                                           (10)

где  – вероятность нахождения системы в S_k состоянии.

 – коэффициент занятости каналов

 – среднее время ожидания заявки в очереди

 – интенсивность ухода заявок из очереди

 – среднее число заявок в очереди. Определяется как математическое ожидание случайной величины m – числа заявок, состоящих в очереди

                                                                        (11)

Здесь  – вероятность нахождения в очереди i заявок;

 – среднее время пребывания заявки с СМО

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

Для открытых СМО справедливы соотношения:

                                                                            (12)

                                                                                            (13)

Эти соотношения называются формулами Литтла и применяются только для стационарных потоков заявок и обслуживания.

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

 

5. Основные типы открытых систем массового обслуживания

 

5.1 Одноканальная система массового обслуживания с отказами

Размеченный граф состояний одноканальной СМО представлен на рисунке 3.

Рисунок 3 – Граф состояний одноканальной СМО

Здесь  и  – интенсивность потока заявок и выполнения заявок соответственно. Состояние системы S_o обозначает, что канал свободен, а S₁ – что канал занят обслуживанием заявки.

Система дифференциальных уравнений Колмогорова для такой СМО имеет вид:

где p_o(t) и p₁(t) – вероятности нахождения СМО в состояниях So и S1 соответственно. Уравнения для финальных вероятностей p_o и p₁ получим, приравнивая нулю производные в первых двух уравнениях системы. В результате получим:

                                                                               (14)

                                                                               (15)

Вероятность p₀ по своему смыслу есть вероятность обслуживания заявки p_обс, т. к. канал является свободным, а вероятность р₁ по своему смыслу является вероятностью отказа в обслуживании поступающей в СМО заявки р_отк, т. к. канал занят обслуживанием предыдущей заявки.

5.2 Многоканальная система массового обслуживания с отказами

Пусть СМО содержит n каналов, интенсивность входящего потока заявок равна , а интенсивность обслуживания заявки каждым каналом равна . Размеченный граф состояний системы изображён на рисунке 4.

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

Состояние S₀ означает, что все каналы свободны, состояние S_k (k = 1, n) означает, что обслуживанием заявок заняты k каналов. Переход из одного состояния в другое соседнее правое происходит скачкообразно под воздействием входящего потока заявок интенсивностью  независимо от числа работающих каналов (верхние стрелки). Для перехода системы из одного состояния в соседнее левое неважно, какой именно канал освободится. Величина  характеризует интенсивность обслуживания заявок при работе в СМО k каналов (нижние стрелки).

Сравнивая графы на рис. 3 и на рис. 5 легко увидеть, что многоканальная СМО с отказами является частным случаем системы рождения и гибели, если в последней принять  и

                                                               (16)

При этом для нахождения финальных вероятностей можно воспользоваться формулами (4) и (5). С учётом (16) получим из них:

                                                                 (17)

                                                                       (18)

Формулы (17) и (18) называются формулами Эрланга – основателя теории массового обслуживания.

Вероятность отказа в обслуживании заявки р_отк равна вероятности того, что все каналы заняты, т.е. система находится в состоянии S_n. Таким образом,

                                                                             (19)

Относительную пропускную способность СМО найдём из (8) и (19):

                                                             (20)

Абсолютную пропускную способность найдём из (9) и (20):

Среднее число занятых обслуживанием каналов можно найти по формуле (10), однако сделаем это проще. Так как каждый занятый канал в единицу времени обслуживает в среднем  заявок, то  можно найти по формуле:

5.3 Одноканальная система массового обслуживания с ограниченной длиной очереди

В СМО с ограниченной очередью число мест m в очереди ограничено. Следовательно, заявка, поступившая в момент времени, когда все места в очереди заняты, отклоняется и покидает СМО. Граф такой СМО представлен на рисунке 5.

S0

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

Состояния СМО представляются следующим образом:

S₀ – канал обслуживания свободен,

S₁ – канал обслуживания занят, но очереди нет,

S₂ – канал обслуживания занят, в очереди одна заявка,

S_k+1 – канал обслуживания занят, в очереди k заявок,

S_m+1 – канал обслуживания занят, все m мест в очереди заняты.

Для получения необходимых формул можно воспользоваться тем обстоятельством, что СМО на рисунок 5 является частным случаем системы рождения и гибели, представленной на рисунке 2, если в последней принять  и

                                                                           (21)

                                                   (22)

                                                                      (23)

Выражения для финальных вероятностей состояний рассматриваемой СМО можно найти из (4) и (5) с учётом (21). В результате получим:

При р = 1 формулы (22), (23) принимают вид

При m = 0 (очереди нет) формулы (22), (23) переходят в формулы (14) и (15) для одноканальной СМО с отказами.

Поступившая в СМО заявка получает отказ в обслуживании, если СМО находится в состоянии S_m+1, т.е. вероятность отказа в обслуживании заявки равна:

Относительная пропускная способность СМО равна:

Абсолютная пропускная способность равна:

Среднее число заявок, стоящих в очереди L_оч, находится по формуле

и может быть записано в виде:

                                                        (24) 

При  формула (24) принимает вид:

 – среднее число заявок, находящихся в СМО, находится по формуле(10)

и может быть записано в виде:

                                              (25)

При , из (25) получим:

Среднее время пребывания заявки в СМО и в очереди находится по формулам (12) и (13) соответственно.

 

5.4 Одноканальная система массового обслуживания с неограниченной очередью

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

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

Все характеристики такой СМО можно получить из формул предыдущего раздела, полагая в них . При этом необходимо различать два существенно разных случая: а) ; б) . В первом случае, как это видно из формул (22), (23), р₀ = 0 и p_k = 0 (при всех конечных значениях k). Это означает, что при  очередь неограниченно возрастает, т.е. этот случай практического интереса не представляет.

Рассмотрим случай, когда . Формулы (22) и (23) при этом запишутся в виде:

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

Абсолютная пропускная способность равна:

Среднее число заявок в очереди получим из формулы (24) при :

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

Среднее число заявок, находящихся в СМО:

Среднее время пребывания заявки в СМО и в очереди определяются формулами (12) и (13).

5.5 Многоканальная система массового обслуживания с ограниченной очередью

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

Граф такой системы представлен на рисунке 7.

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

 – все каналы свободны, очереди нет;

 – заняты l каналов (l = 1, n), очереди нет;

- заняты все n каналов, в очереди находится i заявок (i = 1, m).

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

Выражения для финальных вероятностей легко найти из формул (4) и (5). В результате получим:

                                         (26)

Образование очереди происходит, когда в момент поступления в СМО очередной заявки все каналы заняты, т.е. в системе находятся либо n, либо (n+1),…, либо (n + m – 1) заявок. Т.к. эти события несовместны, то вероятность образования очереди p_оч равна сумме соответствующих вероятностей :

                                                             (27)

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

Относительная пропускная способность равна:

Абсолютная пропускная способность:

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

                                      (28)

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

Среднее число заявок, находящихся в СМО:

Среднее время пребывания заявки в СМО и в очереди определяется формулами (12) и (13).

5.6 Многоканальная система массового обслуживания с неограниченной очередью

Граф такой СМО изображен на рисунке 8 и получается из графа на рисунке 7 при .

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

Формулы для финальных вероятностей можно получить из формул для n-канальной СМО с ограниченной очередью при . При этом следует иметь в виду, что при  вероятность р₀ = р₁=…= p_n = 0, т.е. очередь неограниченно возрастает. Следовательно, этот случай практического интереса не представляет и ниже рассматривается лишь случай . При  из (26) получим:

Формулы для остальных вероятностей имеют тот же вид, что и для СМО с ограниченной очередью:

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

Поскольку очередь не ограничена, то вероятность отказа в обслуживании заявки:

Относительная пропускная способность:

Абсолютная пропускная способность:

Из формулы (28) при