книги / Прикладная теория систем массового обслуживания
..pdfКонстанта С определяется условием нормировки:
Nт-1 00
£Z Jn(x,fc,m)dx = l, т*1 к=О О
и имеет вид
С = |
N |
1 |
|
|
т-1 |
’ |
|||
|
||||
|
<*1*0я)1ЛГ/(ЛГ-*) |
|
||
|
у=1 |
А:=0 |
|
здесь а определяется равенством (4.15).
Распределение (4.16) решает задачу исследования математической модели СМО с буфером бесконечной длины и позволяет находить основ ные вероятностные характеристики. Рассмотрим нахождение некоторых из них:
1. Распределение числа свободных приборов (обслуживающих)
|
|
|
N |
N |
® N |
N |
N |
дг _ 1г |
— ■ |
< , ( , ) . / s |
n(,,*,m )d*=<,c— |
z m |
- |
|
Qm=k+\ |
|
* т=к+1 |
|
£<?("*) |
|
|
|
г=0-^ |
|
|
|
|
^ m=r+l |
|
2. Предельное значение коэффициента загрузки приборов |
||||
|
|
N |
|
|
|
<“ = S - L I >( OT)= |
Ц щ (т ) |
|
|
|
т=1_____ |
|
||
|
N m=i |
ЛГ |
|
|
|
I |
|
|
|
|
г=0ЛГ-г т=г+\ |
|
3. Асимптотическое распределение числа заявок в очереди (экспо ненциальное распределение) с плотностью (4.15) имеет смысл среднего
значения. Поэтому среднее число заявок в буфере М = —.
е
4. Средняя величина задержки (время очереди) /оч в буфере опреде ляется по формуле Литтла:
5. вом (4.13).
Аналогично можно определить и другие вероятностные характери стики СМО с буфером.
Таким образом, выше рассмотрена и построена векторная СМО с бесконечной очередью и однородными запросами на число мест в очереди. Получены явные выражения для расчета основных вероятностных харак теристик СМО с буфером.
4.4. Примеры систем массового обслуживания с ожиданием
Пример 4.1. Показать, что для любого т > 0 и любых параметров (л, Ху ц) СМО с ожиданием имеет большую пропускную способность, чем СМО с отказами и с теми же параметрами (и, Х9р).
Решение
Вероятность обслуживания заявки для СМО с отказами
|
|
«(О _ Л ( и - 1»а)_, |
Р{п,а) |
|||
|
|
Гобс - ~ |
г— - 1 - |
— |
-• |
|
|
|
|
R(n, а) |
Л(и,а) |
||
Вероятность обслуживания заявки для СМО с ожиданием |
||||||
|
|
р(2) _ 1 |
v m |
Р(п,а) |
|
|
|
|
гобс - 1" X |
|
|
|
|
|
|
|
Я(л,а) + Я(и,а)х1 - Г |
|||
|
|
|
|
|
1-Х |
|
Рассмотрим первоначально случай, когда %= 1 (а = п), и покажем, |
||||||
что гобс |
гобс > О |
|
|
|
|
|
В этом случае разность вероятностей |
|
|
||||
1- - |
Р{ПуП) |
\ |
Р(п,п) |
=Р(п,П) |
1 |
>0, |
|
|
|
|
1 |
||
Я(/я,и) + тР{ПуП) . |
R(n>n)_ |
LR(rtyп) |
R(riyп) + тР(Пуп)_ |
так как знаменатель первой дроби в квадратной скобке меньше знаменате ля второй дроби.
Рассмотрим общий случай, когда %Ф 1 :
р(2) |
СО_ Р(п,а) |
Л(и, а) + Р(п, а )х -г — - *(”,а)Хт |
___________ _ . 1 г х _____ ____ |
||
Л)бс |
061 R(n, а) |
1 —у т |
|
|
R(n, а) + Р(п,а)х— ^ ~ |
|
|
1-Х |
Разность будет положительной, если положительным является чис литель последней формулы; покажем, что он положительный:
R(n,a) + Р(п,а)х-— ^ — - R(n,а)хт= ^-[Л(и,а)(1 - % ) - %Р(п,а)] =
1-Х |
1-Х |
= |
_ ХЛ(л - 1,а)} |
|
1-Х |
Отношение — — положительно при любом значении %. Покажем, 1-Х
что разность, стоящая в квадратных скобках, тоже положительна:
R(n, а) - %R(n - 1,а) = Л(«,а) - - R (n - 1,а) = р(0,а) + £/>(*, а / 1 - -1 > О,
и *=1 V п )
т.к. каждый член суммы неотрицателен (к < ri).
Таким образом, показали, что при одинаковых параметрах (п, А., р) система с ожиданием имеет большую пропускную способность, чем сис тема с отказами. Это достигается за счет увеличения времени нахождения заявки в системе, т.е. за счет того, что заявка будет ожидать в очереди.
Пример 4.2. Рассматривается СМО с ожиданием и частичной взаи мопомощью, когда каналы могут помогать друг другу, объединяясь в группы, наибольший состав которых равен 1<п. При занятии всех каналов очередная пришедшая заявка не получает отказ, а может стать в очередь, число мест в которой равно т. Составить размеченный граф состояний системы и найти основные характеристики работы такой системы.
Граф состояний имеет вид, показанный на рис. 4.3.
Рис. 4.3. Граф состояний СМО с частичной взаимопомощью и конечной очередью
На этом графе величина h равна целой части отношения у . Этот
граф с точностью до обозначений совпадает с графом состояний СМО с частичной взаимопомощью (глава 3) или системы массового обслуживания с ожиданием (§ 4.1). Следовательно,
р.= |
Р(к,а,) |
0 = 0, 1...... А), |
n -h + m |
R(h,a,) + P(h,a,)x i - x
1-Х
P r t P h Q= h,h+ 1, ...п + т),
X |
- L |
где а , = —; х |
|
/ц |
иц' |
Для краткости рассмотрим только случай %* 1. Вероятность обслу живания
^обс = 1 - Р»+т = 1 - PhX"~h*m-
Среднее число занятых каналов К =аРобс. Среднее число заявок, находящихся в очереди:
г = £гРя+1 = ï r P hXn+r = г пРн 1 х г = Рихп+' L~ |
- j - r ?x)+1]. |
|||||
п=\ |
Г=1 |
|
Г=1 |
|
(1 - х) |
|
Среднее число заявок в системе |
|
|
|
|||
п+т |
h |
п+т |
|
|
|
|
î = т |
= |
+ 1 |
jPj = |
|
|
п-И +т |
1=0 |
/=0 |
j-h |
R(h,a.i) +P(h,CLi)x |
1-Х |
|
|
|
|
|
|
|
1 - х |
|
|
. |
„ |
1 - х л+т[(« + '« )(1-х )+ 1] |
|
||
|
|
*х |
г ? ) |
• |
|
|
Среднее число обслуживаемых заявок S - I - г .
г
Среднее время ожидания в очереди /оч = —, среднее время пребыва- А,
. I ния заявки в системе t = —.
X
5. РАЗЛИЧНЫЕ СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ
Эта часть учебного пособия содержит разделы, охватывающие большой круг вопросов, содержащих ряд важных приложений теории мас сового обслуживания к различным областям практической деятельности. Многие реальные процессы могут рассматриваться как представленные в данной главе системы массового обслуживания. За последние годы теории СМО уделялось большое внимание и были получены важные результаты. Вследствие того, что прикладное значение теории СМО возросло, некото рые из новых результатов включены в главу 5.
5.1.Система массового обслуживания с ожиданием
иприоритетом в обслуживании
Зачастую при рассмотрении СМО приходится иметь дело с заявками определенного типа, которые должны обслуживаться в первую очередь. Примером такой СМО является аэродром с одной взлетно-посадочной по лосой (ВПП). Самолетам, идущим на посадку, ВПП предоставляется в первую очередь, т.е. они пользуются приоритетом в обслуживании по сравнению с самолетами, которые используют ВПП для взлета. Аналогич ную картину можно наблюдать на автозаправочной станции (АЗС), где обычно рейсовые автобусы обслуживаются в первую очередь.
В системах массового обслуживания с приоритетом могут быть раз личные варианты дисциплины обслуживания.
Системами с абсолютным приоритетом называются такие системы, в которых заявка, обладающая приоритетом, немедленно принимается к об служиванию каналом, занятым обслуживанием заявки без приоритета в обслуживании. Например, если на АЗС прибывает рейсовый автобус, а в это время заправляется легковая машина, то ее заправка прекращается и начинается заправка автобуса. После того, как заявка, обладающая при оритетом, обслужена, а других заявок, обладающих приоритетом, нет, во зобновляется прерванное обслуживание заявки, не обладающей приорите том. Здесь возможны различные варианты: заявка, обслуживание которой было прервано, начинает обслуживаться заново; прерванное обслуживание заявки начинается с того места, где оно было прервано; заявка, обслужива ние которой было прервано, вообще теряется.
Системами с относительным приоритетом называются такие систе мы, в которых заявка, не обладая приоритетом, обслуживается до конца, после чего принимаются к обслуживанию заявки, обладающие приорите том (если такие имеются).
Из всех возможных СМО с приоритетом здесь рассмотрим только одну, самую простую: одноканальную СМО с абсолютным приоритетом.
Постановка задачи. Рассматривается СМО с абсолютным приори тетом, на вход которой подаются два независимых простейших потока зая вок с интенсивностями Х\ и А.2. Заявки первого потока (интенсивность ко торого равна Х\) обладает приоритетом в обслуживании. Число мест в оче реди для заявок обоих видов не ограничено. Если канал обслуживает заяв ку первого потока, то интенсивность простейшего потока обслуживания равна \х\. Если канал обслуживает заявку второго потока, то интенсивность простейшего потока обслуживания равна р2- В этом случае нет различия между двумя вариантами дисциплины обслуживания:
а) прерванное обслуживание заявки начинается с того места, где оно было прервано;
б) заявка, обслуживание которой было прервано, начинает обслужи ваться заново.
Это объясняется тем, что интервал времени всего обслуживания и интервал остатка времени обслуживания распределены одинаково по пока зательному закону с параметрами р2. Граф состояний такой СМО приведен на рис. 5.1.
Рис. 5.1. Граф состояний СМО с бесконечной очередью и абсолютным приоритетом
Состояние системы будем связывать с числом заявок /, обладающих приоритетом, и числом заявоку, не обладающих приоритетом, находящих ся в данный момент t в системе. Рассмотрим различные состояния систе мы: х0,о ~ в системе нет никаких заявок; x0tj - в системе имеется у заявок, не обладающих приоритетом, из этиху заявок одна обслуживается, ay - 1 ждут очереди; xit0- в системе имеется i заявок, обладающих приоритетом, и нет заявок, не обладающих приоритетом, из этих i заявок одна обслужи вается, а остальные i - 1 ожидают в очереди; Ху - в системе имеется / зая вок, обладающих приоритетом, иу заявок, не обладающих приоритетом, из / заявок, обладающих приоритетом, одна заявка обслуживается, а / - 1 ожидают в очереди; до тех пор, пока все заявки, обладающие приоритетом, не будут обслужены, заявки, не обладающие приоритетом, не обслужива ются.
Система уравнений имеет следующий вид:
^ 7 ^ = -(*1 + W . o ( ' ) + ^ Л о (') + Ц2*0,.(') > at
— |
=~(^1 +^2 + ^2)^о(0 + ^1^/-1,о(0 + Ц1^-1,о(0» |
(5.1) |
||||||
dPQAt) |
|
|
|
|
|
|
|
|
-------^ |
- ~ (^1 |
+ ^ 2 |
+ |
1*2 У *3,у ( 0 + |
^ 2^ 3,7-1 ( 0 |
+ ^ 2 ? 3,7+1 ( 0 |
+ P lf l.y ( 0 |
» |
^ |
= “ (^1 |
+ ^ 2 |
+ |
lA2 ) ^ , 7 ( 0 + |
^ 2^ , 7- l ( 0 + |
^ l ^ - l,7 ( 0 + |
li l^ + l, 7 ( 0 |
- |
Эту систему дифференциальных уравнений обычно интегрируют |
||||||||
при следующих начальных условиях: Ро,о(0) = 1 ; |
Рц{0) = 0 (при / Ф 0 или |
у * 0; в начальный момент система свободна).
Решение системы уравнений для любого момента времени t удовле творяет условию нормировки:
00ОО
££ Л,у ( 0 = 1.
/=0 у=0
Введем обозначения: (Xj = /щ ; а 2 = Я,2 /ц 2.
Можно доказать, что стационарный режим работы системы сущест вует только в случае, когда ai + а 2 < 1. Так как величины ai и а 2 поло жительны, то при этом также должны выполняться условия ai < 1, a 2 < 1.
Найдем стационарный режим работы системы с приоритетами, для чего нужно в уравнениях (5.1) принять все производные равными нулю.
Допустим, что удалось решить полученную систему алгебраических уравнений и вероятности Ри (/ = 0, 1, 2, ...;j = 0, 1,2, ...) найдены. Тогда
вероятность того, что в системе будет ровно i заявок, обладающих приоритетом (безотносительно к тому, сколько имеется там заявок, не об ладающих приоритетом), можно найти по следующей формуле:
У - о
Вероятность Ру.2)того, что в системе имеется ровно j заявок, не об
ладающих приоритетом (безотносительно к тому, сколько имеется там зая вок, обладающих приоритетом), запишем в виде
pj 2) = z pi j -
/=0
Так как рассматриваемая система является системой с абсолютным приоритетом, то рассмотрение вопросов обслуживания заявок, обладаю щих приоритетом, можно проводить без учета наличия заявок, не обла дающих приоритетом. Одноканальная система без ограничения мест в оче реди была рассмотрена в главе 4. Следовательно,
/>(,) = а ;(1 - а ,) |
(i = 0 ,1,2,3,...). |
Для нахождения вероятностей PtJ применим метод производящих функций [9] и введем в рассмотрение производящую функцию вида
= £ I pi j x ‘y J
/=07=0
Отметим некоторые свойства этой производящей функции:
1 . t p ( U ) = î î ^ 7 = l .
/=07=0
2. ф(о,о)=ё | ; р, .о о =/>о,0-
/=07=0
QO 00 |
00 |
00 |
оо |
... ао |
1__ п |
3. ф(0,0)= Z I |
ри х‘ = 2 * ' I |
Ри = |
|
= |
|
i= 0j =0 |
i= 0 |
7 = 0 |
/ = 0 |
/ = 0 |
i |
Среднее число заявок, не обладающих приоритетом и находящихся в системе, найдем так:
h = £ Î J P 'J |
= £ |
jP j2)= ( ^ - î t |
Pijyj ) = (^-<?(hy))y=v |
7=01=0 |
7=o |
qv/=o7=o |
чу |
После этих предварительных замечаний найдем производящую функцию ф(х*у), для чего в уравнениях (5.1) примем все производные рав ными нулю. Далее первое уравнение системы (5.1) умножим на х°у° = 1, второе уравнение - на хгу° = х\ третье уравнение - на x°yJ = y J\ четвертое уравнение - на xly J и все эти уравнения сложим, перебрав все возможные значения / и / Проделав это и проведя некоторые простые преобразования, получим
( I , + х 2 + M X |
X /> у У = х (ц, - \i2)PQJy J + р2/>0,о+ ^ I |
Z |
У + |
||
/=0 у =0 |
7=0 |
,=1 |
у =0 |
|
|
+ Hi I |
2 |
Pi+ijx‘yJ + * 2 1 |
+ Ц2 I ^о,,+У |
(5-2) |
|
/=07=0 |
/=07=1 |
7=0 |
|
|
Двойные суммы, входящие в выражение (5.2), могут быть выражены через функции ф(х,у). Проведя соответствующие преобразования выраже ния (5.2), получим следующую формулу:
Ф |
^ ) = к Я * - 0 - V2*(y - 1)ко,>о+ »2х(у - 1)ф(0,0) |
|
*•1хуО - х) + Х 2ху(1 - у ) + ц 2^ (х - 1 ) |
Найдем корни i | и i ; знаменателя этого выражения, считая, что |
|
1< ^ < 0: |
|
X, |
A.t +Я2(1->') + Ц1 -д/(^1 + M i~ .)0 + m )2 —4A.|(j.! |
= |
|
|
2Х, |
|
_ X] + Х2 (1 - у) + Ц] + ~J( \ , +А.2(1->0 + р 1)2 -4Я.,р| |
2 |
23Ц------------------------------ • |
Это дает возможность (после некоторых довольно громоздких пре образований, которые опускаем) получить следующее выражение для про изводящей функции:
ф (х ,у ) = -----------— g O O - a ^ )
(1- ajx, - a 2y)(l - a ^ x ) ’
где a = ct]+ a 2.
Обратим внимание на то, что величина х\ зависит от переменной у. Приу = 1 xi= 1.
Для нахождения отдельных вероятностей состояний можно восполь зоваться следующими формулами:
^о,о = Ф(0>0) = 1 - a , di+J ,
?iJ Яj\
x=y=0
Воспользовавшись выражением производящей функции [9] для оты скания закона распределения числа заявок, не обладающих приоритетом в обслуживании и находящихся в СМО, получим
00 |
00 |
= i p j 2)yJ=-— — — , |
|
фОоО 'Е |
I p i j y J |
||
/=0 |
у=0 |
j=o ' |
\ - щ х х- а гу |
откуда |
|
|
|
|
р(2) = 1 |
(5.3) |
|
|
|
|
|
|
7 ~ |
f i |
7=0 |
|
|
|
При вычислении производных по выражению (5.3) нужно иметь в виду, что величинах! является функцией^.
Среднее число заявок, обладающих приоритетом в обслуживании и находящихся в очереди, определяется из выражения
1 -0 ,
Среднее время пребывания заявки, обладающей приоритетом, в сис теме (в очереди),
|
п = |
1 <*1 |
|
|
Хх |
ц, 1 - а , |
|
Среднее время пребывания заявки, обладающей приоритетом, в сис |
|||
теме (в очереди и на обслуживании), |
|
|
|
1ii |
i]_ l 2 |
|
J ___1__ |
= — |
= 'о ч 1 + ------------ |
1 —ot, |
Hi 1-cti |
h |
Hi Hi |
Среднее число заявок, не обладающих приоритетом и находящихся в системе,
|
|
а |
дх}■ + СХп |
||
/,= |
|
(1 -а ) |
ду |
|
|
у=1 |
а,х, - |
а 2у) |
|||
ду |
(1 - |
||||
|
|
|
|
у=I |
|
а, |
X2Х\ |
+ «2 |
|
|
|
---- 2- L^ |
|
1+ H2 «I |
|||
= (1-а) |
HI ~ ^ I*I_____ |
^2 |
|||
(1 - a,jc, - a 2y)2 |
1-X |
Hi i - V |
Jy=l