Опять выдвинем гипотезу, состоящую в том, что время пребы вания произвольной заявки в системе Т попало в интервал
(t,t + dt):
Р{Т с ( / , t + dt))xf{t)dt .
Так как в потоке П'вых заявки следуют строго друг за другом, то за время t в системе накопится в среднем Xt заявок. Следова
тельно, и в этом случае формула (3.2.14) тоже имеет место. Вернемся к анализу разомкнутых систем массового обслужи
вания.
Т_______
л_____ |
r |
9 |
9 |
1 |
*1 |
> |
> |
Выходящий |
О |
1' |
2е |
3' |
4' |
5’ |
б' |
7' t |
nomoK |
|
|
|
|
Рис. 3.2.6 |
|
|
||
Сравнивая выражения (3.2.12) и (3.2.14), можно записать следующую формулу для среднего времени нахождения заявки в системе:
t = |
s+r - = — |
(3.2.15) |
|
|
X |
л |
v |
В дальнейшем будет |
доказана |
справедливость |
формулы, |
определяющей среднее время ожидания заявки в очереди |
|||
|
70Ч = ^ - . |
|
(3.2.16) |
Сопоставляя формулы |
(3.2.14) и |
(3.2.16), можно |
убедиться |
в том, что среднее время обслуживания заявки определяется по формуле
(3.2.17)
Разомкнутые системы массового обслуживания будут рас смотрены в гл. 4, 5, 6.
Глава 4
СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ С ОТКАЗАМИ
Система массового обслуживания называется системой с от казами (потерями), если заявка, пришедшая в момент, когда все
каналы заняты, немедленно получает отказ и покидает систему (теряется).
Рассмотрим я-канальную разомкнутую систему массового обслуживания, на вход которой подается простейший поток зая вок с интенсивностью К. Поток обслуживаний каждого канала —
простейший с интенсивностью ц. Если заявка застает все каналы занятыми, то она покидает систему необслуженной (получает отказ).
При наличии свободных каналов могут рассматриваться раз личные алгоритмы распределения заявок по каналам: строгое (неслучайное) распределение заявок по свободным каналам или же случайное (хаотическое) распределение заявок по каналам. Кроме того, могут иметь место случаи, когда заявка, принятая к обслуживанию, по тем или иным причинам, не дождавшись конца обслуживания, покидает систему, т. е. остается необслуженной (случай «нетерпеливых» заявок). Могут иметь место случаи не полного обслуживания заявки, выхода канала из строя и т. п. Общим для всех этих систем является то обстоятельство, что заявка получает отказ, если все каналы заняты.
Перейдем к анализу различных систем массового обслужива ния с отказами. Рассмотрение каждой системы будем начинать с постановки задачи и заканчивать сводкой основных расчетных формул.
Хотя большинство систем, рассматриваемых в книге, являет ся частными случаями схемы гибели и размножения, тем не ме нее с целью развития навыков анализа этих систем будем каж дую систему изучать достаточно подробно.
юз
§4.1. КЛАССИЧЕСКАЯ СИСТЕМА МАССОВОГО ОБСЛУЖИВАНИЯ
СОТКАЗАМИ (СИСТЕМА ЭРЛАНГА)
П о с т а н о в к а з а д а ч и . На вход n-канальной системы массового обслуживания подается простейший поток заявок с интенсивностью X. Интенсивность простейшего потока обслужи-
ваний каждого канала ц. Если заявка застала все я-каналов занятыми, то она получает отказ (покидает систему необслуженной). Если заявка застала свободным хотя бы один канал, то она принимается к обслуживанию любым из свободных каналов и обслуживается до конца (заявки «терпеливые»).
Рис. 4.1.1
Описанная выше система названа нами классической потому, что с рассмотрения такой системы Эрлангом и начала разви ваться теория массового обслуживания. Эрланг рассмотрел ра боту такой системы на примере работы автоматического теле фонного узла связи. В этом случае поток заявок представляет собой поток вызовов со стороны абонентов. Длительность обслу живания характеризуется длительностью коммутации и длитель ностью разговора. Число каналов п равняется максимально воз
можному числу одновременно осуществляемых разговоров. Анализ работы любой СМО будем начинать с рассмотрения
возможных состояний системы и составления размеченного гра фа состояний системы с указанием интенсивностей потоков, переводящих систему из состояния в состояние.
Рассмотрим следующее множество состояний системы:
Хо — все каналы свободны, ни одна заявка не обслуживается; Х\ — занят ровно один канал (какой — неважно), обслужи
вается одна заявка;
хк — занято ровно k каналов (каких именно — неважно), об служивается k заявок;
хп — все п каналов заняты, обслуживаются п заявок *
Граф состояний данной СМО с отказами представлен на рис. 4.1.1. Как и ранее, возможность перескока «через состояния» не рассматривается, так как все потоки ординарны.
* Можно было бы рассмотреть и более обширное множество состояний с указанием, какие именно каналы заняты, но в этом нет необходимости, так как все каналы одинаковы.
104
Поясним порядок определения интенсивностей потоков собы тий на рис. 4.1.1. Когда система находится в состоянии x0i на нее
действует поток заявок с интенсивностью X, переводящий систему в состояние Х\. Если система находится в состоянии то на нее
действует уже два потока событий: 1) поток заявок с интенсив ностью 7., который стремится перевести систему в состояние Л'2 и
2) поток освобождений канала («поток обслуживаний»), кото рый стремится перевести систему в состояние лг0. Интенсивность этого потока равна р.
Рассмотрим случай, когда система находится в состоянии xh(k = 1, 2, ..., п— 1). В этом состоянии на систему действует опять
два потока:
1)поток заявок с интенсивностью X, который стремится пере вести систему слева направо, т. е. в состояние xh+\;
2)поток освобождений всех А занятых каналов с интенсив ностью Ар, который стремится перевести систему справа налево
всостояние хк~\.
Если система находится в состоянии х1и то на нее действует
только один поток событий с плотностью яр, переводящий систе му справа налево в состояние хп-\.
В соответствии с мнемоническим правилом составления си стемы дифференциальных уравнений для вероятностей состояний (см. § 2.3) получим
dt |
— |
"f l1/7! 00; |
|
|
|
|
|
|
|
||
dPk(t) |
— (Л4Au) pk (t) 4- |
\рь- 1(/) + |
|
||
dt |
(4.1.1) |
||||
|
|
|
|||
+ (* + l ) l ^ A + i ( 0 (* = 1. 2,. |
/ г - 1 ) , |
||||
dpn it) |
—HV-PnW + ^Pn-1(0- |
|
dt |
||
|
Система (4.1.1) обычно интегрируется при начальных условиях
Ро(0)= 1: |
| |
Ра(0) = О (А = 1, 2,. |
(4.1.2) |
п), J |
что соответствует случаю, когда система в начальный момент при /= 0 свободна. Решение системы (4.1.1) при начальных усло виях (4.1.2) удовлетворяет нормировочному условию
V р„{{) = \ ( /> 0 ) . |
(4.1.3) |
Уравнения (4.1.1) называются уравнениями Эрланга. Заме
тим, что выражения (4.1.1) — (4,1.3) справедливы и для случая, когда потоки событий не являются простейшими, а представляют собой нестационарные пуассоновские потоки. В этом случае пара метры X = k(t)y р = р (0 являются некоторыми функциями вре
мени. В дальнейшем мы, как правило, не будем выписывать систе му дифференциальных уравнений для вероятностей состояний, так как читатель, зная мнемоническое правило составления этих уравнений и глядя на граф состояний, может без труда самостоя тельно их записать.
Вернемся к анализу нашей системы и рассмотрим стационар ный режим работы при t— *оо. Такой режим существует (см.
§ 2, 4), так как наша система эргодична: в ней нет групп состоя ний без выхода или без входа и все потоки простейшие.
Тогда при t— ъоо система дифференциальных |
уравнений |
||
(4.1.1) |
превратится в систему алгебраических уравнений: |
||
0 = — |
|
|
|
0 = |
— (Х-{- £ц) pk-\-\pk„\ - j (-£ -j- 1) |
( ^ = 1 , 2 , . |
., n — 1); |
|
|
|
(4.1.4) |
0 = — яр./?я + \p n-u
которые нужно решать совместно с нормировочным условием (4.1.3).
Для решения системы (4.1.4) введем обозначения такие же, какие были введены при анализе .схемы гибели и размножения:
i i ^ — lp i-i-i-ip p . (1 = 1, 2,. |
/г). |
(4.1.5) |
С учетом (4.1.5) уравнения (4.1.4) примут вид
«1 = 0;
iik |
i — uk — 0 (£ = 1, 2,. |
п — 1); |
(4.1.6) |
«/, = |
0- |
|
] |
Анализируя систему (4.1.6), убеждаемся в том, что
«/ = 0 ( / =1 , 2,. |
п). |
(4.1.7) |
Следовательно:
100
и вообще |
|
|
|
p* = ( - j f - ^ p0 |
(* = 0 , 1 , 2 , . |
(4.1.8) |
|
Для нахождения вероятности р0 воспользуемся нормировоч |
|||
ным условием |
|
|
|
I! Pk— Po X |
1, |
||
k=0 |
k=0 |
|
|
откуда |
|
|
|
Ро = |
1 |
(4.1.9) |
|
i —\Lkk\ |
|||
|
|
||
|
Л = 0 r |
|
|
Окончательно получим следующие формулы для вероятностей |
|||
состояний: |
|
|
|
|
|
(4.1.10) |
|
k=0 |
|
|
|
которые называются формулами Эрланга: |
|
||
Введем обозначение |
|
|
|
а = X |
(4.1.11) |
||
Величина а равна среднему числу заявок, поступающих в систе му за среднее время обслуживания одной заявки в одном канале.
Преобразуем выражение (4.1.10) к виду, удобному для вы числений. С этой целью используем обозначение (4.1.11) и умно жим числитель и знаменатель дроби (4.1.10) на величину е~%:
Р(Ь> а)
R(n, а)
(4.1.12)
к =0
где P(k, а) и R(n, а) табличные функции пуассоновского распре
деления (см. приложение).
107