Е.С. Вентцель, Л.А. Овчаров - Задачи и упражнения по теории вероятностей (1115276), страница 57
Текст из файла (страница 57)
Пример СМО с очередью и с абсолютным приоритетом.Имеется одноканальная СМО с двумя местами в очереди (га = 2).На вход СМО поступают два простейших потока заявок I и II синтенсивностями Х 1? Х 2 . Времена обслуживания — показательные с параметрами \хг, |л2. Заявка I, прибывшая в СМО, «вытесняет» заявку II, если она обслуживается, и занимает место в очередиперед ней, если она стоит в очереди.
«Вытесненная» заявка II покидает СМО необслуженной, если в очереди уже нет мест, и становится в очередь, если места есть. Нумеруя состояния СМО двумя индексами г, j соответственно числу заявок I и II, находящихсяв СМО, построить размеченный граф состояний СМО и написатьуравнения для финальных вероятностей состояний. Считая этимуравнения уже решенными, выразить через р{- (i + j < 3) следующие характеристики эффективности СМО:^отк (PQ-ПС ) ~~ вероятность того, что заявка I (II) получит отказнемедленно после прибытия;406Qi (Q2) ~~ вероятность того, что заявка I (II) будет обслужена;гг (z2) — среднее число заявок I (II), связанных с СМО;г, (г2)_— среднее число заявок I (II), находящихся в очереди;Чист (*сист) ~ среднее время пребывания в системе заявки It$ (t^) — среднее время пребывания в очереди заявки I (II);tcliCT — среднее время пребывания в системе любой (произвольной) заявки;tQ4 ~ среднее время пребывания в очереди любой заявки.Р е ш е н и е .
Состояние СМО: s- — в СМО находится г заявок Iи j заявок II (г Л- j < 3). Размеченный граф состояний показан нарис. 11.42.Уравнения для финальных вероятностей состояний:(\+ Х 2 ) р00 = \Ltp10 + \i2p01;+\1гР20 +\12Рп]VlPw =\(Р20( \ + \+ M > 2 W =Х2Р01+M-l)?20 =\PlO(Х1+ №(*>+ \poz;(\+\h2)+++V1P3O +M-2P21»*+^2^02;+ \1гр21 + \l2Pl2> ( Х 1 += Х 2 р 1 0 + \Р01+VlPl2+\2рп+ Х2 + |j,1) р10 = \р00( Х 1 ^ Х 2 + М-2)Р(>1 = Х 2 ^ 0 0 +V4P1+P2l);( \ + Х 2 + \LX + [i2)pn(\Ml +V2)Pl2=ХХ2 +1^02 +р03 = Х 2 р 0 2 ;Р00 + Рю + Р20 + РЗО + Poi + Pll + ?21 + Р02 + Р\2 + Роз = ^* отк=^30 ' -* отк=РзО ~^~ P21 ^~ P l 2 ~^~ ^ 0 3 'X,5V00"10Г==^—"* отк=•*•—^30'VI1!ХЦ2Х12^2М-2Г1Г м-1^2^1М>2,Vr*М-1XX, 1 1ДйГРис.
11.42407Чтобы найти Q2> найдем сначала А2 — среднее число обслуженных заявок II в единицу времени:А2 = М1~ Ро(тк) ~ \(Р03 + Pl2 + P 2 l ) = Х 2 [ ! - (fto + ?21 ++JP12 + РОЗ )] - Х 1 (РОЗ + Pl2 + P21 )•Разделив это выражение на Х2, находим среднюю долю обслуживаемых заявок II (вероятность того, что заявка II будет обслужена): Q2 = А2 J Х2. ТогдаF =1l( P l O + P l l + Pl 2 ) + 2 (Р 2 0 + P 2 l ) + 3 f t 0 ;23Г =+ P 2 l ) + ( P 0 2 + Pl2) + P03; 11*2= 1(j>01 +Pll2+f( Р 2 0 + P 2 l ) + P3 0 ; 2 = l ( P l l ++р 2 1 ) + 2р12.По формулам Литтла7(1)_ ~/ \ •6сист ~ *1 I A l Jf''СИСТ= _ b _ f (хЛ1 "ГхА1)°СИСТ27(2) —_ F/\.сист^2 / А 2>6XI'хА21 +хА6Г(1) __ - / \ .оч ~~ 'l I А 1 )7(2) .
Ги^СИСТ 12ОЧХ^хА11+7(2) _ _ - / х .оч ~ ' 2 I А 2 'Х7(1) ,хА62°ОЧ'хА1 +27(2)хЛ^ОЧ*2Все характеристики, относящиеся к заявкам I, можно вычислить и не решая уравнений (11.42), а просто игнорируя наличиезаявок II, рассматривая СМО с ограниченным числом мест в очереди (т = 2) и находя ее характеристики по формулам п. 3 (см.с. 379, 380).11.43. Простейшая! СМО без очереди и с «разогревом» каналов.На вход n-канальной СМО поступает простейший поток заявок синтенсивностью X. Время обслуживания — показательное с параметром |о, Перед тем как начать обслуживание заявки, канал должен подготовиться («разогреться»). Время «разогрева» Траз имеетпоказательное распределение с параметром У и не зависит от того,как давно канал прекратил работу. Заявка, заставшая канал свободным, «занимает» его и ждет, пока он разогреется, после чегопоступает на обслуживание. Заявка, заставшая все каналы занятыми (обслуживаемой или ожидающей заявкой), покидает СМОи остается необслуженной.
Найти финальные вероятности СМОи характеристики ее эффективности: вероятность отказа Ротк, относительную пропускную способность Q, абсолютную пропускную способность Л, среднее число занятых каналов к.Р е ш е н и е . Будем считать, что обслуживание заявки состоитиз двух фаз: ожидания разогрева и самого обслуживания:^обсл = тРаз + Тобсл • Случайная величина Гобсл распределена пообобщенному закону Эрланга 2-го порядка (см. задачу 8.39) с параметрами |i, У. Мы знаем, что формулы Эрланга (11.0.6) справедливы не только для показательного, но и для любого распределе408ния времени обслуживания. Найдем величину fx = 1 / M f f ^ ].ИмеемМ[Гобсл] = М[Граз] + М [ Г о б с л ] = 1 / ^ + 1 / у = (^ + у ) / ( И 1откуда fl = ([iv) I ([i + v).
Вычислив р = X / jl и подставив это значение р в формулы Эрланга (11.0.6), получим:Ро1 + £+...+£-+...+£1!к\п!Ркк\Ро (1<к<п);1 -9- Р0Чтобы найти среднее число занятых каналов к, нужно разделить А на jl:1Ро = РМ-о-11.44. Простейшая одноканалъная СМО с очередью и «разогревом» канала. На одноканальную СМО с неограниченной очередьюпоступает простейший поток заявок с интенсивностью X. Времяобслуживания — показательное с параметром [i (\х > X).
Перед темкак приступить к обслуживанию заявки, свободный до того каналдолжен «разогреться». Время «разогрева» — показательное с параметром у и не зависит от того, как давно канал закончил работу.Если обслуживание начинается сразу же после окончания обслуживания предыдущей заявки, «разогрева» не нужно. Составитьграф состояний СМО и написать уравнения для финальных вероятностей состояний; выразить через эти вероятности характеристики эффективности СМО: средние числа заявок в системе J и вочереди г, средние времена пребывания заявок в системе £сист и вочереди tQ4.Р е ш е н и е .
Состояния СМО (рис. 11.44):s00 — канал свободен, не разогрет;501 — пришла одна заявка и ждет, канал разогревается;500XS,°U11хS4J2У\хЧ15111Х s°0бУхи* М- ''5XУ1хв1512VX13VРис. 11.44409sn — канал разогрет, одна заявка обслуживается, очереди нет;502 — канал разогревается, в очереди две заявки; ...;sQl — канал разогревается, в очереди I заявок;su — канал обслуживает одну заявку, / — 1 заявка стоит в очереди; ....Уравнения для финальных вероятностей:Хроо = М>ц; (X + v) Рог = ^Роо; ( Х + И») Рп = vPoi + M>i2 5( \ + v)p 02 =\p01;(\ + \i)p12 =yp02 + \рп +м> 1 3 ;...;(X + v)p 0|/ = X p 0 i M ;(X + M,)plf/ =VPO,/ +Xp l f W + M . P I I / + I ; - .
. ;oooo* = X ^ (^м + Pi,*);f= Z ^ (Pof/ + Pi,/+i)•/=1t =0По формуле Литтла^сист — ^ / X; tm —r J X.11.45*. Имеется одноканальная СМО с очередью, ограниченной числом мест га = 2. На вход СМО поступает простейший поток заявок с интенсивностью X. Время обслуживания распределено по обобщенному закону Эрланга с параметрами щ, |i 2 (см. задачу 8.31). Найти вероятности состояний СМО:s0 — в СМО нет заявок;вг — в СМО одна заявка (очереди нет);5 2 — в СМО две заявки (одна обслуживается, одна в очереди);5 3 — в СМО три заявки (одна обслуживается, две в очереди).1)_ Найти характеристики эффективности СМО: Р отк , Q, А,z, г, £ сист , tQ4.
Вычислить их для значений X = 2, \х.г = 6; \х2 = 12.2) Сравнить их с теми, которые получились бы для простейшейСМО с таким же значением X и значением |л, равным 1 / to6cJl, где^обсл ~~ с Р е Д н е е время обслуживания заявки в данной СМО.Р е ш е н и е . Поток обслуживании — не пуассоновский, значит,система не марковская, и найти вероятности состояний СМО пообычной методике, которую мы применяем для марковских процессов с дискретными состояниями и непрерывным временем,нельзя. Однако процесс, протекающий в СМО, можно искусственно свести к марковскому с помощью так называемого «методафаз».Представим обслуживание состоящим из двух фаз (I и И), продолжающихся соответственно время Тг и Г2; полное время обслуживания Тобсл =Тг + Т2, где Тх имеет показательное распределение с параметром щ; Т2 — показательное распределение спараметром |л2.
Тогда Гобсл будет иметь обобщенное распределение Эрланга с параметрами |л1 и \х2 (см. задачу 8.39).410Введем следующие состояния СМО:s0 — СМО свободна;M-iX сЯsn — в СМО одна заявка, обслужива1°11ние в первой фазе;X \ ^ 2X512 — в СМО одна заявка, обслужива?тние во второй фазе;>Ч 22215 21 — в СМО две заявки (одна обслуживается и одна в очереди); обслуживаXX\ ^ 2ттние в первой фазе;Snt*1ш 5_ 15 22 — в СМО две заявки, обслуживаниеяво второй фазе;5 31 — в СМО три заявки, обслуживаниеРис. 11.45в первой фазе;5 32 — в СМО три заявки, обслуживание во второй фазе.Дальнейших состояний нет, так как (по условию га = 2) больше трех заявок в СМО быть не может. Размеченный граф состояний СМО показан на рис.
11.45. При таком подходе состояние sxрасчленяем на два: sn и s12 (или, короче, sx — su -j- s12); аналогично s2 = 521 + s 22 , sz = s3l + s32. Уравнения для финальных вероятностей, соответствующих графу рис. 11.45, будут:рь556Z>Фо = M<2Pi2; ( х + м-1) Рп = х ^о + м<2^22; ( х + м-2) Рп = м-i^ii;( Х + Щ)Р 2 1 =^2^32 + X Pll5V-iPsi( X + M-2)^22 =^iP 2 l + XPl2*>= X^2i5 ^2Рз2 = РгРгг + Х^22^нормировочное условие р0 + рп + р12 + р21 + р22 + р31 + р32 = 1.Решая эти уравнения, получаем:г [(X + f x 2 )XX[|X3(X + ^ + j x 2 ) + XV 2 (X + ^ 2 )Ро2^ 2M-lM-22[|2Х (Х + [х1 + \х2)Х 4 (Х + Щ + м , 2 ) + Х У 2 ( Х + |х 2 )||2 3M-lM-2M-lM-23|Х (Х + ^ + ц 2 )4|Х (Х + ц 1 + р , 2 ) + ХУ 2 (Х + ц 2 )3M-iM-1(Х+ц2)Х^ _XРи=Ро> Рп=—Ро\_ Х 2 ( ц 1 +М-2 +™22 ~'оМ-1^2Х)„ .
„PoiРз1-12X 3 (X+ t i 1 + ( i 2 )+XV a (X+ t i a ) j > .рРп =Г1°>_Х4(Х + ц г + ц 2 ) + Х У 2 ( Х + ц 2 ) _—3ч 29M-lM-2"0>411Р32:\ 4 ( Х + | А , + Н,2) + Х 3 Ц 2 ( Х + Ц 2 )\ 3 ( \ + щ + ц2)МчУ 2M-iM-2р 0 . (11.45.1)Далее находим финальные вероятности состояний sv s2, s3:( X + M-I + M*2)PO;Pi = P n +Pi2 =x2P 2 = Р И +Р22 = - T2T 2[ ( XM-iM-2+^l)(X+^l + M ' 2 ) + M'2(X + M'2)]PO;3ft = ftl + PS2=T T ^ 2M-iM-2+X^ 1 + M - I 2 ) ( ^ + M-I + ^ 2 ) ++ \12{\1г +ц 2 )(Х + ^ 2 ) ] р 0 ,(11.45.2)где p0 определяется первой из формул (11.45.1).Характеристики эффективности СМО могут быть найдены через вероятности р0, pv р2, ft по формулам:ротк=Рз'> Q = 1 - ft; i4 = х (1 - р 3 ); * = lft + 2р2 + Зр3;г = 1р2 + 2р3; *сист = J / X; tm=r/\.(11.45.3)Подставляя в формулы (11.45.1) численные данныеX = 2, |х1 = 6, |х2 = 12, получаем: р 0 = 0,540; ри = 0,182; р12 — 0,090;р 21 = 0,087; р22 = 0,050; р 31 = Сф29;;?32 — 0,022. Отсюда, возвращаясь к исходной (немарковской) СМО, имеем: р0 = 0,540; рг = 0,272;р2 = 0,137; рг = 0,051.Далее, по формулам (11.45.3):Ротк = 0,051; Q = 0,949; Л = 1,89; г = 0,705; г = 0,243; *сист = 0,352;*оч - 0,122.2) Подсчитаем те же характеристики для простейшей СМО с темиже X = 2,[JL = ( 1 / ^ 1 + 1 / | J L 2 ) ~ 1 = 4 По формулам (11.0.12)—(11.0.15)имеем:р = 0,5; р0 « 0,533; к = 1 - р0 « 0,467; рх = рр0 « 0,267;р2 = p2ft> ~ 0,133; р 3 = Р Ч ~ 0,067; Ротк = р3 « 0,067;Q = 1 _ р 3 « 0,933; А « 1,866; г « 0,733; f « 0,267; fCHCT = 0,367;*"от «0,133.Видим, что наша немарковская СМО имеет над простейшейСМО некоторое преимущество по пропускной способности иочень мало отличается от нее (в лучшую сторону) по времени пребывания заявки в СМО и по длине очереди.11.46*.