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

Справедливость соотношения, связывающего функции о»(з, »1) и и(в, »!), следует из равейства У (1) = (Р (! ) + В (В'(() и  — независимы,  — длительность обслуживания требования), справедливого для обеих дисциплин НГО и 1 1ГО. С л е д с т в и е. Пусть р» = а[!» < 1, тогда существуют В'(() =-Ю, у(1) =:-(т, ( оо, причем функции ь»(в) =Ме-'»г, в(з) =Ме-»г определяются по формулам: 84 а) при дисциплине Г1РО ы(з)=(1 р) ! — »+ ар(») о(я) =ю(5) р(з); б) при дисциплине 1.1ГО (15) ы(з) =(1 — р) + 5 +» — ля (5) о(з) =ы(з)р(з).

5.2. Доказательство теоремы 3 основывалось на знании распределения случайного вектора (Е(!), х(()). В теореме 4 на примере дисциплины Г1РО мы продемонстрируем другой метод, для которого знание указанного выше распределения не требуется. В следующей главе этот метод будет применяться в более общей ситуации (для систем с приоритетами) как в случае дисциплины Г)ГО, так и 1.1ГО. Введем следуюшие обозначения: )р'»!(у!, ..., у„, т!, ..., т ) = Р ( у7 (т!) <у!, » я7 (т, + т,) < у,, ..., (р' ((~ т,.) < у.), у=! ы!»>(з„...,з„, !)г,..., а„) = ~ .. ) ехр( — ~ а,.т,.~ Х о о !=! Х М ~ехр ( — (згЯ7 (т,) + з,Я7(т, + т,) + ...

+ з„В'(~ т,))~] йт, ... дт,. !=1 Т е о р е м а 4. При дисциплине Г1РО функции ы!»М(з!, ... ..., з„, о!, ..., а,) определяются из рекуррентных соотношений ы(!>(з!, д!) =<о(зь д!) = (д!+а — ап(д!)) 'Х Х 1+ (- а (р (ед — п (ч!)! д! — »! + а — ар (и) ы!")(з!, ..., з„, д!, ..., о ) = (д„— з„+а — ар(е») ) ' Х 5» Х ~е!~» !! (з! з» вЂ” е з» ! + з» !)! ' ' ' Ч» !) Х ч»+ а — ап(д») Х ы!» '>(з„...,з, м з»-!+ 4»+а — ап(Ч) Ч! "° Ч вЂ” !) г)!»>(з, 1) = М'!е — 'я'и!!У~/(О) = х), 85 Д о к з з а т е л ь с т в о.

Найдем сначала распределение сл.в. )Р(г), если Ю(0) =х (в условиях теоремы 3 Ж'(О) =О, так как предполагалось, что в начальный момент система свободна). Положим о>(к> (з ()) < е — ц((>(.к> (э () ((( о Докажем, что о>(к> (з 1) — е(к — а(-аэ(я>( е — ~к э ~ Р(к> (и) еи — а+аз(ви — а> ((и к (17) где ( к> О, и<х, Р(Ф'(и) == О/В'(0) =х), и ) х.

е — ап — >>васе — ы е — '((>ео (з () ( ~ !э(к> (и) е а(1 — а(к>>и — а> (! (! е — 5а) к вытекает теперь из следующих рассуждений. Для того чтобы за время 1 не поступали «плохие» требования и за время х— «катастрофы» (вероятность чего равна е — а((-а(к(»е-'"), необходимо и достаточно, чтобы: 1) либо «катастрофы» не поступали за время 1+((к (1); вероятность этого события равна е "(о (к>(з, Г); 2) либо первая «катастрофа» поступила в интервале (и, и+ +((и), х(и<(, причем в этот момент система была свободна (и, следовательно, все поступившие до момента времени и требования, а они уже обслужились, «хорошие») и за время ! — и не поступали «плохие» требования; вероятность этого события равна Ро (и) е (((! — -е (к> — а(( — мок( — а~ г ~, — ~а) Воспользуемся методом введения дополнительного события. Будем считать, что в систему поступает пуассоновский поток «катастроф» с интенсивностью з.»0, который не требует обслуживания и не влияет на обслуживание требований.

Тогда р(з) можно интерпретировать как вероятность того, что за время обслуживания требования в систему не поступали «катастрофы». Условимся называть каждое поступающее требование «хорошим», если за время его обслуживания не поступали «катастрофы», и «плохим» вЂ” в противном случае. Тогда каждое требование является «хорошим» с вероятностью р(з) независимо от остальных. Следовательно, потоки «хороших» и «плохих» требований являются пуассоновскими с интенсивностями ар(э) и а[1 †(з)) соответственно. Соотношение (17), переписанное в виде Умножая (!7) на е-о' и интегрируя по 1 от 0 до ао, получаем е-" — а(;)(о) о)(*) (з, д) = Π— е+ а — ар (е) (18) где р(*) (у) = ) е — Ро Я И(, о Рассмотрим уравнение (относительно з): д — з+а — ар(з) =О.

Очевидно, функция з(у) =У+а — ап(д) является его решением. Так как прн Кеу)0 Ке(У+а — ап(())))0, то о)(а)(з, д) при э=У+а — ап(д) ограничена, Но это возможно только в том случае, когда е-" — зро( )(у) =0 при з=()+а — ал(д). Отсюда находим рооп(д)1 р (л) (У) — ]У+и ап (У) ] — 1Е-(а ' а — а»(ане Подставляя найденное значение ро(а)(д) в (18), получаем ее — (р-(-а — ал(»а а о)(а) (з д) = ]д — з ч- а — ар (з)] — 1 ) е — '*— +.— - )] О)(л Н(З(, ", Зл — г, У -1 У! - Чл-1) = — 1 ... ] ехр~ — ~, д(т,)М]ехр( — (з(В'(т,) + згяу(т, + т,) + о о ! =-1 — г л — 1 + ° ° ° + Зл — г)а Д' т())) ! ((е (Я т)) С Ул — 1)) ((т) ° .

° ((тл — 1 из равенства (19) получаем (о(л)(з з у д) — ~ е 'л !ал !о)(а» !)(з у) )( о (» — 1) Х ((ел (о) (з(* ° ° зл-г, Ул-1 Ч(~ ° Ул — 1). Но -(аЧ-а — ал(оа а, о)(а) (з, д) = (д — з + а — ай (з)] — ' ]е-еа — м О+ а — ал(д) 87 Легко показать, что )))(1) — однородный марковский процесс. Следовательно, (()(а)(у, 1) =Р()()'(!) <У]((г(0) =х) представляет собой его переходную функцию и Ю' (У1, ° -, Ул, т(, ° —, тл) = ал 1 )()лм (у» т„) ((„(Рч" ') (у,,..., Ул ь и, т,, ..., тл 1). (19) о Полагая Следовательно, »!!л! (З З»л» )— — а ар (З )] — ! ~~ ~ Е !1л-1»л-1+1»1ял-1! о »л ~Л-1 Л-1 е — !»»+» — »»!Р»!!»Л-1 ~ дл + а — ая (Ч») !л — П Хйе ы (з! ° ° з» вЂ” ь9» — ! ч! ч» — !)~ = = (а„— ел+ а — ар(зл)) — ' (ы<л — '!(з„..., зл ь зл !+з., д1, ..., д» !)— — ы!»-'!(зп ...,а-их ! т д, + а— чл+ а»п (1Ь1) — ан(дл), а1,..., дл !)~.

6. Метод вложенных цепей Маркова, Одним из наиболее распространенных методов исследования систем массового обслуживания является метод вложенных цепей Маркова. Сущность метода заключается в рассмотрении изучаемого случайного процесса (вообще говоря, немарковского) в специально подобранные моменты времени, значения процесса в которые оказываются связанными в цепь Маркова. В этом пункте этот метод будет использован для анализа системы М)6~1~»о при дисциплине Г!РО.

Занумеруем требования в том порядке, в котором они поступают в систему. Пусть (к (1»'=1, со) — момент окончания обслуживания У-го требования, 1»=0, тп=(л — 1л 1, Уъ1. Так как входящий поток пуассоновский, последовательность ((.к, Ф) 1), 1и=1. ((и+О), образует цепь Маркова. Положим Р» (И =- бдо, рк(А) = Р(1.л =-Ф), Рл(г) = Мг~"„ р (и1, г) =- ~~ ю~Рл (г), м=в Р,'ч~'(1г,, ..., йл, и„..., и„) =— = Р(1.к = й1,, 1.л+» ! == й», тк(и,, ..., тл+» ! с. и»), л л р<л>(г,,..., г„, з,,...,з ) =- М! П г, л+! — 'ехр( — 'Г зтл+; !)), И !» !» л» =! /=! Кл и )1к — соответственно время ожидания до начала обслу- 88 )кнвания и время пребывания в системе ))(-го требования, ын(5) =Ме ~н, он(5) =Ме ' ", ° » (ш, 5) = ~ шнь)н (5), о (ш, 5) = Я а чон (5). и=! и=-! Теорем а 5.

а). Функции Рн(2), ын(5) и он(5) удовлетворяют соотношениям гРн).)(2) = (Рн(2) — Рн(0)+2Рн(0)([)(а — аг), (20) ын(5) = (р(5)) 'Рн(1 — (5/а)), (21) он(5) =ын(5)Р(5). (22) б). При )5е5)0, [2[<1, [и)[<1 функции р(ш,г), ь)'(ш,5) и о*(ш,5) определяются по формулам р(ш, г)— 7 -)- (7 — ! ) ы!Р (й — й ) [1 — )!) (ы)1 7 — )йР (й — й7) ы'(ш, 5) = !й [й — 7 (! — 4) (й!))'1 (24) й — 7 — й)ьР ($) о (ш,5) =ь) (ю,5)р(5), (25) где )[) (ш) — единственное решение функционального уравнения )р(ш) =шр(а — а)р(ш)), аналитическое в области (ш! <1, где [)р(ш) ( <1. в) Функции рн!") (г), ..., г„, 5), ..., 5„) определяются из рекуррентных соотношений Р)н!)(г, 5) = (Рн;(г) — Рн )(0)] ' + 7 (26) + Рн )(0) р(5»-а — аг), 5 -)- й Рь!») (2! 2 = (РК!» )(2! 2, 7 2» )2» 5! 5» !)— 7» + р"' — ') (г,, ..., г„й, О, 5,, ..., 5„!) р (5» -!- а — аг»).

(27) 5» -)- й г). Если р)=ар)<1, существуют пределы Ел=~~., Ртн=7-Ж', [75--ь- 1', А' — ~-йо, [ни рн!")(2), „,, 2„, 5), „, 5») =!о!")(2), „, 21„5),, 5»), к причем функции Р(г) =Мг"., ь)(5) =Ме — ')т, о(5) =Ме — '7 опре- 89 (28) Р (г1 гл 51 — 'Ял) = '!р "-' (г! .. г -г гл !гл я! .. ял 1)— — р'л '1(г,,гл 5,0,я„...,ял !)) " " + гл — -ргл — '1(г„....

г,— г, О, я,, ...,ял !) р(ял+ а — агл). (31) 5л + й 3 а м е ч а н и е. Функция гр(ш), введенная в формулировке. утверждения б) теоремы, представляет собой одну из важных характеристик изучаемой системы обслуживания — производящую функцию числа требований, обслуженных за период занятости (см. задачу 5).

