книги / Прикладные задачи теории массового обслуживания
..pdfЭто следует из того, что
/7—1
1 ~ Л . = 2 Л >~°- k=О
Т^аким образом, для обеих систем, рассмотренных в § 4.2 и существует такое значение параметра (при прочих одина1^Овых параметрах), когда обе системы имеют одинаковую пр°Г1ускную способность. При К Х * СМО, рассмотренная в § 4.6, бУА£т иметь большую пропускную способность, чем СМО, рас ш иренная в § 4,2, а при 7.Ж* — наоборот. На рис. 4.6.3а по-
казаны графики зависимости относительных пропускных способН0СТей систем, рассмотренных в § 4.2 (Робе) и § 4.6 (Робе).
Глава 5
СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ С ОЖИДАНИЕМ
До сих пор рассматривались системы массового обслуживания с отказами; характерной особенностью таких систем было то, что любая поступившая заявка либо немедленно принималась к об служиванию, либо немедленно получала отказ и покидала сис тему.
Вэтой главе будут рассмотрены системы массового обслужи вания с ожиданием, в которых заявка, заставшая все каналы за нятыми, не получает немедленного отказа, а может стать в оче редь и ожидать освобождения канала, который может ее обслу жить.
Системы с ожиданием бывают «чистого» или «смешанного» типа. В чистой системе с ожиданием число мест в очереди и вре мя ожидания в ней ничем не ограничены: каждая заявка рано или поздно будет обслужена. Для такой системы понятие «от каз» не имеет смысла.
Всистеме с ожиданием смешанного типа возможны как от казы, так и ожидание заявки в очереди. Отказы (отсутствие обслу
живания) могут быть связаны или с ограниченным числом мест в очереди, или с ограниченным временем ожидания, которым располагает заявка.
В этой главе рассмотрим систему массового обслуживания смешанного типа с ограниченным числом мест в очереди т. Очевидно, при т = О получим как частный случай ранее рассмот ренную систему с отказами, а при т— ьсо чистую систему с ожи
данием.
При рассмотрении систем массового обслуживания с ожида нием необходимо учитывать систему правил, регламентирующих порядок образования и обслуживания очереди (так называемую «дисциплину очереди»). Необходимо указать, является ли оче редь общей, или образуется к каждому каналу отдельно; каков порядок вызовов заявок из очереди и т. д.
Будем называть порядок вызовов заявок из очереди естест венным, если заявки обслуживают по принципу «кто раньше стал
172
в очередь, тот и раньше обслуживается». Можно рассмотреть обслуживание с приоритетом, когда определенного вида заявки обслуживаются в первую очередь. Например, самолетам, иду щим на посадку, в первую очередь предоставляют взлетно-поса дочную полосу (ВПП). Если нет самолетов, идущих на посадку, разрешается использование ВПП взлетающими самолетами. Другим примером системы массового обслуживания с приорите том может служить система обслуживания населения городским транспортом: пассажиры с детьми и инвалиды обслуживаются вне очереди. Могут рассматриваться и такие случаи, когда заяв ка вызывается из очереди на обслуживание в случайном порядке.
Поведение заявок в очереди также входит в понятие «дис циплина очереди». Заявки в очереди могут «терпеливо» ждать начала обслуживания, а могут и уходить из системы, не дождав шись своей очереди. В этой главе будут рассматриваться только «терпеливые» заявки. Случай «нетерпеливых» заявок будет рас смотрен в шестой главе.
§5.1. КЛАССИЧЕСКАЯ СИСТЕМА МАССОВОГО ОБСЛУЖИВАНИЯ
СОЖИДАНИЕМ
П о с т а н о в к а з а д а ч и : На |
вход |
/z-канальной |
системы |
|
массового обслуживания поступает |
простейший |
поток |
заявок |
|
с плотностью А,. Плотность простейшего |
потока |
обслуживании |
||
каждого канала р. Если вновь поступившая заявка застает сво бодным хотя бы один канал, она принимается на обслуживание и обслуживается до конца (заявки «терпеливые»). Если заявка застает все каналы занятыми, она становится в очередь и «тер пеливо» ждет своего обслуживания.
Дисциплина очереди естественная: кто раньше пришел, тот раньше и обслуживается*; максимальное число мест в очере ди т. Если заявка застает все т мест в очереди занятыми, то
она получает отказ и исключается из обслуживания. Каждая за явка может обслуживаться только одним каналом (взаимопомо щи между каналами нет). Величины /г, А,, р, т будем называть
параметрами системы массового обслуживания с ожиданием. Состояния рассматриваемой системы будем связывать с чис
лом заявок, находящихся в системе (обслуживаемых и ожидаю щих в очереди):
Xk — в системе имеется k заявок (& = 0, 1, 2, ..., /г), они об служиваются k каналами, очереди нет;
— в системе имеется п + r заявок (г=1, 2, ...,т), п из них обслуживаются в п каналах и г заявок находит
ся в очереди.
*Необходимо иметь в виду, что для пуассоновских систем дисциплина очереди влияет лишь на закон распределения времени пребывания заявки в очереди. При этом никакие вероятностные характеристики самой системы, ни даже среднее время пребывания заявки в очереди не зависят от дисциплины очереди.
173
Таким образом, система имеет п + т+ 1 состояний. Граф со
стояний рассматриваемой системы показан на рис. 5.1.1.
Этому графу состояний соответствует система дифференци альных уравнений для вероятностей состояний, которая справед лива и для переменных л и р. Обычно эту систему дифференци альных уравнений интегрируют при начальных условиях
а Г(0)=1; Pj(0)=o (j ф о), |
(5.1.1) |
т. е. когда в момент / = 0 система свободна от заявок.
Рис. 5.1.1
Заметим, что рассматриваемый нами граф состояний СМО с ожиданием (рис. 5.1.1) с точностью до обозначений сов падает с графом состояний системы массового обслуживания с отказами и частичной взаимопомощью между каналами, изо
браженным на |
рис. 4.4.1. |
Поэтому при |
анализе стационарного |
||||
режима работы |
СМО |
с |
ожиданием, когда |
A,= const, |
p = const, |
||
т < оо, t— юо, можно |
воспользоваться результатами § 4.4. Сле |
||||||
довательно [см. (4.4.6)], имеем |
|
|
|
|
|||
рк = ^~ pQ(k = 0, 1, 2, . . . , и); |
рп+г=у.Трп(г = 0, 1, 2, . . . , т). |
||||||
к\ |
|
|
|
|
|
|
|
|
|
|
|
п |
т |
Рп+Г=^' получим |
|
Используя нормировочное |
условие ^ |
+ 2 |
|||||
|
|
|
|
к=0 |
т=1 |
|
|
Рк=- |
Р (к, а) |
1—у." -(* = <>, |
1, . . . , *), |
(5.1.2) |
|||
|
|
|
|||||
Я(П, а) + Р(п, а) у. ■1—х |
|
|
|
||||
р„+г = у/р11-. |
|
7ГР (П, а) |
|
(5.1.3) |
|||
|
|
1 — ът |
|||||
|
|
|
|
|
|
||
|
|
|
R (П, |
а) + Р (п, |
а) у.- 1—т. |
|
|
гле
(5.1.4)
174
___ х_
(5.1.5)
пц
Эти формулы получаются из формул (4.4.2), (4.4.3) и (4.4.6) пу тем замены величин:
/|д, — величиной (х; h — величиной п;
п — величиной п+т.
(сравните графы на рис. 4.4.1 и рис. 5.1.1). В формулах (5.1.2) и (5.1.3) величина х ф \ .
Для сокращения дальнейших записей введем обозначения:
— |
" Р " |
I |
|
R (Л, а) + Р (л, а) % ■1—X |
|
(5.1.6) |
|
|
|
||
_________ 1________ |
при |
у.= 1. |
|
R{n, п) + Р(п, п)т |
|||
|
|
Заметим, что если нормировочное условие записать в виде
л—1 т
2 ^ * + 2 j°n+r = I» Аг=0 г=0
то величина р будет определяться так: |
|
|
|
1 |
при |
у. ф 1; |
|
1— х” *» |
|||
|
|
||
Я (л — 1, а) + Р (л , а) 1 - х |
|
(5.1.7) |
|
Р = |
|
||
|
|
||
R (r t— 1, н) + Я (л, л) (m -f- 1) |
при |
/ — 1. |
|
|
|
Из этого, в частности, вытекают следующие равенства:
/ ? ( » - ! , |
*) + Я(л, а) Г^ х- |
= /? (« . |
=0 + |
|
|
|
+ # (я , а )х 1 — — ( ■/ 1) ; |
|
|
(5.1.8) |
|
|
|
|
|
||
R ( n —1, |
л) + Я(я, /г)(«г-(-1)=/((л, |
«) + ^ (я> п)т, , |
|
||
в справедливости которых для любых положительных |
а и к |
||||
и любых положительных целых |
п и m можно |
непосредственно |
|||
убедиться. |
|
заявки |
равна |
вероятности |
того, |
Вероятность обслуживания |
|||||
что заявка, поступившая на обслуживание, застанет свободными хотя бы один из каналов или хотя бы одно место в очереди:
л-fm—1
Робе= ^ Pk= ^ Рпфт— 1 р%тР (п, а )= 1 ш/’тр п• (5.1.9) ft=О
1 7 5
С д р у го й стороны :
где
п |
т |
|
k p ^ |
n 2 р "*г |
|
к=0 |
г=1 |
|
среднее число занятых каналов. |
|
|
Следовательно, среднее число занятых каналов будет |
|
|
Т = — Ро6с= « (1 - * тРп)- |
(5.1.10) |
|
Вероятность того, что канал занят, равна |
|
|
* э . к = |
— |
(5.1.11) |
Вероятность того, что система полностью загружена, равна ве роятности того, что в системе заняты все каналы:
т |
т |
|
|
*п.з = 2 |
P n +r = ? P { n , а) X |
L = £ ^ 1 |
(5.1.12) |
г=0 |
г=0 |
|
|
При рассмотрении классической системы массового обслужи вания с отказами мы приводили граф состояний для определения времени неполной загрузки системы (см. рис. 4.1.3), который бу дет справедлив и для рассматриваемой СМО с ожиданием при определении закона распределения времени неполной загрузки системы.
Поэтому среднее время неполной загрузки СМО с ожиданием
будет равно среднему времени неполной загрузки /н.3, опреде ляемому для СМО с отказами [см. (4.1.26)]:,
1 R (n — 1, g)
(5.1.13)
//'J. Р (/?, а )
Рис. 5.1.2
Закон распределения времени полной загрузки системы опре деляется графом, который изображен на рис. 5.1.2. Этот граф аналогичен графу, изображенному на рис. 4.3.3, с помощью ко торого определялся закон распределения времени полной заня тости СМО с отказами и полной взаимопомощью, рассмотренной в § 4.3.
17G
Среднее время полной загрузки СМО с ожиданием определим на основании эргодического свойства [см. (5.1.12) и (5.1.13)]:
Л,з = / н .з - Лп‘3 - |
(5.1.14) |
1— Лп.з |
|
Рассмотрим величину Г„.0 — время наличия очереди в систе ме. Это время отсчитывается начиная от момента образования очереди до следующего очередного момента ликвидации очереди. Закон распределения времени наличия очереди в системе опре деляется с помощью графа, изображенного на рис. 5.1.3. Соответ-
Рис. 5.1.3
ствующую |
этому графу состояний систему |
дифференциальных |
|
уравнений |
нужно интегрировать при начальных условиях |
||
/5??+1(0) = 1; ph(0 ) = 0 при к ф п + 1. |
Функция |
распределения вре |
|
мени наличия очереди определяется из выражения |
|||
|
F « . o ( t ) = |
p „ { t ) . |
|
Среднее время наличия очереди можно найти с помощью гра фа состояний, изображенного на рис. 5.1.4. Этот граф с точ ностью до обозначений совпадает с графом СМО с отказами и полной взаимопомощью, изображенным на рис. 4.3.1.
Рис. 5.1.4
Следовательно:
1— у.1*
1 — у.т 1
Рп+г |
1 |
|
( * = 1 ). |
|
|
|
|
||
|
т + 1 |
|
|
|
|
|
|
|
|
Таким образом, среднее время наличия очереди^ (т. е. среднее |
||||
время пребывания системы в группе |
состояний .vn+i, |
*n+m) |
||
определяется по формуле |
|
|
1 — ът |
|
|
1— Я |
1 |
(5.1.15) |
|
|
Т |
|
||
|
Рп |
1 — У- |
|
|
|
|
|
|
|
177
Для нахождения среднего времени занятости канала прове дем следующие рассуждения. Допустим, что к моменту оконча ния обслуживания заявки в рассматриваемом канале в системе нет очереди.
Вероятность этой гипотезы обозначим
/?Н.О== 1 ' р н . 0 1
где Рн.о — вероятность наличия очереди в системе.
Если в системе очереди нет к моменту окончания обслужи вания, то среднее время занятости канала будет равно 1 / JLI. Если
к моменту окончания обслуживания в системе будет очередь (ве роятность этой гипотезы р в . о), то среднее время занятости кана
ла будет равно — + /н.0- Применяя формулу полного матема-
тического ожидания, можно найти среднее время занятости ка нала:
/з.к= (1 — Рн.о) — |
-\-Рн.о(— + /н.о)=— + |
P H J » . O. |
(5.1.16) |
|||
Н- |
|
\ И |
) |
V- |
|
|
Вероятность наличия очереди определяется по формуле |
|
|||||
тп |
|
ш |
|
|
|
|
Рн.о=2_1 Pn+r = |
2 j Pn*r — Pn* |
|
' |
(5.1.17) |
||
г=1 |
|
г=1 |
|
|
|
|
Среднее время простоя канала найдем |
из выражения |
|
||||
|
|
Я з . к 1 |
|
|
|
(5.1.18) |
Ат.К-- А |
|
|
|
|||
1 --Яз.К
Рассмотрим другие характеристики очереди. К таким харак
теристикам относится прежде всего среднее число завок г, на
ходящихся в очереди и ожидающих обслуживания, которое оп ределяется из следующего выражения [см. (5.1.3), (5.1.6) и (4.3.13)]:
m
1 — |
[ m ( \ |
— у . ) 4 - 1 ] |
(5.1.19) |
r = Yi ГРп+г=Рп% |
( l - 7 |
(*¥=1). |
|
r=l |
. ) 2 |
|
|
|
|
|
|
При х = 1 это выражение примет вид |
|
||
7 = 2 rfP("- « )= р />(». ») . ” (” +' > |
■ ± а± И . |
(5.1.20) |
|
Г=1 |
|
|
|
В этом выражении р определяется из второго равенства в фор муле (5.1.6).
178
Найдем закон распределения времени пребывания заявки в очереди Гон, для чего найдем вероятность того, что это время
больше некоторого фиксированного |
интервала t, т. е. найдем |
P { T 04> f ) V > |
0). |
Буд^м рассматривать только стационарный режим работы. Вы двинем гипотезу, состоящую в том, что система находится в со стоянии хк (& = 0, 1, 2, п + т). Тогда по формуле полной
вероятности
п + т
Р(Т0Ч> П = 2 РкР(То.>*\хк), |
(5.1.21) |
*=0 |
|
где P(T04> t\x h) — условная вероятность пребывания в очереди в течение времени, большого, чем t, при усло
вии, что к моменту поступления очередной заявки система находилась в состоянии JC/t.
Очевидно, вероятность P(T04> t \хк)=0 при k<n, так как
в этом случае есть свободные каналы и заявка немедленно при нимается на обслуживание. Кроме того, вероятность Р(?оч>1\*п+?п) =0, так как в этом случае заявка получает отказ
и тоже в очередь не становится. Следовательно:
/и—1
|
/ >(Г0Ч> |
/ ) = 2 |
Pn+rP(T04> i \ x n+r). |
(5.1.22) |
||
|
|
|
г=0 |
|
|
|
(m-r) |
|
|
г заявокВ очереди |
cm |
|
|
мест в очереди |
|
|
||||
i--------А-------- , |
|
_______ |
ш |
|
||
t—1Ы •• н—101—|0нч |
|
m |
Каналы |
|||
••• 1—101—101- LTJ |
обслуживания |
|||||
ТП ^ |
г + / |
Т |
Г-1 |
|
1 |
|
0 |
Вновь построившая |
|
С Ю |
|
||
заявка |
|
|
|
|||
|
|
|
|
Рис. 5.1.5 |
|
|
Вероятность того, что время ожидания в очереди Точ будет боль ше, чем t, при условии, что перед данной заявкой имеется оче редь, в которой стоят г заявок (г = 0, 1, 2, ..., m— 1) (см. рис. 5.1.5) равна вероятности того, что за время t будет обслу
жено не более г заявок, при этом обслуживание производят всея каналов. При наличии очереди, когда все п каналов заняты, по
179
ток обслуженных заявок будет простейший |
с |
параметром /гр, |
||||||||||||
следовательно:! |
|
|
г |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
^ |
|
L |
|
e- ^ |
= R{r, |
n\U). |
|
||
|
Я(7'0Ч> ^ |х „ +г) = У |
|
|
(5.1.23) |
||||||||||
|
|
|
|
k =0 |
|
k\ |
|
|
|
|
|
|
||
С учетом этого выражения, |
а также выражений |
(5.1.22), |
(5.1.3) |
|||||||||||
и (5.1.5) получим |
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
P(T04> t ) = |
t |
y-rpn V |
|
|
|
|
|
|||||
|
|
|
|
r = 0 |
|
|
|
k = 0 |
|
|
|
|
||
Изменим |
порядок суммирования: |
|
|
|
|
|
|
|
||||||
|
|
|
т—1 |
|
|
|
|
|
|
ш—1 |
|
7л _ |
||
Р{Т0Ч>£) = рле г ^ У) |
(щ^)к |
S ■г = |
|
2 |
|
|||||||||
|
|
/г;х/) |
|
|||||||||||
|
|
|
|
k\ |
Р п |
|
1 -7 . |
|||||||
|
|
|
* = 0 |
|
|
|
|
|
|
|
* =0 |
|
|
|
|
|
|
"тп—1 |
<W0* |
е- ща _ |
%тц (nl _ |
|
|
|
|||||
|
|
Рп |
у |
1 |
|
|
||||||||
|
|
1 —7. |
— |
k\ |
|
|
|
|
|
|
|
|
|
|
|
|
|
Lfe= o |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
e-(nx,-i)t[^ (m _ |
1 1 X/)- x*tf (от— 1, «u/)j |
(5.1.24) |
|||||||||
При |
y.= l |
получим |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
/7 1 - 1 |
|
|
|
|
|
||
|
|
P{T04> t ) = Pne ~ ^ |
£ |
|
k\ |
|
|
= |
|
|||||
|
|
|
|
|
|
|
k = 0 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
m—1 |
|
|
|
|
|
|
|
= Pn |
от/? (m — 1, |
/ZIJ./) — |
^ |
ke~n'lt |
|
|
|
|||||
|
|
|
|
|
|
|
|
|
ft= 0 |
|
|
|
|
|
|
= ;?„ [от/? (m — 1, n\it) —n^tR(m — 2, |
//.tx/)] |
(от > 1), |
(5.1.25) |
||||||||||
|
П |
£Я(£, a)= aR(n — 1, |
|
|
|
|
|
|
|
|||||
так |
как ^ |
я) |
(я > 0 ) . |
|
|
|
||||||||
|
ft= 0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Заметим, что при f< 0 |
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
я ( |
Г |
о |
ч |
> |
о |
= |
1 , |
|
|
|
так как время ожидания заявки в очереди есть величина неотри цательная. При t = 0 имеет место скачок
{гп , |
(х ф 1); |
1--Л |
(5 . 1.26) |
180 |
рпт |