2. Системы массового обслуживания. Матвеев_ Ушаков (1984) (1186155), страница 27

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 27)

! ]1!(о — (а, г)) + Рн ! (0,) †' ]3! (о — (а, г)), ! = 1, г, (3) о 151 Таким образоМ, (рн(й)) представляет собой совместное распределение числа требований приоритетов 1,г сразу после ухода из системы У-го требования, а (Рио'!(н!!!, ..., йо'!, иь ... ..., и„)) †совместн распределение числа требований приоритетов 1,г в моменты ухода !т'-го, У+1-го,..., !!!'+а — 1-го требований и интервалов времени между уходом из системы 1Ч вЂ” 1-го и У-го, У-го и Л!+1-го,..., И+и — 2-го и И+и — 1-го требований.

Положим р>,(>,...,>, ! — ', >, ..., !) Р!.(>,", )О>() Г б). Если р„=~ а>р>>(1, то существуют пределы 1ип Ря(г) =Р(г), !пп Р,л(х) =Р;(г), Ь Ф 1!>пи»я(е) =ы>(е), (5) причем Г (1 — р >1>>>(ь)+ Я а (! — р>(р>(и))) >=>+! з-та> — а>р>(~>>(з)) Р,(г) = 1Р(0! >х>-!) — Р (О,г>)! (4 ' + г! (б) + (1 — р ) — 'р>(а — (а, г)), а Р(х) определяется соотношениями Р(г) =(1 — х —,'(),(с> — (а, г)))-' >~ >с ~ — Я Р(0>х') (г; ! (), (о — (а, г)) — гф ~,-~.! (о — (а, х))) + с + Р(0,) ~~~~ — >р>(о — (а, г)) — г, ! р,(а — (а, х))]~ >=! Р(О,) =1 — рсо Р(0>г') = (1 — г, >, ~>ч (р>л.>(о> — (а, х)>)))-' х Г х ~ — >~1 Р(0>г>) (г,—.! р, (р,.+>(о' — (а, х)'))— >=>+! à — г,— ь>>~>+>(р,+>(о' — (а, г)'))1+ Р(О,) ~ >>! — ' х >=! Л Р> (Р!.с! (о' — (а, г)')) — г,— ' Р, (1>ьс! (о' — (а, х)')) ~ ~ .

(10) 152 Т е о р е м а 2. Пусть р„! <1, тогда существует !пп рл! >(х!'>, .... г!" > е! е„) =р!">(г!'>, ..., г>>о е! е ) причем р(п>(г" >, ..., х'"', зь "., з ) определяется из рекуррентных соотношений Г р"2 (х, з)= ')' [Р(0,, г'-') — Р(О,х')] Х (=1 л Х г, ' р( (з + о — (а, г)) + (1 — р„) ~ ! ' р! (з + о — (а, х), (11) «+а !=! р(п> (х('),..., г(">, з,,..., з„) = ~], [р(п — (> (х((>, !=! Х(п — 2) О [Х(л — ()Х!и)! (-! — Р(п- ) (Х( ) Х(п-2) О, [Х(л — !)Х(п>] ~ З З ) ] [г,(п)] — ! Х ХР,(зп+о — (а, х(">)+Р("-')(х('>, ..., х(п-'>, О„з, зп,) Х х ~ ' р,.(з„+о — (а,х(">))- п)2, »п+О (=! (12) где [х(»вЂ " х(п>](-' = (г,'" " г,'и', г[" ! " г(">(, ..., г", 'г(п').

Рл ((О, ! х' — ') — Рн ((О,х') есть вероятность того, что в момент ухода (2' — 1-го требования в системе не осталось требований приоритетов 1,! — 1, осталось по крайней мере одно требование приоритета ! и все оставшиеся требования — «красные». р((о — (а, х)) = ~)," ... ~ г" ,... г',л Х ь=о ) =о Г е — пп 1"! !) ((В! (и) 153 Доказательство теоремы !. а). Докажем сначала соотношение (3). Воспользуемся методом введения дополнительного события. Каждое поступающее в систему требование приоритета 1 (!'=1, г) будем считать «красным» с вероятностью х( и «синим» вЂ” с вероятностью 1 — х( независимо от остальных требований. Тогда Р!н(х) можно интерпретировать как вероятность того, что Л'-е требование имело приоритет ! и в момент его ухода !в системе нс осталось «си~них» требований.

Далее, вероятность того, что за время обслуживания требования пр оритета 1 не поступали «синие» требования. Соотношение (3) вытекает из следующих рассуждени Для того чтобы Ж-е требование было требованием приоритет 1 и в момент его ухода в системе не осталось «синих» требава ний, необходимо и достаточно, чтобы: 1) либо после ухода й — 1-го требования система стал свободной, первым после этого в систему поступило требава' ние приоритета 1 н за время его обслуживания не поступал «синие» требования (вероятность этого события равна Рм, (0,)-' — 'р,(а — (а, г))); а 2) либо после ухода У вЂ” 1-го требования система не осво бодилась. При этом в системе не осталось требований приорн тетов 1,1 — 1, осталось хотя бы одно требование нр~иоритета все оставшиеся требования, за исключением требования прио ритета й которое поступает на обслуживание, «краоные», и з ' время обслуживания У-го требования не поступали «синие» требования (вероятность этого события равна (Рэ ,(О;, г'-') — Рк ,(О, г')) г; ' р;(о †(а, г))).

Соотношение (1) получается суммированием (3) по 1 от 1, до г. Соотношение (2) следует из того, что первое требование (в силу того, что в момент Г=О система свободна) поступает в свободную систему, и, следовательно, очередь, остающаяся' после его ухода из системы, образуется из тех требований, ко-. торые поступили за время его обслуживания. Для доказательства (4) покажем, что Рьэ ( 1, ..., 1, гь 1, ..., 1 ) = = Рг«(1, ..., 1) ы,» (а; — а;г;) р; (а, — а;г;) . (13~ Соотношение (13) вытекает из того, что при дисциплине Р)ГО очередь из требований приоритета 1, остающихся в системе после ухода некоторого требования приоритета 1, образуется из тех требований, которые поступили в систему в интервале между поступлением и уходом из системы данного требования приоритета 1, т.

е. за время его обслуживания и время его ожидания. В соотношении (13) слева стоит вероятность того, что Л1-е требовач)ие имеет приоритет 1 и после его ухода в системе не остается «синих» требований того же приоритета, а справа — вероятность того, что Ж-е требование имеет приоритет 1, за время его ожидания и обслуживания не поступали' «синие» требования приоритета й Полагая в (13) э=а; — а;гь получаем (4) при 0<з<аь Используя принцип аналитического продолжения, доказываем соотношения (1) — (4) при, 1г~!<1,1=1 г, Кез>0, 154 б).

Последовательность ((.гг, У= Ц образует цепь Маркова. Докажем, что при р„!(1 существует стационарное распределение этой цепи. Занумеруем состояния цепи (их счетное число) числами 1, 2,... так, чтобы состоянию ((.к=О) соответствовало число 1, в остальном нумерация произвольна. Если состоянию (1чч=й) соответствует число з, будем писать зг а(к). Рассматриваемая цепь однородна, неразложима и непериодична. Положим для каждого состояния зс в(й) уз=у!О!!+-.+/г р.!, которое можно интерпретировать как среднее время, необходимое для обслуживания Аь ...,й, требований приоритетов 1, ...

...,г. Пусть Є— матрица переходных вероятностей рассматриваемой цепи (явный вид ее нам не понадобится, а те свойства, которыми мы будем пользоваться, легко доказываются). Тогда ~' Р„у, — среднее время обслуживания требований в си!=! стеме после одного шага, если в его начале было оостояние з=з(к), Если 1!= (О, ...,О, аг, ...,гг„), причем ггг>1, то ~' Р„у, = !), (афг!)О!!+ (й, — 1)ргг+ ~» Иф;! г=! г=! !=!+! Г Г йЯ рп ~1 ~Г а (),г1 ~(у е !'= ! г=! где е= пнп Ог! (! — р,!), !<г~г и так как р„!<1, е>О.

Далее, ~~) Р„у, = 1) — ' ~~ (а рг!) р,! ( оо, г=! г=.! г=! Таким образом, видим, что выполняются условия теоремы 4.5 Введения. Следовательно, для любого й= (й!, ..., )г„) существует ':!ч п,((г) =р(к) >О, причем Отсюда следует существование 1!!и Ра (х) = Р(х), Р(1) = 1.

155 Следовательно, из (3) и (4) вытекает сушсствование прелелоМ 1пп Р,„(г) = Р,(г) и 1!гп ь!,т(з) = ы,(з). Переходя к пределу при Д!! — «оо в (1), имеем Г Р (г):= ~~~~ [Р ( О, ! г' ') — Р (О г' ) [ =1 г — ! ~)~ Р(0 г!) [г;.-!р, (о — (а, г)) — г !! ~+, (а — (а, г))[ !=! (15)~ = Р(0,) ~~~1! — 'р, (а — (а, г)) — г, 'р,(о — (а, г)) о !=! Продифференцировав (!5) по гь 1'=1,!., подставив г=1 и по- ложив х! =- Р (О, ..., О, 1,..., 1) — Р (О,..., О, 1,..., 1) + — ' Р (0,), ю=! получим систему линенных уравнении Г а, ~чх![1,! —— х, — — 'Р(0,),, о Г=:! Г а, ~ х,[1!, = х, — — 'Р(0,), '== ! (1Е) 156 ;; гР![1,(о — а,г)) -,'- Р(0,) ~ч — 'р!(а — (а,г)).

(14д о !=! Отсюда вытекает (так как по определению Р(О,г') =Р(г)) (8).; Рассмотрим систему уравнений (относительно гь...,г!) 1 — г,— ' (3!(о — (а, г)) =О, г,-' [1!(о — (а, г) ) — г~-' р2(о — (а, г) ) =О, 1 ' р! ! (о — (а, г) ) — г;-' р;(о — (а, г) ) =О. В силу леммы 1.1 она имеет единственное решение г, =пи (о! — (а, г) !), „, г! =пи(о! — (а, г) !). Подставляя эти значения гь ...,г! ~в (14), получаем (10). Най-1 дем теперь Р(0,).

Перепишем соотношение (8) в виде Р(г) [! — г —,'р!(о — (а, г))[+ Г Г а, ~Ух р„— х, — ~' Р(0,), ~~х, = 1, !=1 !=! откуда Р(0,) = 1 — рсо !х! = — "', о Р(0,..., О, 1, ..., 1) = 1 — —" р„. Соотношение (7) является непосредственным следствием (3) Докажем (6). Из (4) при Л! — оо (сушествование пределов нами уже доказано) получаем )сН ) ! !) а! и(!) й(0 Заметим, что, как следует из определения х! и из (7) при х= = 1, р;(1) =х!=а!!!о. Найдем р;(1,..., 1, 1 — з/а!, 1,..., 1). Подставляя в (7) г! =ге=...

... =г!,=г!+,—— ... — — г,—— 1, получаем Р, (1, ..., 1, г„1, ..., 1) = = (Р(0, ..., О, г„1, ..., 1) — Р (О, ..., О, 1, ..., 1) ) Х Х г-,.-' р, (а, — а!г!) -!- (1 — р„) — ' р! (а! — а,г;) Отсюда р(о,...,о, ! — —, ),...,!) — Р(о,...,о, ),...,!) е 1 —,"а = а,.р,.(з) ! — ! Далее, так как Р(0,..., О, 1,..., 1) = 1 — са рсо ~~~ ~а!(),(р,(з))= = а!,и; ! (з), из (10) получаем Р(0,... „О, 1 — — ~, 1,..., 1) = (1 — '~'("'( )) ~ Х а, ~ а, — з 157 1 х [ "-"'-" +,'),'— "й;(р,(.)) — ~,(р;(э))1~ = /=/ Г Ро/ ( а,р,(р,(»)) 1 — ! (,, ог-!л,,(«) т)ч сч /= !.!-! Отсюда Р! 1, ...,1,1 — — ',1,...,11= "р/(' х а/, » — а,+а,()/(!!/(»)) ( ! х (1-р„)'+"-' "-'"'-"+ У.

Характеристики

Список файлов книги