Д о к а з а т е л ь с т в о теоремы 5. а) . Докажем сначала, что л-1-1 5Ю (аг)л рн+! (и) =- У рн(/г) ~ е-" с!В(х) + (л — л+ 1)! 5=! о + рн (0) ~ е — '" ' — 7(В (х). л! о (32) Пусть Р„== Р(Ен.5! = !УЕн = !), тогда по формуле полной ве- ' 1У) роятности л-1-! рн,!(и) = ~ рн(4)Р',„' ь р,(0)Р,"„', 5=! но ргн) — ак (аг) л — 5+! — (е— (л — а+ 1)! о 7(В (х) = Р,„, ! < )г < и + 1. Действительно, при А> ! (Л!+1)-е требование находится в системе в момент окончания обслуживания Л1-го. Поэтому для того, чтобы после окончания обслуживания (Л1+1)-го требова- 00 деля!отсн соотношениями (! — 55) (г — !) Р (й — йг) Р(г) = г — (! (а — аг! ог (я) = м , о (я) =- !о (я) р (я) 5 — а + ар (5) а функции р1л1(г1, ...,гл, 51, ..., я„) определяются из ных соотношений р1" (г, я) =-(! — р,)г — !р(я+ а — аг) ~ + (г — 1! Р (а — аг! г — р (а — аг) (29) ' рекуррент- ! аг ' ! 5+а (30) ния в системе стало и требований, надо, чтобы за время обслуживания (А!+ 1)-го требования поступило и — й+ 1 требований (действительно, й было, одно (А1+ 1-е) обслужится, и, чтобы стало и, надо, чтобы поступило и — л+ 1).

Аналогично С» р'и! =~а ' (а ) ВВ(х) = Р„,. л! о Итак, (32) доказано. Умножая его на г" и суммируя по и от 0 до оо, получаем ю л-!. ! (а») — оь! р (г) = ~~~~ г»~ ри(й) ) е — * а г(В(х) и(л — л+ !)! л=-о о=! о + р (О)(. ~;1 (а-)", ак„В(х) .! ' ! л! о »=о ~ ! Ри (~Ь) ~~! «» 1 е — »ко(В (х) + (л — л+ 1)! л=! »=-о — ! о + ри (О) ~ е !а — аг!»НВ (х) =— о =г-' (рл(г) — Р (0) ) р(а — аг) -ьрл(0) Яа — аг), что эквивалентно (20). Докажем теперь, что Рл (г) = !ол (а — аг) р (а — аг) .