1. Введение в теорию массового обслуживания. Гнеденко_ Коваленко (2-е изд) (1987) (1186154), страница 48
Текст из файла (страница 48)
$5.2. Система 61 (С ! Из 1. Многомерное случайное блуждание. В настоящем параграфе будет рассмотрена система массового обслуживания с ожиданием с т обслуживающими приборами. Входящий поток с ограниченным последействием, В(х) — функция распределения 2)„, где ц„— длительность обслуживания п-го требования, А(х) = = Р(2„(х), где 2„— длительность интервала между поступлениями в систему (и — 1)-го и и-го требований. Будем считать случайные величины 12)„) и (з ) независимыми в совокупности. Обозначим через и) длительность ожидания и-м требованием начала обслуживания, и ~ 1. При т ) 1 не удается непосредственно связать ю„с и)„,.
Приходится рассматривать многомерное случайное блуя(дание. е) МВСК (МЕ22 12 ЬЕ((ЕГ Оу Пас() Ш атотадс — НОВЫЙ (ЗЛЕМЕНТ) ЛУЧШЕ НС- пользованного в среднем); МЖ()Е (Меч) 12 ногае о1 пзе() ш атегале — новый хуже использованного в среднем). 9 5.а систеыл Опо)п~ 255 рассмотрим функционирование г-го прибора в отдельности. Вудем считать, что входящий поток для него — тот же, что и для всей системы, а длительность обслуживания и-го требования равна п„„где ц ~ = п„в случае, если данное требование действительно поступило на этот прибор, т~„~ = О в противном случае. Введем случайную величину ит; — время с момента 1„до момента освоболгдення г-го прибора от требований, поступивших ранее ~„, вли О, если все они обслужены до момента г . Тогда для (юы) удовлетворяется рекуррентное соотношение, аналогичное (5) иэ ~ 5,1, а именно: "=( .—, +Ч.— с' — .) .
В то же время иЪ = ш1в ю„и (2) 1 ля ~1В так как лгобое требование поступает на прибор с минимальным временем ожидания. Случайные величины ц„, определяются формулой чг~ иь = ипч~ Чп1 = юь'с юьи в том случае, если среди чисел ю„о ..., ю„ лишь одно минимально. Если же, скажем, иЪ = ю„;, = ... = иь;„, а все остальные ю„, ~ ю„, то необходимо определить правило выбора среди номеров ~„ ..., г,.
Так как на распределение (ю„) это правило не влияет, будем считать, что ив множества (го ..., г„) выбирается по равновероятному закону то г, для которого ц ~= в),; для всех остальных ) полагается ц„, = О. Случайные величины Ю =(ю„„..ч ю„„) определяют пг-мерное случайное блуждание. 2. Эргодическая теорема Кифера и Вольфовица (2].
Теорема. Пусть т=Мт1 (со, Х '= Мвю р=)т. Тогда: 1) если р ( пг, то (и„) обладает зргодичеснии распределением; 2) если р ) т, то при любых х, у =(у„..., у„) Р(ю„(х)и, у) — О; (3) 3) если р = пг и с положительной вероятностью г)„Ф тг„, то выполняется условие (3); 4) если р=пг и Ч =те„с вероятностью т, то величины и детерминированы и ограничены; ю„периодически (с перродом гп) зависят от и.
Мы докажем лишь ту часть теоремы, которая относится к случаю р ( пг. Вначале докажем некоторые леммы. Условимся понимать неравенство х (у для векторов х, у как систему неравенств х~ ( у~ для соответствующих компонент этих векторов. 256 Гл. б, пРименение БОлее Овщих методов Пусть у. (у„„..., у. ) — вектор, компоненты которого— упорядоченные в неубывающем порядке компоненты вектора Ю„; Рп(х«У) = Р(дп(х«ед У), Еп(х) = Рп(х«О). Обозначим еще 7(г, Ч«у) значение вектора д„при фиксированных значениях д„, = у, г„= г, Ч„, = Ч. (Легко заметитть что внд функции у не зависит от и.) Лемма 1. Еслиу(у', Ч(Ч', г«г', то 7(г, Ч«У)(~(г', Ч'«У').
(4) Доказательство. Обозначим через п„(х) число компонент вектора х, меньших х; Е(х)= 0 при х ~ 0, Е(х) 1 при х «О. Тогда п„О(г, д1 «у)) = Е(х — у — т1 + г) + ~ Е(х — у; + г). (5) з=з Так как функция Е(х) — неубывающая, то иэ (5) следует, что и (д (г, Ч!у))«п„(у(г', т1'«у')).
Зто и означает, что любая компонента 7(г, Ч«у) не превосходит соответствующей компоненты П ', ч'«у'). Следствие. Пусть (у,) построены по данным Чь г, у=уз, «д„« — аналогичная последовательность, построенная по Ч» гдд у', причем гд)гг, Ч;(Чи у ( у'. Тогда для любого п 1 уп ( Кп. Для доказательства достаточно проитерировать неравенство (4). Отсюда р (х) «Р (х «в) Лемма 2.
При любом и «2 Ез (х) < Е,(У). До к аз а тел ь ство. Можно записать Уз=1(гз, Чз«дз), .", Оп=1(гп, Ч--з«д.-з) По етому же типу запишем формулы для уб, ..., у д в котсрых, однако, вместо Б„Чз будек писать гз+» Чз+„что, естественно, ие нарушает закона раопределення: Уз= 7(гзз Чз«0) з ° °, ьп-д=1 (г з Ч -з«Уп-з) ° Сравнив последние две формулы и применив лемму 1, получим уз = 7(гз, Чз«уз)«7(гн Чз«0)= Уз д =7(гз, Чз«дз) «7(гз, Чз«дз) = Узз У.=Пг., Ч.— «у--)«У(г., Ч.— «уп — г) =уп-д З Кз. СИСТЕМА О1(с~ее 257 Итак, у = Е„(зв, ° ° .в зе1 Цв, ° ° в ве-в)~~ ~ ~Ь-в(зв, °, 2; 11в, ° ., 1)„-1).
(7) Пусть Хе(д„) — случайная величина, равная 1 при д„~х и раьвая 0 в противном случае. Тогда из (7) имеем 1„-(я„)( ~1 (о„,). Перейдя к математическим ожиданиям, получим г"'„(х) ~ Р„-,(х), чго и требовалось доказать. Б л е д с т в и е. Существует Р (х) = Пш г'н(х). н ао рассмотрим вспомогательную «циклическую» систему обслу- япввавпя, в которой распределение требований по приборам про- исходит в циклическом порядке: если п = — 1(шойт), то я-е тре- бование посылается на 1-й прибор.
Случайные величины, отно- сяшлеся к циклической системе, будем обозначать аналогично относящимся к системе с общей очередью, но заглавными бук- вами вместо строчных. Будем считать, что в обеих системах по- следовательности (2 ), (1) ) одни и те же. Пусть в циклической системе некоторый прибор обслужива- ет требование в интервале (2, 1+ цв) и приступает к обслужи- ванию следующего требования в момент г+ 11„+ е,.
В таком случае заменим т)в па Чв+ ев, т. е. положим т)а = Ча+ еа. Пере- ход от 1)а к 1)ь, очевидно, может лишь увеличить величины 6аь При новых значениях длительностей обслуживания перерывов в обслуживании не будет, и система превратится в систему с об- Р щей очередью, т. е. 6„= я„, где 6„и я„— величины, в кото/ рые перейдут 6„, ре при переходе от цв к цю По следствию лем- мы 1 при обратном переходе компоненты я. могут лишь уменьшиться.
Итак, ~„< 6„'. (8) Пусть 6„+, 1 = 6'„'~. Последовательность (6нн) имеет смысл (1з.) для системы 666)1 с распределением В(х) времени обслуживания и распределением Ансе(х) времени между поступлением требований. Таким образом, ее загрузка меньше единицы, откуда (9) Р (61о е" х) Ф (х), где Ф (х) — функция распределения. Пусть л = йт+ 1,. Тогда 6 'о =шах(6„;,, 2,+1+ ... + 2 +~), + 6о,в +1 = Пваз ((6н — ев+1,1 +1 (2~-ва+е + " в + зн)) в н+1) вв в. з. Гнененко, и.
н. коваленко гл. з. пгвмвнинии волки овщих мвтодов 258 и т. д. Следовательно, ввиду (9) зпрР [С„~ ) х) — ~ О, » х-~ а тогда в силу (8) зто же свойство выполняется и для (у..). Отсюда следует, что «'(х) = 11ш «'„(х) — функция распределе»-> сю нпя. Так как [Г/~„'~) — зргодические цели Маркова, то в силу выведенных выше соотношений между у» и [С'„' ] найдется такое х, что число возвращений у. в множество состояний (у„< х) бесконечно с вероятностью 1. Если р < т, то это означает, что с положительной вероятностью ц < з, +...
+ з„. Найдутся такие е ) О и Ь ) О, что Р(т~„~(та — е) ~~б, Р(з„) а) ~~6. «0) Предположим теперь, что у„~ <х, 1» ~» т, и что ц., з.+~ при г ~ и удовлетворяют неравенствам «О). Тогда аа [тх/е)+ 1 шагов очередь исчезнет; при этом распределение случайного вектора д», У = и + [тх/е) + 1, уже не будет зависеть от д . Далее, очевидно, г.(*,.",» Ь,",»)»г.[ — »," - — Во): ч\ 1=1 1=1 отсюда выводим, что равномерно по и при фиксированных у, «"„(х„..., х„!у„..., у„)~ с) 0 (11) при достаточно большом х. Обозначим через А„ событие (-'- тх у„; ( х, 1 ( 1 ~( т; ц, ( та — е, з,+, ) а, и ( з ~( — + 1~. - е События (А ) будут рекуррентными (см.
Феллер [3)), так что можно записать «'„(х, ..., х (у, ..., у )= ~~~~ Р(А,А,, Аь гАь[ у„..., у ) Х а=1 Х ) «и — ~ (хг~ ° ° ° з хщ ! Ум ° ° ° ~ Уя) аФ (Угг ° ° ° з Уи) + +ЕР(А,...А„), «2) где 1 = [тх/з) + 1, О » В » 1, Ф(х„ ..., х ) — условное распределение случайного вектора и*= [и,,..., ш ), где и; — расположенные в порядке возрастания случайные величины 1 и; = ТК вЂ” ~ зьез, 1 ~ ($ (» т, «3) ь=з 259 з б,з, системА м~ с 1т ~ 0 еловик, что для всех тп и з,+, в формуле (13) выполнено условие (10). При некотором а и достаточно малом е ввиду неравенства Р„(х„ ..., х,„)3- Р„+,(х„ ..., х ) последовательность (~-- (" ) др(...)), столщвн пР вой части Формулы (12), будет невозра Поскольку, далее, в силу оценок (10) и (11) ~А...А„) о, лов учим )'", (х„. ° ., х„(Р„..., р„) Ф 1 =П-1~.(х„..„..~„„.
„,„., В частности, подставив у~ =... = у = О, будем иметь Пт Р„(хы ..., х,„(ры ..., Р,„) = Р (х, ..., х,„). Это говорит о том, что предельное распределение является эрго- дическим. б 5.3. Система М(С (лз(О $. Эргодическая теорема. Рассмотрим систему М(С!т(0 с функцией распределения В(х) длительности обслуживания и параметром Х входящего потока. Результат, который будет здесь изложен, состоит в том, что формула Эрланга (з 1.4) справедлива при произвольном В(х), если обозначить р =Хх, т = ) 8(1) Ж. о Пусть т(1) обозначает число приборов, в момент 8 занятык обслуживанием требований.
Предположим, что в некоторый момент времени ч(1) приняло значение й (1 ~ х ~ и) (стало быть, т(~ — О)~й). Присвоим тем приборам, которые заняты в момент 1, индексы от 1 до й в случайном порядке. Представить себе зто можаю следующим образом. В урку кладется й шаров с номерами занятых приборов. Затем из псе случайным образом извлекается один шар; если на нем стоит ~~мер 1о то (,-му прибору присваивается индекс 1, а сам шар в Урву не возвращается. Второму шару будет соответствовать индекс 2 и т. д,, пока все шары не будут извлечены.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
